Python底层是怎么实现字典的？

前言

上次我们分享了列表的底层原理，今天我们继续分享另外一个常用的Python数据结构，字典。字典的键值对，可以让我们可以很轻松的完成数据查询、添加和删除，说到键值对，我又不经意想到了散列表（哈希表）。

今天可以明确的告诉你，字典就是用到了哈希表的思想，全剧终。开玩笑哈，那废话不多说，开整。

哈希表

在说字典的具体实现之前，我们还是简单介绍下哈希表的原理，大可放心，我尽量讲的通俗些。

之前我们介绍过数组，通过索引我们能快速获取元素值。哈希表也是一样，但是数组的索引是0到n-1，但是哈希表是键值对，所以，哈希函数来了。

我们把键通过哈希函数转换为哈希值（这样就可以是个整数），然后将对应的值存在数组中这个哈希值索引的位置上。

dict = {}
dict['name'] = 'lisi'

当然哈希表没有这么简单，还会涉及哈希冲突，扩容等等问题，这里就不过多介绍了。

字典

不会吧，都2021年了，不会还有人说字典是无序的吧。

确实，在python3.6之前，字典是无序的，但是在python3.7开始，字典就有序了，这有序无序，恰恰就说明字典的底层发生了变化，我们来一探究竟。

无序

在python3.6之前，哈希表结构如下所示，每一行存储了哈希值（hash）、键（key）、值（value）3个元素。

table = [
    ['--', '--', '--'],
    [hash, key, value],
    ['--', '--', '--'],
    ['--', '--', '--'],
    [hash, key, value],
]

例如dict['name'] = 'lisi'，假设name计算的hash值为1，则存储如下。

dict = [
    ['--', '--', '--'],
    [1, 'name', 'lisi'],
    ['--', '--', '--'],
    ['--', '--', '--'],
     ['--', '--', '--'],
]

所以我们没办法保证下一个插入的键值对能保证在1的后面，hash值计算出来是多少，就存储在什么位置，没法做到有序，而却这种方法也很容易让哈希表稀疏，占用大量内存。

有序

有序的字典把索引和哈希值、键、值单独分开，如下所示。

indices = [None, None, index,]
table = [
    [hash0, key0, value0],
    [hash1, key1, value1],
    [hash2, key2, value2]
]

所以前面的例子在这里保存就是这样的。

indices = [None, 0, None]
table = [
    [1, 'name', 'lisi'],
]

这样确保了有序。

总结

当然，Python具体用的是什么hash函数，又是怎么解决哈希冲突和扩容的，这些就留给读者了，今天的分享就到这了，我们下期再见~