234
技術社區[雲棲]
[筆記]PyDictObject頭文件閱讀
dictobject.hPyDictObject是一種字典類型，從可哈希的對象映射到另一個對象。
然後提到了在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值，表示後麵還可能存在有效表項。
#define PyDict_MINSIZE 8
PyDict_MINSIZE是一個字典的最小大小，這個“小字典”是直接作為表項的成員的，ma_smalltable。
表項的結構如下：
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;
由注釋可以知道me_hash的一個作用是避免重複計算，另一個作用是可以用來指向探索鏈的下一個。
字典的結構如下：
typedef struct _dictobject PyDictObject;
struct _dictobject {
PyObject_HEAD
Py_ssize_t ma_fill; /* # Active + # Dummy */
Py_ssize_t ma_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_t ma_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, long hash);
PyDictEntry ma_smalltable[PyDict_MINSIZE];
};
由注釋可知ma_fill和ma_used的含義。
ma_mask經常用來與key的哈希值進行與運算，使其落在表的範圍內。
ma_table指向ma_smalltable或者另外分配的內存。
為了保證在表中搜索位置的過程會終止，表中至少有一項Unused。
另外為了避免低效搜索，當有三分之二的表項被使用了，會重新調整表的大小。
JasonLee 2011.08.14 23：35 明天又周一了，今天大連散步
最後更新：2017-04-02 22:16:33