相信dict对于大部分人来说都很熟悉,所以本文不会介绍其相关用法。试想如果让你实现Python中的dict,你会准备怎么做?就此打住,思考两分钟。

你理应设计一个结构来存储dict,实现插入删除以及修改等必要操作,同时你该考虑如何实现遍历字典,判断某个键值是否存在等功能;接着,你会想如何比较两个字典的关系,尝试合并字典或者从其他数据结构转换成字典结构;进一步地,如果你能注意到性能问题,发现dict的很多操作都应该是O(1)复杂度,你会想到hash table… 如果你能一直往下想并找到解决思路,那你比作者的能力强多了,可以不用看了>,<

Hash Table

但我们决定先考虑性能问题,我们先分配足够大的数组空间,对字典的key做哈希,用哈希值作为数组下标进行存储和操作,显然这样的结构支持O(1)复杂度。如下所示:

1
2
3
4
5
6
7
# 原始字典, 假设这里所有Value都是int
dict_ = {1: 1, 'a': 2}

# 字典存储方式, 此处MAX_INT表示无穷大的空间
int dict__[MAX_INT];
dict__[hash(1)] = 1; # dict__[1] = 1
dict__[hash('a')] = 2; # dict__[12416037344] = 2

但无穷大的空间是不现实的,所以我们必须对哈希值做些处理,如对数组长度取模。假设我们数组长度为8,则上面的示例就变成了:

1
2
3
4
DICT_LEN = 8
int dict__[DICT_LEN];
dict__[hash(1) % DICT_LEN] = 1; # dict__[1] = 1
dict__[hash('a') % DICT_LEN] = 2; # dict__[0] = 2

对8取模相当于取了哈希值的低三位,所以在python中规定存储字典的数组长度必须为2的整数次幂,这样取模就变成简单操作了。既然低位的哈希值这么重要,所以一个理想的hash函数应该能在低位体现这些不同。如下:

1
2
3
4
>>> map(lambda x: hash(x) & 7, [1,2,3,4]))
[0, 1, 2, 3]
>>> map(lambda x: hash(x) & 7, ['a','b','c','d']))
[0, 3, 2, 5]

但是毕竟哈希值范围比数组长度大太多,当键值对增加时,冲突是不可避免的;另一方面,构建特殊例子也能使上面的策略严重冲突,如:

1
2
>>> map(lambda x: hash(x) & 7, [i << 3 for i in range(8)]))
[0, 0, 0, 0, 0, 0, 0, 0]

key冲突时,应该在数组中寻找其他位置,最简单的方案是累加遍历的方式,如我们hash('a') & 7 == hash('i') & 7 == 0,即ai在数组0位置冲突了,那么我们就要尝试1位置,如果还是冲突,则尝试2位置,以此类推。但是这种方案不好,因为hash函数本身就具有连续累加的特性,这样会让冲突解决方案效率低下(想想为啥)。python中使用如下随机遍历的方法:

1
2
3
4
5
6
7
8
9
10
# j = ((5 * j) + 1) mod 2**i
# 在我们例子里,2**i 就是8
>>> f = lambda j: ((5 * j) + 1) % 8
>>> j_list = []
>>> for i in range(9):
... j_list.append(j)
... j = f(j)
...
>>> j_list
[0, 1, 6, 7, 4, 5, 2, 3, 0]

上面的例子说明在数组长度为8时,冲突解决顺序。但是我们可以看到该解决方案有个问题,探针的起点是第一次冲突时数组的下标。而这个下标是取自哈希值的低位而来的,换句话说哈希值的高位信息丢失了,更高效的探针顺序还应该考虑高位信息,改变探针顺序如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
# j = (5 * j) + 1 + perturb
# perturb >>= PERTURB_SHIFT
# use j % 2**i as the next table index

