The Mighty Dictionary in Python

The Mighty Dictionary是PyCon 2010上Brandon Craig Rhodes报告的题目。借用他的题目,本文整理了Python内建类型dict的一些所谓Mighty的知识。


故事起源于the order of keys in a dict

d = {'a': 1, 'b': 2, 'c': 4}
print d.keys()  #['a', 'c', 'b']
class A(object):
    pass
d = {
    5: 'this is a number',
    'astr': 'this is a string',
    A: 'this is a class'
}
print d.keys() #[<class '__main__.A'>, 'astr', 5]

dict是一种无序的关联数组,当调用keys这个method的时候,每一个key的输出顺序与定义时的顺序或者插入时的顺序都无关。


Python内部具体是如何实现dict的?【开始复习数据结构-.-】

Python用哈希表来实现O(1)的dict查找。(回顾一下C++ STL中的map类型,它的内建数据结构是rbtree,log(n)的时间复杂度)

--- hash table ---
index |  hash(key) | key  | value
000   |            |      |
001   | ..0010 001 | test |  9
010   |            |      |
011   |            |      |
...

Python中dict的key可以是很广泛的类型(任何实现了__hash__函数的not mutable的object)。
对于一个key,Python会调用它的hash方法去生成index。对于hash method,我们可以这么做:

for k in [5, 'a', 'b']:
    print hash(k),
#5 -468864544 -340864157

大部分的类型你都可以调用hash方法去生成一个整型的值,当然如果你试图去hash一个list,他会告诉你TypeError: unhashable type(list是mutable的类型)。
对于hash table来说,Python使用每个key哈希值的后n个bits去构造index(也就是常说的mod操作)。

现在我们可以解释那个the order of keys in a dict的问题了,没错,实际输出的顺序其实就是hash table中key的顺序。所以在大部分情况下,key的输出顺序和插入顺序是不同的。

谈到hash table,就会讨论index碰撞的问题,传统的index碰撞有两种办法:开放地址法和链地址法。(默默打开数据结构的书复习一下=。=)

Python选用了第一种实现,当冲突出现的时候,会进行多次的探测直到找到一个未被使用的index。(Python没有选择链地址法是因为这个方法需要经常malloc,在时间和空间两个方面,Python选择了牺牲空间换取时间)

对于开放地址的探测方法,最普通的就是线性探测法。线性探测法的逻辑是对于index i,不断的探测i+1、i+2、…直到找到不冲突的下标。该探测法有很多问题,比如在有冲突的时候容易产生大量连续的区域,当a、b、c三个key都映射到i的时候,a在i,b在i+1,c就一定要找三次跳过i和i+1才行。一般情况下,都会在线性的基础上增加一些随机性比如采用i+k的算法,k是一个关于key的独立的函数F。这样F(b)和F(c)不会一样,b和c就都只需要找两次就可以了。

在探测算法上,Python使用了如下的递归方法:

# for the key=k, perturb被初始化为hash(k),也就是j的初值
j = (5*j) + 1 + perturb;
perturb >>= PERTURB_SHIFT;
use j % 2**i as the next table index;

其中i代表hash表的规模,2**i就是hash表的大小。perturb被初始化为key的hash值。PERTURB_SHIFT是一个常量,在python内部被设置为5。每一次探测中,通过旧的j和perturb生成新的j,然后对perturb进行移位操作。

之所以采用这个公式,笼统来说就是在计算简单的基础上,充分的利用的hash(k)包含的所有独立信息。对于这一点,源码里面有一些相关的注释可以参考。

现在,我们又可以获得一个新的结论:因为冲突的存在,Python dict输出key的顺序与插入顺序是相关的,因此在任何时候我们也不能对key的顺序作任何的假设。

对于查找(lookup)操作,我们只需要执行同样的算法,计算出index,然后去判断key是否相等,相等则反回value的值。如果不相等,我们迭代一次index,算出新的下标,继续判断,一直迭代下去直到找到相等的key。如果我们最终找到一个index,但是这里是空的,即没有保存任何值,我们就可以提前结束这次lookup,表示查找失败。

