Python字典核心底层原理

字典核心底层原理（是很重要的）

一.存储键值对过程

字典对象的核心是散列表，散列表是一个稀疏数组(总是有空不元素的数组)，数组的每一个单元叫做bucket（或叫桶.表元），每一个bucket有两部分，一个是键对象的引用，一个是值对象的引用，

由于，所有bucket结构和大小一致，可以通过偏移量来读取指定bucket。

Python字典核心底层原理

将一个键值对放在字典的底层过程：

>>>a={}

>>>a['name']='tianya'

假设字典a对象创建完成后，数组长度为8：

Python字典核心底层原理

要把“name”=“tianya”，这个键值对放到字典对象a中，首先第一步需要计算键“name”的散列值，python中可以通过hash()来计算。

>>>bin(hash('name'))

'0b11111111101110101000001110001111101010110100011000011111110'

由于数组长度为8，可以拿计算出的散列值得最右边3位数作为偏移量，即"110",十进制数字是 6，我们查看偏移量6，对应的bucket是否为空，如果为空，则将键值对放进去，如果不为空，则依次取右边3位作为偏移量，即“111”，十进制是数字7，再查看偏移量为7的bucket是否为空，如果为空，则放进去，直到找到为空的bucket将键值对放进去。

流程图如下：

Python字典核心底层原理

扩容：

Python会根据散列值列表的拥挤程度扩容，“扩容”指的是创造更大数组，将原有内容拷贝到新的数组中。

接近2/3时，数组就会扩容。

二.根据键查找“键值对”的底层过程

理解了，一个键值对是如何存储到数组中的，根据键对象取到值对象，理解起来就简单多了。

>>>a.get('name')

tianya

当调用a.get('name')，就是根据键“name”查找到“键值对”，从而找到值对象“tianya”

第一步，仍然要计算“name”对象的散列值：

>>>bin(hash('name')

'0b11111111101110101000001110001111101010110100011000011111110'

和存储的底层算法一致，也是依次取散列值的不同位置的数字。假设数组长度为8.我们可以拿计算出的散列值的最后边3位数字做完偏移量，即“110”，十进制数字是6，查看偏移量6，对应的bucket是否为空，如果为空，则返回None。如果不为空，则返回这个bucket的键对象计算对应散列值，和我们的散列值进行比较，如果相等，则将对应“值对象”返回，如果不相等，则再次依次取其他几位数字，重新计算偏移量，依次取完后，仍然没有找到，则返回None，流程如下：

Python字典核心底层原理

用法总结一下：

1.键必须可散列：

1>数字、字符串、元组都是可以散列的

2>自定义对象需要支持下面三点：

1）支持hash()函数

2）支持通过__eq__（）方法检测相等性

3）若a==b为真，则hash(a)==hash(b)也为真

2.字典在内存中开销巨大，典型的空间换时间

3.键查询速度很快

4.往字典里面添加新建可能导致扩容，导致散列表中键的次序发生变化，因此，不要在遍历字典的时候同时进行字典的修改。

Python字典核心底层原理

相关推荐