# perturb默认为原来的Hash值, 我们以上面的a和i为例子
>>> j, perturb, j_list = 0, hash('i'), []
>>> for i in range(14):
... j_list.append(j % 8)
... j = f(j, perturb)
... perturb >>= 5 # PERTURB_SHIFT = 5
...
>>> j_list
[[0, 1, 5, 1, 3, 1, 6, 3, 0, 1, 6, 7, 4, 5]

可以发现,一开始考虑高位信息时,遍历顺序有跳变,当perturb不断右移位后越来越小变成0后,就会退化成上面一开始的遍历顺序,即挨个遍历。由此可见,perturb的值大小影响了该退化的速度,过大则退化过快,达不到我们利用高位信息的目的;太小,在极端情况下会浪费时间,因为挨个遍历是能保证一定找到目标的。python源码选定值为5。

至此,我们把字典按照key值散列到数组中,当发生冲突时可以根据规定好的探针顺序查找下一个可用下标。更进一步,我们可以优化探针顺序计算过程(如j << 2 + j1 + perturb同时计算)。

字典最小单位:PyDictEntry

上面为了描述Hash Table探针顺序做了很多简单的假设,如规定Value一定是int类型,也没有在数组中存储key值。这一章我们看dict真正的结构。dict最小存储单位是PyDictEntry,该结构在include/dictobject.h定义。

形象起见,我们可以简单对第一章的例子做如下转换(作者一点都不想在文章里贴源码,不过该结构实在非常重要,破例一次):

1
2
3
4
5
6
7
8
typedef struct {
Py_ssize_t me_hash; # 哈希值
PyObject *me_key; # key值
PyObject *me_value; # value值
} PyDictEntry;

# int dict__[DICT_LEN];
PyDictEntry dict__[DICT_LEN]

dict在初始化后会分配固定内存给PyDictEntry数组,数组长度是不会经常变化的,因为我们在散列过程中用到了该长度。当所给数组容纳不了所有dict元素时,必须要对该长度进行拓展,上面提到我们要求数组长度必须是2的幂次方,所以只能Double或者Quadruple增长。考虑到不应该让冲突频繁发生,所以不能等到数组容纳不了时才拓展,应该选取一个更合适的临界值。python中认为数组被使用的数量大于数组长度的三分之二时才应该拓展。

相同地,dict元素被大量删除时,是否应该缩小呢?讲道理是要的,但这样可能会引起在临界值附近进行添加或删除元素时,字典跟着频繁扩大缩小。因此在python中,只有添加新元素时才会对数组大小进行改变。

此时引出另外一个概念,即PyDictEntry有三种状态,Unused,ActiveDummy。字典被初始化时,里面的所有数组元素都是Unused状态,一旦有键值对占用了PyDictEntry则变成了Active状态,如果一个键值对被删除,则会从Active转换成Dummy状态;而如果又有新元素进来,也可能会导致Dummy状态转换成Active状态。这一段说起来有点绕。上一段提到数组扩展的临界值,提到了数组被使用的数量,即DummyActive状态的元素之和,从这里我们也可以看出,元素删除并不会导致该值变化(只是从Active变成Dummy而已),对同一个元素在临界值附近频繁删除插入也不会引起数组变化(同理)。

是否有这么个疑问,如果dict元素在删除时不会引起数组变化,那么该数组是否只会慢慢增加?不会的。dict很多元素被删除之后,如果某个元素的插入引起临界反应,这个时候会创建新的数组,并只把原来字典中Active状态的元素拷贝过去。因此新数组的长度只与dict中真正存在的元素数量相关,此时有可能会引起数组变小。

显然的,这种数组扩大的过程在dict比较小的时候发生的概率会很大,比如2扩展为4,4扩展为8等等。因此python在数组初始化的时候会预先创建一个大小为8的数组用来存储,临界值被打破时,则放弃使用该数组,并向系统请求新数组。

到这里为止,我们可以用第一章提到的探针思路构建一个方法lookdict,用来查找在dict中指定key所对应的PyDictEntry,并执行一些基本的操作,如插入(直接对PyDictEntrykeyvalue复制即可),删除(修改PyDictEntryDummy状态),修改(修改PyDictEntry中的value)等。

重要的工具:遍历

在文章一开始我们自己土想dict应该具有的功能时,提过合并字典这样的操作。当要求ab字典进行合并时,我们对b进行遍历,然后根据是否override,把元素挨个插入到a字典中;再比如要求我们输出字典所有的keys或者values时,只需要对dict进行遍历,输出所有PyDictEntrykey或者value就可以。换句话说,只要我们知道如何遍历一个字典,很多操作我们都可以“自己实现”。

遍历在源码很多地方都会涉及到,比如打印一个字典时,遍历keys或者values时,虽然有一些小区别,但是总体思路是一样的。因此我们不举例子,直说思路。因为本身存储结构已经是数组,只需要从头到尾遍历,过滤UnusedDummy节点即可。

借此说另一个问题,即平时我们在遍历数组操作时为什么不能删除元素或者增加元素,只能修改元素呢?根据上面的分析,增加元素时可能会引起数组长度变化,接着会导致整个数组中Active节点被拷贝到新数组中去,新节点的下标和之前的可能已经不一样了,因此会导致遍历出错;但删除元素不是不会改变数组大小么?

不负责任的说,是因为有下面这段检查:

1
2
3
4
5
6
if (di->di_used != d->ma_used) {
PyErr_SetString(PyExc_RuntimeError,
"dictionary changed size during iteration");
di->di_used = -1;
return Null;
}

在执行遍历操作时(itervalues, iterkeys等)时,python会初始化一个迭代对象,上面代码中的di,并进行相关赋值操作,当执行删除或者添加元素操作时,会引起原数组dma_used变化,而迭代对象中的di_used并不会随之改变,因此会报错。但显然这个答案不好。

作者也不知道,留作思考题吧…