OrderedDict：维护插入顺序的有序字典

字数统计: 3.5k字 | 阅读时长: 16分

2020-11-15

摘要: 维护插入顺序的有序字典

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 LRU：维护最近访问/插入的元素和 LFU：维护最频繁访问的元素中，我们分别以模板题介绍了 LRU 和 LFU 的原理与实现。它们都属于有序字典的一种。

有序字典简单理解就是在字典的基础上保持有序，是一种哈希表+链表的结构。其原理是结合哈希表的高效查找以及链表的高效插入删除的优点，在保持哈希表高效增删改查的基础上，利用链表节点间有顺序的特性，维护元素的某种与增删改查有关的顺序。

这里的顺序根据需求可能是插入时间顺序 (OrderedDict)、访问时间顺序 (LRU)、访问频率顺序 (LFU) 等。

本文我们详细介绍 OrderedDict 的原理与实现，用 OrderedDict 解决 340. 至多包含 K 个不同字符的最长子串并对比传统的滑动窗口+哈希表的方法。

维护插入顺序的字典

链表具有优秀的插入删除性能，因此如果在维护数据的过程中对数据插入顺序有需求的话，持有数据的数据结构用链表是不错的方案。

而链表由于查找的性能不太好，但是可以将数据的 key 和链表节点分别作为键和值交给哈希映射。查询的需求通过哈希映射找到节点，而插入顺序直接由链表的插入维护。

把 key 和链表节点放到哈希映射中，可以视为是对链表做了一层哈希索引，参考加索引的链表。

当需要通过 key 快速查询数据并且在维护数据过程中需要维护数据的插入顺序时，双向链表+哈希映射是比较好的解法。

双向脸部和哈希表我们此前都详细介绍过，并写过代码模板，参考文章：

OrderedDict

Python 中有序字典 OrderedDict 是 collections 提供的一种数据结构，它提供了维护插入顺序的 dict 结构。但是需要注意当插入时 key 如果已经存在，则不会讲 key 调度到表头。

源代码: https://github.com/python/cpython/blob/master/Lib/collections/__init__.py

关键点：

一个继承自dict的键值对字典
继承的字典提供 __getitem__, __len__, __contains__, get 方法
所有方法的时间复杂度均与正常的字典一样.

内部的 self.__map 字典将key与双向链表的指针关联在一起
循环双向链表是以一个哨兵元素作为开始和结束节点的
哨兵元素永远不会被删除.

双向链表+哈希映射实现 OrderedDict

接口

put、get、remove 就是哈希表的插入，查询，删除。但是有一点变化，就要插入时，如果 key 已经存在，需要调度到表头。这里需要注意 Python 标准库里的 OrderedDict 在插入时，如果 key 已经存在，则不会自动调度到表头，需要自己用 move_to_end 操作，见后面的题解。

1
2
3

void put(int key, int value)
int get(int key)
int remove(int key)

再此基础上新增 remove_buttom ，删除最早插入的节点。

1	int remove_buttom()

哈希表和双向链表如果用 STL，则实现起来简单一些，见后面的题解代码。下面看一下哈希表和双向链表都用模板的实现代码。

数据结构设计

链表的容量用一个默认的很大的值。即不带容量限制和扩容。

链表的数据类型为 int，也是哈希表的键。

1
2
3

typedef int DLType;
const DLType DLTypeNULL = -1;
const int MAX_LEN = 1e6;

哈希表用比哈希表模板，容量提前计算好，不带扩容和重哈希。

哈希表的键为 int，值为自定义类型 ValueType，持有 int 类型的值和链表节点的指针。

const int INF = 1e9;
typedef int HashType;
struct ValueType
{
    int value;
    DLNode *list_node;
    ValueType(int v=-1, DLNode *node=nullptr):value(v),list_node(node){}
    bool operator==(const ValueType& v) const
    {
        return value == v.value && list_node == v.list_node;
    }
    bool operator!=(const ValueType& v) const
    {
        return !(*this == v);
    }
};
const ValueType VALUENULL(-1, nullptr);

CloseHashTable 和 DoubleCircleList 两部分除了哈希表的值的类型自定义之外，其余的代码复制模板：

有序字典的数据结构如下，有序字典本身不带容量限制。

1
2
3

const int hashtable_capacity = 99991;
DoubleCircleList linkedlist;
CloseHashTable mapping;

完整代码 (C++，模板)

带插入顺序的字典，双向链表和哈希表分别使用代码模板 DoubleCircleList 和 CloseHashTable。

#include <iostream>

using namespace std;

