Python 之 dict 底层实现

Dictionary vs OrderedDict

在 3.6 版本之前，Python Dict 底层在初始创建的时候采用的是 indice 和存储合并在一个二维数组当中。Dict 采用哈希表原理，key 作为取值对象，进行 hash(key) 操作，得到哈希值，然后用进行 值%字典容量 得到要插入的位置。

my_dict = {}
my_dict['age'] = 26
my_dict['salary'] = 999999

"""
# Dictionary结构
[
    [-4234469173262486640, '指向salary的指针', '指向999999的指针'],
    [1545085610920597121, '执行age的指针', '指向26的指针'],
    [---, ---, ---],
    [---, ---, ---],
    [---, ---, ---],
    [1278649844881305901, '指向name的指针', '指向kingname的指针'],
    [---, ---, ---],
    [---, ---, ---]
]
"""

取值和存放都是先 hash 然后取模，然后直接访问这个二位数组。当你要循环遍历字典的 Key 的时候，Python 底层会遍历这个二维数组，如果当前行有数据，那么就返回 Key 指针对应的内存里面的值。如果当前行没有数据，那么就跳过。所以总是会遍历整个二位数组的每一行。

每一行有三列，每一列占用8byte的内存空间，所以每一行会占用24byte的内存空间。由于Hash值取余数以后，余数可大可小，所以字典的Key并不是按照插入的顺序存放的

注意，这里我略了与本文没有太大关系的两个点：

1. 哈希冲突解决方案：开放寻址，当两个不同的Key，经过Hash以后，再对8取余数，可能余数会相同。此时Python为了不覆盖之前已有的值，就会使用开放寻址技术重新寻找一个新的位置存放这个新的键值对。
2. 当字典的键值对数量超过当前数组长度的2/3时，数组会进行扩容，8行变成16行，16行变成32行。长度变了以后，原来的余数位置也会发生变化，此时就需要移动原来位置的数据，导致插入效率变低。

在版本3.6之后，字典的底层数据结构发生了变化，现在当你初始化一个空的字典以后，它在底层是这样的：

my_dict = {}
my_dict['address'] = 'xxx'
my_dict['salary'] = 999999


## 此时的内存示意图
indices = [1, 0, None, None, None, None, 2, None]

entries = [
    [-5954193068542476671, '指向name的指针', '执行kingname的指针'],
    [9043074951938101872, '指向address的指针','指向xxx的指针'],
    [7324055671294268046, '指向salary的指针', '指向999999的指针']
]

实际数据存储和索引进行分开存放，indices是数据存放在二维数组的位置，其他内容保持不变。这样就保证了字典在添加新的键值对的时候是按照顺序进行依次存放的。当去读取字典内容的时候

hash('salary')      # 7324055671294268046
hash('salary') % 8  # 6

然后就去读 indices 下标为6的这个值。这个值为2. 然后再去读 entries 里面下标为2的这一行的数据，也就是 salary 对应的数据了。

按照新的结构，当要插入新的数据的时候始终是往 entries 的后面添加数据，这样就能保证插入的顺序。

当我们要遍历字典的 Keys 和 Values 的时候，直接遍历 entries 即可，里面每一行都是有用的数据，不存在跳过的情况，减少了遍历的个数。

老的方式，当二维数组有8行的时候，即使有效数据只有3行，但它占用的内存空间还是 8 * 24 = 192 byte。但使用新的方式，如果只有三行有效数据，那么 entries 也就只有3行，占用的空间为3 * 24 =72 byte，而indices由于只是一个一维的数组，只占用 8 byte，所以一共占用 80 byte。内存占用只有原来的41%。

时间复杂度

字典的查询、添加、删除的平均时间复杂度都是O(1)。

哈希算法不可避免的问题就是hash冲突，Python字典发生哈希冲突时，会向下寻找空余位置，直到找到位置。如果在计算key的hash值时，如果一直找不到空余位置，则字典的时间复杂度就变成了O(n)了，所以Python的哈希算法就显得非常重要了。Python字典的哈希算法，会尽量保证哈希值计算出的index是平均分布且每一个值之间有剩余位置。

Referenct

• https://juejin.cn/post/7005897386732208136