Middle Earth

Python dict 的实现

  • Python (cpython) 的 dict 是用哈希表实现的。

  • 碰撞的处理方法是 open addressing，因为 chaining 的 overhead 太高 (哈希表里记录的只是哈希值和相关的 object 的地址，不记录实际 object，所以如果用链表来做 chaining 的话，光 next 指针就占去了很多空间)。(不知道我理解得对不对)。

Open addressing is preferred over chaining since the link overhead for
chaining would be substantial (100% with typical malloc overhead).

  • 一般的哈希表在选择哈希函数时，都希望产生的哈希值尽量随机，但是 python 的哈希函数不是这样的。dict 和其它一些地方使用的哈希函数其实就是 python 的内置函数 hash ，它的返回值非常的不随机。比如对于最重要的两种 key，整数和字符串，整数的哈希值就是它本身，而字符串的哈希值计算也很简单。且看
1
2
3
4

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

这样的好处是如果 key 是连续的整数或者字符串，几乎不会有碰撞。而且哈希值基本都是连续的，效率也比较高。

  • 有时候，好处也是坏处。这样做的坏处是，表里会有数据连续地存在一块，而不是相互散开 (这正是哈希表，也称散列表的意义所在啊)，也就是，一旦有碰撞发生，用线性探测的方法来寻找可用位置是绝对不可行的。python 用的探测方法是一种 quadratic probing，保证不会受到连成块的数据的影响。

  • 既然是使用 open addressing，也就是说整个哈希表存储在一段连续的内存中，或者说是一个数组 (dict 是用 C 实现的)。这意味着，当数组快满时 (比如超过 2/3)，需要把数组扩大 (resize)。

  • python 保证在修改元素的时候不会发生 resize，也就是保证了可以一边遍历 dict，一边修改元素。但是其它的操作就不一定了，所以会有这样的错误:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

>>> a = {1:2, 3:4}
>>> for k in a:
...  del a[k]
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

>>> a = {1:2, 3:4}
>>> for k in a:
...  a[2*k]=1
...
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
RuntimeError: dictionary changed size during iteration

参考

  • http://www.laurentluce.com/posts/python-dictionary-implementation/

  • http://hg.python.org/cpython/file/tip/Objects/dictobject.c

  • http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

Comments