typedef int DLType;
const DLType DLTypeNULL = -1;
const int MAX_LEN = 1e6;
struct DLNode
{
    DLType val;
    DLNode *next;
    DLNode *prev;
    DLNode(DLType x) : val(x), next(nullptr), prev(nullptr) {}
};

class DoubleCircleList
{
private:
    // head 一直指向 dummy
    // tail 在空表时指向 dummy，否则指向 head 的前一个节点
    DLNode *head, *tail;
    int length;
    int capacity;

public:
    DoubleCircleList(int N=MAX_LEN)
    {
        head = new DLNode(0);
        head -> next = head;
        head -> prev = head;
        tail = head;
        length = 0;
        capacity = N;
    }

    bool removeHead()
    {
        if(isEmpty())
            return false;
        remove(get_head());
        return true;
    }

    bool removeTail()
    {
        if(isEmpty())
            return false;
        remove(get_tail());
        return true;
    }

    DLType getHead() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_head() -> val;
    }

    DLType getTail() const
    {
        if(isEmpty())
            return DLTypeNULL;
        return get_tail() -> val;
    }

    DLNode* insertHead(DLType val)
    {
        if(isFull())
            return nullptr;
        return insert(head, val);
    }

    DLNode* insertTail(DLType val)
    {
        if(isFull())
            return nullptr;
        return insert(tail, val);
    }

    DLNode* insert(DLNode *pos, DLType val)
    {
        if(!pos || isFull())
            return nullptr;
        DLNode *cur = new DLNode(val);
        cur -> next = pos -> next;
        cur -> prev = pos;
        pos -> next -> prev = cur;
        pos -> next = cur;
        if(tail == pos)
            tail = cur;
        ++length;
        return cur;
    }

    DLType get(DLNode *pos) const
    {
        if(!pos || is_dummy(pos))
            return DLTypeNULL;
        return pos -> val;
    }

    DLNode* remove(DLNode *pos)
    {
        if(!pos || is_dummy(pos) || isEmpty())
            return nullptr;
        if(tail == pos)
            tail = tail -> prev;
        --length;
        pos -> prev -> next = pos -> next;
        pos -> next -> prev = pos -> prev;
        DLNode *result = pos -> next;
        delete pos;
        pos = nullptr;
        if(isEmpty())
            return nullptr;
        if(is_dummy(result))
            result = result -> next;
        return result;
    }

    bool change(DLNode* pos, DLType val)
    {
        if(!pos || is_dummy(pos))
            return false;
        pos -> val = val;
        return true;
    }

    DLNode* get_next(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_tail(pos))
            return get_head();
        return pos -> next;
    }

    DLNode* get_prev(DLNode *pos) const
    {
        if(isEmpty())
            return nullptr;
        if(is_head(pos))
            return get_tail();
        return pos -> prev;
    }

    bool is_dummy(DLNode *pos) const
    {
        return pos == head;
    }

    bool is_head(DLNode *pos) const
    {
        return (!isEmpty() && pos == head -> next);
    }

    bool is_tail(DLNode *pos) const
    {
        return (!isEmpty() && pos == tail);
    }

    DLNode* get_tail() const
    {
        if(isEmpty())
            return nullptr;
        return tail;
    }

    DLNode* get_head() const
    {
        if(isEmpty())
            return nullptr;
        return head -> next;
    }


    bool isEmpty() const
    {
        return head == tail;
    }

    int size() const
    {
        return length;
    }

    bool isFull() const
    {
        return length >= capacity;
    }

    void traverse() const
    {
        auto iter = head -> next;
        while(iter != head)
        {
            cout << iter -> val << " ";
            iter = iter -> next;
        }
        cout << endl;
    }
};


const int INF = 1e9;
typedef int hashType;
struct ValueType
{
    int value;
    DLNode *list_node;
    ValueType(int v=-1, DLNode *node=nullptr):value(v),list_node(node){}
    bool operator==(const ValueType& v) const
    {
        return value == v.value && list_node == v.list_node;
    }
    bool operator!=(const ValueType& v) const
    {
        return !(*this == v);
    }
};
const ValueType VALUENULL(-1, nullptr);

class CloseHashTable
{
private:
    struct Node
    {
        hashType data;
        ValueType item;
        int state;
        // 0: Empty  -1: deleted
        // >0: cnt / active
        Node()
        {
            state = 0;
        }
    };

    Node *arraytable;
    int sizetable;
    int (*key)(const hashType& x); // 将 key 变成一个整数，如果 key 本身是整数直接返回
    const double A = 0.6180339887;

