【Python旧时笔记 五】PyDictObject头文件阅读

圣凤凌霜

dictobject.h

PyDictObject是一种字典类型，从可哈希的对象映射到另一个对象。
然后提到了在Objects目录下，有dictnotes.txt文件，关于字典的使用设计和优化。


字典类实际上是维护了一张哈希表，而表项，entry or slot，有3种状态。
1. Unused. me_key == me_value == NULL
未使用状态，key和value都为空。
这是表项的初始状态，仅当初始时key才会为空。
2. Active. me_key != NULL and me_key != dummy and me_value != NULL
正在使用状态，key不为空且不为dummy，value不为空。
3. Dummy. me_key == dummy and me_value == NULL
曾使用状态，但该表项已经被删除了。key为dummy，value为空。
设置Dummy状态是因为Python面对hash冲突时所采取的是开放地址法，会再次寻找位置。
所以会产生探索链这样的关联结构，比如A、B、C三者的哈希值一样，那么会处在一条探索链上。
当B被删除后，为了保证能够搜索到C，特地设置Dummy值，表示后面还可能存在有效表项。


#definePyDict_MINSIZE8
PyDict_MINSIZE是一个字典的最小大小，这个“小字典”是直接作为表项的成员的，ma_smalltable。
表项的结构如下：
typedefstruct{
/* 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_tme_hash;
PyObject*me_key;
PyObject*me_value;
}PyDictEntry;
由注释可以知道me_hash的一个作用是避免重复计算，另一个作用是可以用来指向探索链的下一个。


字典的结构如下：
typedefstruct_dictobjectPyDictObject;
struct_dictobject{
PyObject_HEAD
Py_ssize_tma_fill;/*# Active + # Dummy */
Py_ssize_tma_used;/*# Active */


/* The table contains ma_mask + 1 slots, and that's a power of 2.
* We store the mask instead of the size because the mask is more
* frequently needed.
*/
Py_ssize_tma_mask;


/* ma_table points to ma_smalltable for small tables, else to
* additional malloc'ed memory. ma_table is never NULL! This rule
* saves repeated runtime null-tests in the workhorse getitem and
* setitem calls.
*/
PyDictEntry*ma_table;
PyDictEntry*(*ma_lookup)(PyDictObject*mp,PyObject*key,longhash);
PyDictEntryma_smalltable[PyDict_MINSIZE];
};
由注释可知ma_fill和ma_used的含义。
ma_mask经常用来与key的哈希值进行与运算，使其落在表的范围内。
ma_table指向ma_smalltable或者另外分配的内存。


为了保证在表中搜索位置的过程会终止，表中至少有一项Unused。
另外为了避免低效搜索，当有三分之二的表项被使用了，会重新调整表的大小。


JasonLee   2011.08.14   23：35   明天又周一了，今天大连散步