---
url: https://www.zhihu.com/question/614136694/answer/3141438097
fid: 20241123-082316
title: 为了使字典的键有序, python付出了怎样的性能代价? - 最大的梦想家的回答 - 知乎
keywords: dict, dict order, ordered dict
---


(20241123-082316)=
# 如何高效实现有序Dict?
From: [为了使字典的键有序, python付出了怎样的性能代价? - 最大的梦想家的回答 - 知乎](https://www.zhihu.com/question/614136694/answer/3141438097)

2024-11-23



## 有序字典的官方实现

Python 的字典有序来自于 [Python 3.6](https://zhida.zhihu.com/search?content_id=601255824&content_type=Answer&match_order=1&q=Python+3.6&zhida_source=entity)  中，引入的一项内存相关的优化。

> The [dict](https://docs.python.org/3/library/stdtypes.html#typesmapping) type has been reimplemented to use a [more compact representation](https://docs.python.org/3/whatsnew/3.6.html#whatsnew36-compactdict) based on [a proposal by Raymond Hettinger](https://mail.python.org/pipermail/python-dev/2012-December/123028.html) and similar to the [PyPy dict implementation](https://morepypy.blogspot.com/2015/01/faster-more-memory-efficient-and-more.html). This resulted in dictionaries using 20% to 25% less memory when compared to Python 3.5.

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

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

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

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

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

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

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

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

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

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

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

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

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

```text
    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](https://github.com/blueloveTH/pocketpy) 从`v1.0.9`版本开始，实现了`dict`保持插入顺序的特性。

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

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

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

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

内存布局是这样的

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

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

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

[源码 实现参考 pocketpy/dict.h#L34](https://github.com/blueloveTH/pocketpy/blob/main/include/pocketpy/dict.h#L34)

### 保序的字典是一种LRU缓存

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

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

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

[力扣leetcode.cn/problems/lru-cache/](https://leetcode.cn/problems/lru-cache/)

```python
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()
```

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