Python字典的底层实现

Python字典及特性

字典是一种可变、无序容器数据结构。元素以键值对存在，键值唯一。它的特点搜索速度很快：数据量增加10000倍，搜索时间增加不到2倍；当数据量很大的时候，字典的搜索速度要比列表快成百上千倍。

Python字典的实现原理

在Python中，字典是通过散列表（哈希表）实现的。字典也叫哈希数组或关联数组，所以其本质是数组（如下图），每个 bucket 有两部分：一个是键对象的引用，一个是值对象的引用。所有 bucket 结构和大小一致，我们可以通过偏移量来读取指定 bucket。

哈希数组

存储

定义一个字典 dic = {}，假设其哈希数组长度为8。

>>> dic = {}
>>> dic
{}

实现dic的哈希数组
通过哈希函数计算键对象name的哈希值，对数组长度取余hash(hashable)%k，因为哈希值最右3位110为十进制6，则查看数组索引6对应的bucket是否为空，如果为空则将键值对放入，否则（哈希冲突）左移三位即000，查看索引0是否为空，循环直至找到空的bucket。

Python会根据哈希数组的拥挤程度对其扩容。“扩容”指的是:创造更大的数组，这时候会对已经存在的键值对重新进行哈希取余运算保存到其它位置；一般接近 2/3 时，数组就会扩容。扩容后，偏移量的数字个数增加，如数组长度扩容到16时，可以用最右边4位数字作为偏移量。

>>>dic['name'] = '张三'
>>>bin(hash('name'))
'0b101011100000110111101000101010100010011010110010100101001000110' 

读取

>>>dic.get('name')
'张三'

计算键对象name的哈希值，然后比较哈希数组对应索引内的bucket是否为空，为空返回None，否则计算这个bucket的键对象的哈希值，然后与name哈希值比较，相等则返回值对象，否则继续左移计算哈希值。

注意：
1.键必须为可哈希的，如数字、元组、字符串；自定义对象需要满足支持hash、支持通过__eq__()方法检测相等性、若a == b为真，则hash(a) == hash(b)也为真。

Python中所有不可变的内置类型都是可哈希的。
可变类型（如列表，字典和集合）就是不可哈希的，因此不能作为字典的键。

2.字典的内存开销很大，以空间换时间。
3.键查询速度很快，列表查询是按顺序一个个遍历，字典则是一步到位。
4.往字典里面添加新键可能导致扩容，导致哈希数组中键的次序变化。因此，不要在遍历字典的同时进行字典的修改。