    static int defaultKey(const int &k)
    {
        return k;
    }

    int hash1(const hashType& x) const
    {
        if(key(x) < 0)
            return key(x) % sizetable;
        return (key(x) + INF) % sizetable;
    }

    int hash2(const hashType& x) const
    {
        double d;
        if(key(x) < 0)
            d = (key(x) + INF) * A;
        else
            d = (key(x)) * A;
        return (int)(sizetable * (d - (int)d));
    }

public:
    CloseHashTable(int length=20011, int (*f)(const hashType &x)=defaultKey)
    {
        sizetable = length;
        arraytable = new Node[sizetable];
        key = f;
    }

    ~CloseHashTable()
    {
        delete [] arraytable;
    }

    ValueType findx(const hashType& x) const;
    bool insertx(const hashType& x, const ValueType& v);
    bool removex(const hashType& x);
};

ValueType CloseHashTable::findx(const hashType &x) const
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return VALUENULL;
        if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
            return arraytable[pos].item;
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return VALUENULL;
}

bool CloseHashTable::insertx(const hashType& x, const ValueType& v)
{
    int initPos = hash2(x);
    int pos = initPos;

    do{
        if(arraytable[pos].state <= 0)
        {
            arraytable[pos].data = x;
            arraytable[pos].item = v;
            arraytable[pos].state = 1;
            return true;
        }
        else if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
        {
            // 有重映射将用新值覆盖 item 改为将新值插入 items
            arraytable[pos].item = v;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

bool CloseHashTable::removex(const hashType &x)
{
    int initPos = hash2(x);
    int pos = initPos;

    do
    {
        if(arraytable[pos].state == 0)
            return false;
        if(arraytable[pos].state > 0 && key(arraytable[pos].data) == key(x))
        {
            // 有重映射改为将节点下的所有 item 删掉，将 arraytable[pos].state 改为 -1 后返回
            arraytable[pos].state = -1;
            return true;
        }
        pos = (pos + 1) % sizetable;
    }while(pos != initPos);

    return false;
}

class OrderedDict
{
public:
    OrderedDict()
    {
        linkedlist = DoubleCircleList();
        CloseHashTable mapping(hashtable_capacity);
    }

    ~OrderedDict(){}

    void put(int key, int value)
    {
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            DLNode *node = v.list_node;
            linkedlist.remove(node);
            mapping.removex(key);
        }
        DLNode *node = linkedlist.insertHead(key);
        mapping.insertx(key, ValueType(value, node));
    }

    int get(int key) const
    {
        ValueType v = mapping.findx(key);
        if(v == VALUENULL)
            return -1;
        else
            return v.value;
    }

    int remove(int key)
    {
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            DLNode *node = v.list_node;
            linkedlist.remove(node);
            mapping.removex(key);
            return v.value;
        }
        else
            return -1;
    }

    int remove_bottom()
    {
        int key = linkedlist.getTail();
        ValueType v = mapping.findx(key);
        if(v != VALUENULL)
        {
            // DLNode *node = v.list_node;
            // linkedlist.remove(node);
            linkedlist.removeTail();
            mapping.removex(key);
            return v.value;
        }
        else
            return -1;
    }

    int size() const
    {
        return linkedlist.size();
    }

    void traverse() const
    {
        DLNode *head = linkedlist.get_head();
        DLNode *iter = head;
        do{
            cout << iter -> val << " " << mapping.findx(iter -> val).value << "; ";
            iter = linkedlist.get_next(iter);
        }
        while(iter != head);
        cout << endl;
    }

protected:
    const int hashtable_capacity = 99991;
    DoubleCircleList linkedlist;
    CloseHashTable mapping;
};

340. 至多包含 K 个不同字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出至多包含 k 个不同字符的最长子串，并返回该子串的长度。

示例 1：
输入：s = “eceba”, k = 2
输出：3
解释：满足题目要求的子串是 “ece” ，长度为 3 。

示例 2：
输入：s = “aa”, k = 1
输出：2
解释：满足题目要求的子串是 “aa” ，长度为 2 。

提示：

1 2	1 <= s.length <= 5e4 0 <= k <= 50

算法1：滑动窗口 + 哈希表

与 159. 至多包含两个不同字符的最长子串的解法相同。

滑窗左右边界为 left 和 right，都初始化为 0。然后向右移动 right 指针保证区间内含有不超过 k 个不同字符。当移动到含有 k + 1 个不同字符的时候，移动 left 指针直到区间内不含有超过 k + 1 个不同字符。

对于最好情况，如果字符串不超过 k 个不同字符。只需要一次遍历就可以得到结果，时间复杂度是 $O(N)$。

对于最坏情况，当输入字符串包含 n(n > k) 个不同字，每一步都需要花费 $O(k)$ 时间找到哈希表中的最小值，时间复杂度为 $O(Nk)$

代码 (C++)

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        if(s.empty() || k == 0) return 0;
        int n = s.size();

        int left = 0, right = left + 1;
        unordered_map<char, int> mapping;
        mapping[s[left]] = 1;
        int result = 0;
        while(true)
        {
            while(right < n)
            {
                auto it = mapping.find(s[right]);
                if(it != mapping.end())
                    ++(it -> second);
                else if((int)mapping.size() < k)
                    mapping[s[right]] = 1;
                else
                    break;
                ++right;
            }
            if(right >= n) return max(result, right - left);
            result = max(result, right - left);
            while((int)mapping.size() == k)
            {
                --mapping[s[left]];
                if(mapping[s[left]] == 0)
                    mapping.erase(mapping.find(s[left]));
                ++left;
            }
        }
    }
};

算法2：OrderedDict

为了达到 $O(N)$，需要一种数据结构，保证以下四种操作都可以在 $O(1)$ 时间完成，这正是 OrderdeDict 的功能：

插入 key: put(key, value)
获取 key(隐含判断 key 是否存在): get(key)
删除 key: remove(key)
获取最早插入的 key 并删除: remove_bottom()

这个需求与 LRU 的功能很像，从数据结构层面上看，相当于在哈希表的基础上增加了链表换取获取最早插入的key这个操作的 $O(1)$。

这个结构的目的是在哈希表的 $O(1)$ 插入查找删除的基础上使得主动地获取最早插入的key这个操作也 $O(1)$，而不是插入时空间不够了被动地获取最早的元素。因此与传统 LRU 有几个关键区别：

没有容量限制
插入时不会判断是否达到空间限制，以及达到空间限制的后续动作
查询时不会将查询到的节点调度到表头

代码 (C++，模板)

以下代码是使用 STL 的 OrderedDict 代码模板。

将 OrderedDict 的实现改为前面的使用 CloseHashTable 和 DoubleCircleList 的代码模板，可以进行测试。

class OrderedDict {
public:
    OrderedDict() {}

    int size() {
        return linkedlist.size();
    }

    int get(char key) {
        auto it = mapping.find(key);
        if(it == mapping.end())
            return -1;
        else
            return (it -> second).first;
    }

    void put(char key, int index) {
        auto it = mapping.find(key);
        if(it != mapping.end())
            remove(key);
        linkedlist.push_front(key);
        mapping.insert(pair<char, pair<int, list<char>::iterator>>(key, pair<int, list<char>::iterator>(index, linkedlist.begin())));
    }

    void remove(char key) {
        auto it = mapping.find(key);
        if(it != mapping.end())
        {
            auto iter = (it -> second).second;
            linkedlist.erase(iter);
            mapping.erase(it);
        }
    }

    int remove_bottom()
    {
        char key = linkedlist.back();
        int index = mapping[key].first;
        mapping.erase(mapping.find(key));
        linkedlist.pop_back();
        return index;
    }

private:
    unordered_map<char, pair<int, list<char>::iterator>> mapping;
    list<char> linkedlist;
};

class Solution {
public:
    int lengthOfLongestSubstringKDistinct(string s, int k) {
        if(s.empty() || k == 0) return 0;
        int n = s.size();

        int left = 0, right = 0;
        OrderedDict mapping;
        int result = 1;
        while(right < n)
        {
            mapping.put(s[right], right);
            ++right;
            if(mapping.size() == k + 1)
                left = mapping.remove_bottom() + 1;
            result = max(result, right - left);
        }
        return result;
    }
};

代码 (Python)

直接用 Python 的 OrderedDict，注意代码中 move_to_end 的部分，这是因为 Python 标准库中的 OrderedDict 插入时若 key 已经存在，则不会调度相应节点到表头。

from collections import OrderedDict

class Solution:
    def lengthOfLongestSubstringKDistinct(self, s: str, k: int) -> int:
        if s is None or k == 0:
            return 0
        n = len(s)

        left = right = 0
        mapping = OrderedDict()
        result = -1
        while right < n:
            if s[right] in mapping:
                mapping.move_to_end(s[right], last=True)
            mapping[s[right]] = right
            right += 1
            if len(mapping) == k + 1:
                left = mapping.popitem(last=False)[1] + 1
            result = max(result, right - left)
        return result

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法数据结构