PythonTip >> 博文 >> python

python源码剖析笔记---Dict

liushulinle 2014-11-29 15:11:00 点击: 26335 | 收藏


1. Python中的Dict对象和C++及Java中的Map对象不同,Python中Dict对象利用散列表的方法组织,而C++和Java采用红黑树之类的树结构组织。理论上讲,Python的Dict效率比上述两种语言中的Map效率要高,因为散列表的复杂度为O(1),树的复杂度为O(logn)。散列表采用的是开放定址法。

2. 关联容器的entry
一个(键,值)元素对称作一个entry。其定义如下:
typedef struct{
py_ssize_t me_hask;  //保存me_key的hash值,避免每次访问都要重新计算
PyObject *me_key;
PyObject *me_value;
} PyDictEntry;
从代码中可以看到,PyDictObject中存放的其实都是PyObject*,这也是Python中的dict什么都能装得下的原因。

3.PyDictEntry对象有三种状态:Unused,Active和Dummy,每个对象都在这三种状态中 转换。具体定义如下:
Unused态:当一个entry的me_key和me_value都是NULL时,entry处于Unused态。此状态表示该entry并没有存储键值对,而且在此之前也没有存储过。每个entry对象初始化的时候都是这种状态,而且只有在Unused状态是,entry的me_key才为NULL
Active态:当entry中存储了键值对时便转换为该状态。此状态下,me_key和me_value都不为NULL,并且me_key也不能是dummy对象

Dummy态:当entry中的键值对被删除后,entry不能从Active转换为Unused,因为采用开放定址法,该元素连接之后的元素,不能将该元素真正的删除,否则查找时无法找到该元素之后的元素。此时,me_key指向一个dummy对象,me_value = NULL。搜索时,当发现某个entry为Dummy态时,说明该entry无效,但其后的entry可能有效。 状态转换如下:


4.关联容器的实现
dict实际上是entry的集合,总控这些entry对象的PyDictObject对象定义如下:
typedef struct{
Pyobject_HEAD
Py_ssize_t ma_fill;  //元素个数:Active + Dummy
Py_ssize_t ma_used;  //Active
Py_ssize_t ma_mask;   //capacity, 这个只所以取名为mask而不是size的原因是,在利用hash值计算存储位置时,为了防止计算出的位置超过capacity,计算的策略为:pos = hash & ma_mask
PyDictEntry * ma_table;  //指向存放Entry的空间
PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);  //entry查找函数
PyDictEntry ma_smalltable[PyDict_MINSIZE];  //对象被创建之初,初始会分配空间,ma_table初始指向ma_smalltable
} PyDictObject;

5.元素搜索的步骤:
假设搜索的键值为*key, 哈希值为hash
step1:pos = hash & ma_mask , 利用key的hash值计算存储位置
step2:e = &ma_table[pos], 若:
            if  e->me_key == NULL,return e //e是unused状态,表明dict中不存在key,返回空的entry
            if  e->me_key == key, return e //注意这里比较的是引用位置,me_key和key都是地址,相同表示e是要查找的entry,直接返回
            若不满足条件,则转Step3
step3:由于上面第二个if判断的是引用是否相同,而不是值是否相同,因此可能会错过值相同的键值相同引用不同的entry。
             如果e的状态是Active且e->me_hash == hash, 则检查值是否相同(因为hash不同值肯定不同)
             若值相同,则返回e,否则转step4
step4:如果e是Dumpy状态,按照开放定址往下找,如果找到空,则返回第一个Dumpy状态的entry

5.Dict的大小调整是在插入的时候出发的,删除entry并不会释放空间(伪删除机制)
插入时,检查ma_fill和ma_mask的关系,若ma_fill达ma_mask的2/3,并且使用过Dumpy状态的entry,则重新调整dict大小:
调整有可能变大,也有可能变小,如果Dummy的很多,则重新调整的空间会变小,因为重新分配空间后,会重新存储Active的entry,Dummy的entry会被删除
调整的空间会比需要的大很多,以减少插入冲突的可能性。

6.和其它Object类似,Dict也有缓存机制,创建PyDict对象时,若缓冲池中有空闲对象,则直接初始化使用,否则创建新对象。



作者:liushulinle | 分类: python | 标签: python Python源码 | 阅读: 26335 | 发布于: 2014-11-29 15时 |