所以事实是,每次lookup的操作时间不一定是相等的,但是依然O(1)。

下面的问题是:当你删除一个key的时候,你不能直接删除它,而是需要留下dummy key(比如一个是否deleted的标志位)。

这样做的原因是显而易见的,如果你删除了某个key,所有与它冲突而探测新下标的key就都找不到了。

现在我们解决了dict增删改查的问题,开始思考,当一个dict的key越来越多的时候,冲突会越来越频繁的发生,甚至hashtable的大小不够存放所有的key了,所以这里就涉及到了resize的问题。(就像C++ STL的vector一样嘛)

Python实现的规则是:
初始情况下,dict的hash table大小为8(PyDict_MINSIZE常量),当dict的hash table使用率达到2/3的时候,就会resize以保证较少的index碰撞。当key的数量小于50k,size*4;当key的数量大于50k,size*2。需要注意的是每次resize的时候,所有的key会被重新插入(从上文的探测算法角度来说,i改变了,index需要重新计算),所以key的顺序很有可能又改变了。

看一段新的代码:

d = {'a': 1, 'b': 2, 'c': 4}
for k in d.iteritems():
    d['k'] = 9
#RuntimeError: dictionary changed size during iteration

这是一个Python新手的常见错误,我们不能在遍历dict的时候插入新的key(我们可以修改key的value)。原因经过上面的解释就很清楚了,insert操作可能会修改key在hash table中的分布,也就是其遍历顺序。

我们对以上内容给出一些结论

  • dict key的顺序不可依赖,如果有需求请参考OrderedDict
  • 遍历key的时候不可插入
  • dict的key不能是mutable的,且必须可以被hash
  • dict牺牲空间来换取时间(hash table其实有超多空的地方),在某些memory严格的情况下也许你可以用namedtuple

下面讲一讲hash method

这一段从做实验开始,运行代码:

class A(object): pass
class B(object): pass
class C(object): pass
class D(object): pass
class E(object): pass
class F(object): pass
class G(object): pass
class H(object): pass

class Foo(object):
    d = {A: 1, B: 2, C: 3, D: 4,
         E: 5, F: 6, G: 7, H: 8}

    def bar(self):
        for key, value in self.d.iteritems():
            print key.__name__,

f = Foo()
f.bar()
#import time
#time.sleep(0)

然后把最后两行的注释去掉,再次运行。奇妙的事情出现了,输出不一样了。

我们之前了解了dict的实现,所以现在可以断定,加了代码以后,d的key的hash值不一样了。的确hash值不同了,但是不是说hash值是唯一的么?

事实是对于自己创建的class A,它的默认hash方法是id(A)。查一下id方法是什么,其实就是返回A本身的memory地址。我加了两行代码导致class存放的地址改变了?很有可能!

id(object)
Return the “identity” of an object. This is an integer (or long integer) which is guaranteed to be unique and constant for this object during its lifetime. Two objects with non-overlapping lifetimes may have the same id() value.

CPython implementation detail: This is the address of the object in memory.

做完了实验陈列一些Python事实:

  • 对于5, 5.0, complex(5, 0),他们的hash值是一样的
  • 用户自定义的类默认hash方法是返回它的id方法的值
  • 你可以自己自定义__hash__方法,但是同时你也要定义__cmp__和__eq__方法,记住不要使用复杂度太高的hash方法

参考文档


结尾

贴一下文章开头说的PyCon演讲的视频链接
这个英文blog基于CPython对dict进行了较为详细的源码级别的分析

最后翻译一下题目:酷炫狂拽的派森字典

Tags : ,

One thought on “The Mighty Dictionary in Python”

  1. 拖了好久终于看了这篇…顺便好好复习了一下 hash table,点个赞;)
    讲 hash method 的实验里,结果和最后两行代码注释不注释没关吧。同样的代码每次跑都会不一样啊应该。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Click the right image To submit your comment: