【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 明天又周一了，今天大连散步