深入Python字典的内部实现

字典是经由过程键(key)索引的，是以，字典也可视作彼此接洽关系的两个数组。下面我们测验测验向字典中添加3个键/值(key/value)对：

>>> d = {'a': 1, 'b': 2} 
 
>>> d['c'] = 3 
 
>>> d 
 
{'a': 1, 'b': 2, 'c': 3}

这些值可经由过程如下办法拜访：

>>> d['a'] 
 
1 
 
>>> d['b'] 
 
2 
 
>>> d['c'] 
 
3 
 
>>> d['d'] 
 
Traceback (most recent call last): 
 
  File "<stdin>", line 1, in <module> 
 
KeyError: 'd'

因为不存在 'd' 这个键，所以激发了KeyError异常。

哈希表(Hash tables)

在Python中，字典是经由过程哈希表实现的。也就是说，字典是一个数组，而数组的索引是键经由哈希函数处理后获得的。哈希函数的目标是使键平均地分布在数组中。因为不合的键可能具有雷同的哈希值，即可能出现冲突，高等的哈希函数可以或许使冲突数量最小化。Python中并不包含如许高等的哈希函数，几个重要(用于处理字符串和整数)的哈希函数平日情况下均是惯例的类型：

>>> map(hash, (0, 1, 2, 3)) 
 
[0, 1, 2, 3] 
 
>>> map(hash, ("namea", "nameb", "namec", "named")) 
 
[-1658398457, -1658398460, -1658398459, -1658398462]

如不雅在Python中运行 hash('a') ，后台将履行 string_hash()函数，然后返回 12416037344 (这里我们假设采取的是64位的平台)。

如不雅用长度为 x 的数组存储键/值对，则我们须要用值为 x-1 的掩码计算槽(slot，存储键/值对的单位)在数组中的索引。这可使计算索引的过程变得异常敏捷。字典构造调剂长度的机制(以下会具体介绍)会使找到空槽的概率很高，也就意味着在多半情况下只须要进内行单的计算。假如字典中所用数组的长度是 8 ，那么键'a'的索引为：hash('a') & 7 = 0，同理'b'的索引为 3 ,'c'的索引为 2 , 而'z'的索引与'b'雷同，也为 3 ，这就出现了冲突。

可以看出，Python的哈希函数在键彼此持续的时刻表示得很幻想，这主如果推敲到平日情况下处理的都是这类情势的数据。然而，一旦我们添加了键'z'就会出现冲突，因为这个键值并不邻接其他键，且相距较远。

当然，我们也可以用索引为键的哈希值的链表来存储键/值对，但会增长查找元素的时光，时光复杂度也不再是 O(1) 了。下一节将介绍Python的字典解决冲突所采取的办法。

下面我们结合例子来看一看 Python 内部代码。

开放寻址法( Open addressing )

开放寻址法是一种用探陈手段处理冲突的办法。在上述键'z'冲突的例子中，索引 3 在数组中已经被占用了，因而须要探寻一个当前未被应用的索引。增长和搜寻键/值对须要的时光均为 O(1)。

搜寻余暇槽用到了一个二次探测序列(quadratic probing sequence)，其代码如下：

轮回地5*j+1可以快速放大年夜不影响初始索引的哈希值二进位的渺小差别。变量perturb可使其他二进位也赓续变更。

出于好奇，我们来看一看当数组长度为 32 时的探测序列，j = 3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2…

关于探测序列的更多介绍可以参阅dictobject.c的源码。文件的开首包含了对探测机理的具体介绍。

下面为字典对应的数据构造。个中，ma_fill为晃荡槽以及哑槽(dummy slot)的总数。当一个晃荡槽中的键/值对被删除后，该槽则被标记为哑槽。ma_used为晃荡槽的总数。ma_mask值为数组的长度减 1 ，用于计算槽的索引。ma_table为数组本身，ma_smalltable为长度为 8 的初始数组。

1/4 1 2 3 4 下一页尾页

　　推荐阅读

　　如何算出精确的PUE？连续监测才是王道

PUE申报精度电力应用效力(PUE)是一个评价数据中间能源效力的通用指标，是数据中间消费的所有能源竽暌闺IT负载应用的能源之比。PUE能赞助数据中间经理有效地治理能耗设备。计算某数据中间举措措施的PUE值有很多原因，>>>详细阅读

本文标题：深入Python字典的内部实现

地址：http://www.17bianji.com/lsqh/35357.html

1/2 1