由于Python內(nèi)部大量使用dict這種結(jié)構(gòu)，效率要求很高，所以Python沒有使用STL map的平衡二叉樹，而采用哈希表，最低能在O(1)時間內(nèi)完成搜索。
使用hash就必須解決沖突的問題，dict采用的是開放尋址法。原因我覺得是開放尋址法比拉鏈法能更好地利用CPU cache，cache命中率較高。
dict的哈希表里每個slot都是一個自定義的entry結(jié)構(gòu)：

typedef struct {
     Py_ssize_t me_hash;
     PyObject *me_key;
     PyObject *me_value;
} PyDictEntry;

每個entry有三種狀態(tài)：

Active, Unused, Dummy。
Unused:me_key == me_value == NULL，即未使用的空閑狀態(tài)。
Active:me_key != NULL, me_value != NULL，即該entry已被占用
Dummy:me_key == dummy, me_value == NULL。

哈希探測結(jié)束的條件是探測到一個Unused的entry。但是dict操作中必定會有刪除操作，如果刪除時僅把Active標記成Unused，顯然該entry之后的所有entry都不可能被探測到，所以引入了dummy結(jié)構(gòu)。遇到dummy就說明當前entry處于空閑狀態(tài)，但探測不能結(jié)束。這樣就解決了刪除一個entry之后探測鏈斷裂的問題。

dict對象的定義為：

struct _dictobject {
    PyObject _HEAD
    Py_ssize_t ma_fill; /* # Active + # Dummy */
    Py_ssize_t ma_used; /* # Active */
    Py_ssize_t ma_mask;

    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

ma_fill記錄Active + Dummy狀態(tài)的entry數(shù)。
ma_used記錄Active狀態(tài)的entry數(shù)。
ma_mask等于slot總數(shù) - 1。

因為一個key的哈希值很可能超過slot總數(shù)，所以作為索引時得把它約束在slot總數(shù)的范圍內(nèi)。而slot總數(shù)在定義的時候必須是2的乘冪，比如0x1000，所以減1之后就成了mask：0x111。再和hash做個&操作就能把索引之限制在0~0x111之間，即slot總數(shù)0x1000個，比較巧妙：）

ma_smalltable是默認的slot，初始有PyDict_MINSIZE個。
ma_table初始指向ma_smalltable，如果后期擴容，則指向新的slot空間。ma_lookup為搜索函數(shù)指針

dict對象的創(chuàng)建

dict對象的創(chuàng)建很簡單，先看看緩沖的對象池里有沒有可用對象，如果有就直接用，沒有就從堆上申請。把fill和used域設成0。由于Python中把字符串作為key的情況很多，所有搜索函數(shù)就有一個針對string優(yōu)化過的版本：lookdict_string。如果在檢查時發(fā)現(xiàn)key不是string對象，則調(diào)用默認的lookdict函數(shù)搜索。

dict對象的插入

dict的插入操作由insertdict函數(shù)完成。插入操作的意義是：如果不存在key-value則插入，存在則覆蓋。所以先通過ma_lookup所指向的函數(shù)得到key所對應的entry。如果value不等于NULL，說明找到，將key指針替換。否則就直接在返回的entry上設置新的key-value對。Python在處理d[key] = value這樣的表達式的時候調(diào)用的是insertdict函數(shù)的包裝函數(shù)PyDict_SetItem。PyDict_SetItem會計算key的哈希值，然后把需要的信息傳遞給insertdict。然后根據(jù)ma_table剩余空間的大小決定是否resize。傳說和理論證明超過容量的2/3時沖突的概率大大增加，所以超過2/3后會進行擴容。

dict對象的刪除

dict里entry的刪除更簡單，算出哈希值，找到entry，將其從Active轉(zhuǎn)換成Dummy，并調(diào)整table的容量。

最后是對象池。和前面list對象池一樣，dealloc時只回收table的內(nèi)存，然后將dict放到池中，供后來new時再用。減少向堆申請內(nèi)存的操作。