python源码学习(十一)——dict

By | 2014/07/12

在C++的STL中,map是一种关联容器,采用红黑树的方式,其搜索效率大约为O(logN),以2为底。但是在python中,dict采用的则是散列表,有名哈希表,虽然python中的dict也是关联容器,其搜索效率为O(1)。散列表有一个索引,当散列表的装载率为2/3以上时,散列冲突的概率非常大,因此在python中,使用开链法进行探测序列,防止出现散列冲突。
我们把关联容器的一对键值成为entry,python中一个entry的定义如下:

typedef struct {
    /* Cached hash code of me_key.  Note that hash codes are C longs.
     * We have to use Py_ssize_t instead because dict_popitem() abuses
     * me_hash to hold a search finger.
     */
    Py_ssize_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictEntry;

从代码中可以看出,PyDictObject中其实存放的就是PyObject*的指针,entry三种状态,Unused态,Active态,Dummy态。当me_key和me_value都为NULL时,处于Unused态,键值存在时为Active态,键值删除时为处于Dummy态,如下图所示:
Screen Shot 2014-07-12 at 上午11.21.29
关联容器的实现如下:
当容器中元素不超过8个时,不会在开辟空间,反之则会像list那样在开辟另外的内存空间。具体如下图所示:
Screen Shot 2014-07-12 at 下午12.03.18
PyDictObject和其他的python对象一样,都有一个对象缓冲池,这一点,dict和list非常像,都是当一个容器的元素全部清空之后只是将ma_table指针所指的内存释放掉,并不是将整个容器对象释放掉。
dict的操作中,无论是插入还是删除,内存都会发生位置变化,这个和list略有一点点不同。
OK,讲完了。

发表评论

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.