如何高效实现有序Dict?

From: 为了使字典的键有序, python付出了怎样的性能代价? - 最大的梦想家的回答 - 知乎

2024-11-23

有序字典的官方实现

Python 的字典有序来自于 Python 3.6 中，引入的一项内存相关的优化。

The dict type has been reimplemented to use a more compact representation based on a proposal by Raymond Hettinger and similar to the PyPy dict implementation. This resulted in dictionaries using 20% to 25% less memory when compared to Python 3.5.

字典的本质是哈希表。Python 3.6 以前的字典实现，就是普通的扁平哈希表。采用伪随机数探测法（一种循环形式的线性探测）处理冲突。

原先是字典结构大致是这样的。

struct dict {
   int size;       // 字典的长度
   int capacity;   // 字典的容量
   dict_entry* entries;   // 扁平哈希表，也就是包含键值对的数组
}

struct dict_entry {
   PyObject* key;       // 键
   PyObject* value;     // 值
}

假设有一个长度为 3 的字典，其容量为 8，

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}

那么他在内存中的表示是这样的。

    entries = [['--', '--'],
               ['barry', 'green'],
               ['--', '--'],
               ['--', '--'],
               ['--', '--'],
               ['timmy', 'red'],
               ['--', '--'],
               ['guido', 'blue']]

entries是一个长度为 8 的数组，键经过哈希运算后被映射到某个下标进行存储，可以看出，字典映射的下标顺序是不确定的，不一定与字典的构造插入顺序相同。

Python 3.6 采用新的数据结构重新实现了字典。

struct dict {
    int count;
    int capacity;
    int* indices;        // 索引数组
    dict_entry* entries; // 键值对
}

struct dict_entry {
    PyObject *key;
    PyObject *value;
}

那么上述字典在内存中的排布方式就变成了如下。

    indices =  [NULL, 1, NULL, NULL, NULL, 0, NULL, 2]
    entries =  [['timmy', 'red'],
                ['barry', 'green'],
                ['guido', 'blue'],
                ['--', '--']]

可以看出，新的实现通过一个额外的indices数组来处理哈希映射，而该数组中的元素指向真正的键值对位置。如此一来，哈希表中的空位就移动到了轻量级的indices数组中，因而在一定程度上节省了内存。

当字典插入新键时，在entries表的末尾构造键值对结构，并在indices数组中找到合适的位置指向它。 此时，entries表就自动对应了键的插入顺序。

这一操作的主要结果是节省了内存，时间性能应该基本不变，理论上看并没有付出「代价」。

在具体实现时，对entries的处理也存在大量细节。为了支持新键的插入，entries数组仍需要预留一定的空间；当删除键时，若对entries进行朴素的数组删除，需要移动元素，则复杂度会达到

。实际采用的是标记删除（即所谓的伪删除），当标记数量达到一定阈值时，再执行一次「压缩」操作。

第二种实现

我自己的开源解释器 pocketpy 从v1.0.9版本开始，实现了dict保持插入顺序的特性。

因为上述方法的实现和调优较为复杂，并不容易达到理论的时空复杂度，pocketpy 采用了另一种数组拟链的思路来实现相同的效果。具体来说，将每个dict_entry视为一个双向链表的节点，增加prev和next字段来保存链表的邻居节点，并在dict结构中存储头节点。

这样字典里面就集成了一个双向链表，结构如下：

struct dict {
    int count;
    int capacity;
    dict_entry* entries; // 键值对
    int head;  // 头节点
}

struct dict_entry {
    PyObject *key;
    PyObject *value;
    int next;       // 下一个节点
    int prev;       // 前一个节点
}

内存布局是这样的

    entries = [['--', '--'],
           ┎--['barry', 'green', 7, 1], <---┑
           ┃  ['--', '--'],                 ┃
           ┃  ['--', '--'],                 ┃
           ┃  ['--', '--'],                 ┃
           ┃  ['timmy', 'red', 1, -1], -----┛
           ┃  ['--', '--'],
           ┗->['guido', 'blue', -1, 1]]

通过内置链表的指引，实现了插入顺序的保持。在时间性能方面，和原先的字典区别不大。插入和删除时需要额外进行一次链表的插入和删除，这两个操作均是

复杂度的。查询复杂度则无影响，因为查询不涉及操作链表。

源码 实现参考 pocketpy/dict.h#L34

保序的字典是一种LRU缓存

语言支持保序的字典有非常多的好处，例如，序列化和反序列化JSON得到的结果总是一样的。以字典形式向控制台输出信息时，不会莫名的变乱。当然，有一点好处可能不那么显而易见，一个保序的字典实质上就是一种LRU缓存。

让我们回顾一下什么是LRU缓存。LRU (最近最少使用) 缓存是一种键值对结构，当缓存容量不足时，LRU算法淘汰掉最久未使用的关键字，并替换为新关键字。

由于字典现在是保序的，在保序字典内置的双向链表中，尾节点就是最新插入的数据，而头节点则是最久未用的数据。因此，稍加修改就可以作为LRU缓存来使用了。这一特性在 Python 3.7 之后已成为标准，了解之后可以简化许多算法的实现。

力扣leetcode.cn/problems/lru-cache/

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}

    def move_to_end(self, key):
        val = self.cache[key]
        del self.cache[key]
        self.cache[key] = val

    def remove_first(self):
        first_key = next(iter(self.cache.keys()))
        del self.cache[first_key]

    def get(self, key: int) -> int:
        val = self.cache.get(key, -1)
        if val != -1:
            self.move_to_end(key)
        return val

    def put(self, key: int, value: int) -> None:
        self.cache[key] = value
        self.move_to_end(key)
        while(len(self.cache) > self.capacity):
            self.remove_first()

总的来说，两种实现都没有付出明显的性能代价。