首先來看看構(gòu)建dict的基礎(chǔ)設(shè)施：

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

這個(gè)結(jié)構(gòu)體為dict中key-value，其中的me_hash為me_key的hash值邓深，［空間換時(shí)間］他嫡。除此之外，我們發(fā)現(xiàn)me_key與me_value都是PyObject指針類型庐完，這也說明了為什么dict中的key與value可以為python中的任何類型數(shù)據(jù)钢属。

struct _dictobject {
    PyObject_HEAD;
    Py_ssize_t ma_fill;
    Py_ssize_t ma_used;
    Py_ssize_t ma_mask;
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

這個(gè)結(jié)構(gòu)體便是dict了。按照我們通常的理解门躯，dict應(yīng)該是可變長(zhǎng)對(duì)象跋场！為什么這里還有PyObject_HEAD讶凉，而不是PyObject_VAR_HEAD染乌。仔細(xì)一看，dict的可變長(zhǎng)與string,list,tuple仍有不同之外懂讯，后者可以通過PyObject_VAR_HEAD中的ob_size來指明其內(nèi)部有效元素的個(gè)數(shù)荷憋。但dict不能這樣做，所以dict干脆繞開PyObject_VAR_HEAD褐望，而且除了有ma_used這個(gè)字段來交代出其有效元素的個(gè)數(shù)勒庄，還需要ma_fill來交代清楚曾經(jīng)有效元素的個(gè)數(shù)（用來計(jì)算加載率）。
ma_mask瘫里，則牽扯到hash中的散列函數(shù);

ma_smalltable实蔽，python一向的有限空間換時(shí)間，一個(gè)小池子來應(yīng)付大多數(shù)的小dict（不超過PyDict_MINSIZE）
ma_lookup谨读，則是一次探測(cè)與二次探測(cè)函數(shù)的實(shí)現(xiàn)局装。
在展開dict實(shí)現(xiàn)細(xì)節(jié)前，先把dict使用的解決沖突的開放定址法介紹一下劳殖。我們知道哈希铐尚，就是將一個(gè)無限集合映射到一個(gè)有限集，如果選擇理想的hash函數(shù)哆姻，能夠?qū)㈩A(yù)期處理到的元素均勻分布到有限集中即可在O(1)時(shí)間內(nèi)完成元素查找宣增。但理想的hash函數(shù)是不存在的，且由于映射的本質(zhì)(無限到有限)必然出出現(xiàn)一個(gè)位置有多個(gè)元素要‘占據(jù)’填具，這就需要解決沖突〖泶停現(xiàn)有的解決沖突的方法：

• 開放定址法
• 鏈地址法
• 多哈希函數(shù)法
• 建域法

其中建域法基本思想為假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1],則設(shè)向量HashTable[0..m-1]為基本表菇篡，另外設(shè)立存儲(chǔ)空間向量OverTable[0..v]用以存儲(chǔ)發(fā)生沖突的記錄。
其中前兩種方法實(shí)現(xiàn)最為簡(jiǎn)單高效，下面回顧下開放定址與鏈地址法祭务。

開放定址法：

形成hash表時(shí)，某元素在第一次探測(cè)其應(yīng)該占有的位置時(shí)躺孝，如果發(fā)現(xiàn)此處(記為A)已經(jīng)被別人占了祖搓，那就在從A開始，再次探測(cè)(當(dāng)然這次探測(cè)使用的hash函數(shù)與第一次已經(jīng)不一樣了)筋量，如果發(fā)現(xiàn)還是被別人占了烹吵，那么繼續(xù)探測(cè)，至到找到一個(gè)可用位置(也有可能在當(dāng)下條件下永遠(yuǎn)找不到)桨武。開放地址法有一個(gè)至關(guān)重要的問題需要解決肋拔，那就是在一個(gè)元素離開hash表時(shí)，如何處理離開后的位置狀態(tài)呀酸。如果設(shè)置為原始空狀態(tài)凉蜂，那么后續(xù)的有效元素就無法識(shí)別了，因?yàn)樵诓檎視r(shí)同樣是依據(jù)上面的探測(cè)規(guī)則進(jìn)行查找性誉，所以必須告訴探測(cè)函數(shù)某個(gè)位置雖然無有效元素了窿吩，但后續(xù)的探測(cè)可能會(huì)出現(xiàn)有效元素。我們可以發(fā)現(xiàn)错览，開放定址法很容易發(fā)生沖突(主要是一次探測(cè)以上成功的元素占取其它元素應(yīng)該在第一次探測(cè)成功的位置)纫雁，所以就需要加大hash有效空間。

鏈地址法：

鏈地址法的思想很簡(jiǎn)單倾哺，你不是可能會(huì)出現(xiàn)多個(gè)元素對(duì)應(yīng)同一個(gè)位置轧邪，那么我就在這個(gè)位置拉出一個(gè)鏈表來存放所以hash到這個(gè)位置的元素。很簡(jiǎn)單吧羞海，還節(jié)約內(nèi)存呢闲勺！很遺憾，python的設(shè)計(jì)者沒有選它扣猫。
那為什么python發(fā)明者選擇了開放定址而不是鏈地址法菜循，在看python源碼時(shí)看到這么一段話：

Open addressing is preferred over chaining since the link overhead for chaining would be substantial (100% with typical malloc overhead).

由于鏈地址法需要?jiǎng)討B(tài)的生成鏈表結(jié)點(diǎn)(malloc)，所以時(shí)間效率不如開放定址法(但開放定址法的裝載率不能高于2/3申尤，相對(duì)于鏈地址法的空間開銷也是毋庸置疑的)癌幕，由此可以看出python的設(shè)計(jì)時(shí)代已經(jīng)不是那個(gè)內(nèi)存只有512k可供使用的時(shí)代了，對(duì)內(nèi)存的苛刻已經(jīng)讓步于效率昧穿。當(dāng)然這需要考慮到python由于實(shí)現(xiàn)動(dòng)態(tài)而必須靠自身的設(shè)計(jì)將損失的時(shí)間效率盡可能地補(bǔ)回來勺远。
好了，交待完開放定址法與為什么python設(shè)計(jì)者選擇它后时鸵，我們來看看dict如何實(shí)現(xiàn)這個(gè)算法的胶逢。前面已經(jīng)看到每個(gè)key-value由一個(gè)Entry結(jié)構(gòu)體實(shí)現(xiàn)厅瞎，python就是利用entry自身的信息來指明每個(gè)位置的狀態(tài)：原始空狀態(tài)、有效元素離去狀態(tài)初坠、有效元素占據(jù)狀態(tài)和簸。

• 原始空：me_key:Null ;me_value:Null
• 有效元素離去：me_key:dummy; me_value:Null
• 有效元素占據(jù)：me_key:not Null and not dummy ;me_value:not Null

其中dict的hash方法與沖突解決方法的思路如下：
lookdict(k,v)
index <- hash1(k)，freeslot<-Null,根據(jù)me_key與me_value選擇2碟刺、3锁保、4一個(gè)執(zhí)行;
查看index處的值處于’有效元素占據(jù)‘狀態(tài)，判斷data[index]與v是否一致(地址或內(nèi)容),一致,則返回查找成功;轉(zhuǎn)5
index所指向的位置處于’原始空‘狀態(tài)半沽，查找失敗爽柒，若freeslot==Null返回index;否則返回freeslot;轉(zhuǎn)5
index所指向的位置處于’有效元素離去‘狀態(tài)，freeslot<-index, 轉(zhuǎn)5
index <- hash2(index),者填，轉(zhuǎn)2

dict的lookdict方法實(shí)現(xiàn)充分體現(xiàn)了python對(duì)內(nèi)存的利用率與空間換時(shí)間提高效率上浩村，表現(xiàn)為如下方面：
內(nèi)存利用率：當(dāng)找到原始空狀態(tài)時(shí)，如果前面已經(jīng)找到dummy態(tài)的entry占哟，則會(huì)將其返回心墅。
提高效率：ma_table始終指向有效散列空間的開始位置，在開辟新空間后重挑，small_table就棄之不用了嗓化，ma_table改指向新開辟空間的首位置。

another one

dict實(shí)現(xiàn)

本文描述了Python是如何實(shí)現(xiàn)dictionary谬哀。dictionary是由主鍵key索引刺覆，可以被看作是關(guān)聯(lián)數(shù)組，類似于STL的map史煎。有如下的基本操作谦屑。
d = {'a': 1, 'b': 2}
d['c'] = 3
d
{'a': 1, 'b': 2, 'c': 3}

hash table

Python中dictionary是以hash表實(shí)現(xiàn)，而hash表以數(shù)組表示篇梭，數(shù)組的索引作為主鍵key氢橙。Hash函數(shù)的目標(biāo)是key均勻的分布于數(shù)組中，良好的hash函數(shù)能夠最小化減少?zèng)_突的次數(shù)恬偷。
在本文中悍手，我們采用string作為key為例子。

arguments: string object
returns: hash
function string_hash:
    if hash cached:
        return it
    set len to string's length
    initialize var p pointing to 1st char of string object
    set x to value pointed by p left shifted by 7 bits
    while len >= 0:
        set var x to (1000003 * x) xor value pointed by p
         increment pointer p
    set x to x xor length of string object

    cache x as the hash so we don't need to calculate it again
    return x as the hash

如果你執(zhí)行hash(‘a(chǎn)’)袍患，函數(shù)將會(huì)執(zhí)行string_hash()返回12416037344坦康，在此我們假設(shè)采用的是64位系統(tǒng)。
假設(shè)數(shù)組的大小是x诡延， 該數(shù)組用來存儲(chǔ)key/value滞欠， 我們用掩碼x-1計(jì)算這個(gè)數(shù)組的索引。例如肆良，如果數(shù)組的大小是8筛璧，‘a(chǎn)’的索引是hash(‘a(chǎn)’)&7=0逸绎， ‘b’的索引是3， ‘c’的索引是2夭谤」啄粒’z’的索引是3與’b’的索引一致，由此導(dǎo)致沖突沮翔。

我們看到Python中的hash函數(shù)在key是連續(xù)的時(shí)候表現(xiàn)很好的性能陨帆，原因是它對(duì)于處理這種類型的數(shù)據(jù)有通用性曲秉。但是采蚀，一旦我們加入了’z’，由于數(shù)據(jù)的不連貫性產(chǎn)生了沖突承二。
當(dāng)產(chǎn)生沖突的時(shí)候榆鼠，我們可以采用鏈表來存儲(chǔ)這對(duì)key/value，但是這樣增加了查找時(shí)間亥鸠，不再是O(1)的復(fù)雜度妆够。在下一節(jié)中，我們將要具體描述一下Python中dictionary解決這種沖突的方法负蚊。

Open addressing

散列地址方法是解決hash沖突的探測(cè)策略神妹。對(duì)于’z’，由于索引3已經(jīng)被占用家妆，所以我們需要尋找一個(gè)沒有使用的索引鸵荠，這樣添加key/value的時(shí)候肯能花費(fèi)更多的時(shí)間，但是查找時(shí)間依然是O(1)伤极，這是我們所期望的結(jié)果蛹找。
這里采用quadratic探測(cè)序列來尋找可用的索引，代碼如下：

i is the current slot index
set perturb to hash
forever loop:
  set i to i << 2 + i + perturb + 1
  set slot index to i & mask
  if slot is free:
      return it
  right shift perturb by 5 bits

讓我們來看看它是如何工作的哨坪，令i=33 -> 3 -> 5 -> 5 -> 6 -> 0…
索引5將被用作’z’的索引值庸疾，這不是一個(gè)很好的例子，因?yàn)槲覀儾捎昧艘粋€(gè)大小是8的數(shù)組当编。對(duì)于大數(shù)組届慈，算法顯示它的優(yōu)勢(shì)。
出于好奇忿偷，我們來看看當(dāng)數(shù)組大小是32金顿，mask是31時(shí)，探測(cè)序列為3 -> 11 -> 19 -> 29 -> 5 -> 6 -> 16 -> 31 -> 28 -> 13 -> 2…
如果你想了解更多牵舱，可以察看dictobject.c的源代碼串绩。

接下來，讓我們看看Python內(nèi)部的代碼是如何實(shí)現(xiàn)的芜壁？

Dictionary C structures

如下的C語(yǔ)言結(jié)構(gòu)體用來存儲(chǔ)一個(gè)dictionary條目：key/value對(duì)礁凡，結(jié)構(gòu)體內(nèi)有Hash值高氮，key值和value值。PyObject是Python對(duì)象的基類顷牌。
1
typedef struct {
2
Py_ssize_t me_hash;

3
PyObject *me_key;
4
PyObject *me_value;

5
} PyDictEntry;
如下的結(jié)構(gòu)體代表了一個(gè)dictionary剪芍。ma_fill是已使用slot與未使用slot之和。當(dāng)一對(duì)key/value被刪除了窟蓝，該slot被標(biāo)記為未使用罪裹。ma_used是已使用slot的數(shù)目。ma_mask等于數(shù)組大小減一运挫，用來計(jì)算slot的索引状共。ma_table是該數(shù)組，ma_smalltable是初始數(shù)組大小為8.

typedef struct _dictobject PyDictObject;
struct _dictobject {
    PyObject_HEAD
    Py_ssize_t ma_fill;
    Py_ssize_t ma_used;
    Py_ssize_t ma_mask;
    PyDictEntry *ma_table;
    PyDictEntry *(*ma_lookup)(PyDictObject *mp, PyObject *key, long hash);
    PyDictEntry ma_smalltable[PyDict_MINSIZE];
};

Dictionary initialization

當(dāng)我們第一次創(chuàng)建一個(gè)dictionary的時(shí)候谁帕，將會(huì)調(diào)用PyDict_New()峡继。我們以偽碼表示該函數(shù)的主要功能。

returns new dictionary object
function PyDict_New:
    allocate new dictionary object
    clear dictionary's table
    set dictionary's number of used slots + dummy slots (ma_fill) to 0
    set dictionary's number of active slots (ma_used) to 0
    set dictionary's mask (ma_value) to dictionary size - 1 = 7
    set dictionary's lookup function to lookdict_string
    return allocated dictionary object

Adding items

當(dāng)增加一對(duì)新的key/value時(shí)匈挖，將調(diào)用PyDict_SetItem()碾牌。該函數(shù)的參數(shù)有dictionary對(duì)象的指針和key/value對(duì)。它檢測(cè)key是否為字符串以及計(jì)算hash值或者重復(fù)使用已經(jīng)存在的index儡循。Insertdict()用來增加新的key/value舶吗，在dictionary的大小被重新調(diào)整之后，而且已使用slot的數(shù)量超過數(shù)組大小的2/3.
為什么是2/3择膝？這樣能夠保證probing序列能夠快速地找到空閑的slot誓琼。稍后我們將看看調(diào)整數(shù)組大小的函數(shù)。

arguments: dictionary, key, value
returns: 0 if OK or -1
function PyDict_SetItem:
    set mp to point to dictionary object
    if key's hash cached:
        use hash
    else:
        calculate hash
    set n_used to dictionary's number of active slots (ma_used)
    call insertdict with dictionary object, key, hash and value
    if key/value pair added successfully and capacity over 2/3:
        call dictresize to resize dictionary's table

Insertdict()使用查找函數(shù)來找到一個(gè)未使用的slot调榄。接下來我們來看看這個(gè)函數(shù)踊赠，lookdict_string()利用hash值和掩碼來計(jì)算slot的索引。如果它找不到slot索引的key等于hash&mask每庆，它會(huì)使用擾碼來探測(cè)筐带。

arguments: dictionary object, key, hash
returns: dictionary entry
function lookdict_string:
    calculate slot index based on hash and mask
    if slot's key matches or slot's key is not set:
        returns slot's entry
    if slot's key marked as dummy (was active):
        set freeslot to this slot's entry
    else:
        if slot's hash equals to hash and slot's key equals to key:
            return slot's entry
        set var freeslot to null
    we are here because we couldn't find the key so we start probing
    set perturb to hash
    forever loop:
        set i to i << 2 + i + perturb + 1
        calculate slot index based on i and mask
        if slot's key is null:
            if freeslot is null:
                return slot's entry
            else:
                return freeslot

        if slot's key equals to key or slot's hash equals to hash
            and slot is not marked as dummy:
            return slot's entry
        if slot marked as dummy and freeslot is null:
            set freeslot to slot's entry
        right shift perturb by 5 bits

我們?cè)赿ictionary中增加如下的key/value：{‘a(chǎn)’: 1, ‘b’: 2′, ‘z’: 26, ‘y’: 25, ‘c’: 5, ‘x’: 24}。流程如下：

• PyDict_SetItem: key = ‘a(chǎn)’, value = 1
  • hash = hash(‘a(chǎn)’) = 12416037344
  • insertdict
    • lookdict_string
      • slot index = hash & mask = 12416037344 & 7 = 0
      • slot 0 is not used so return it
    • init entry at index 0 with key, value and hash
    • ma_used = 1, ma_fill = 1
• PyDict_SetItem: key = ‘b’, value = 2
  • hash = hash(‘b’) = 12544037731
  • insertdict
    • lookdict_string
      • slot index = hash & mask = 12544037731 & 7 = 3
      • slot 3 is not used so return it
    • init entry at index 3 with key, value and hash
    • ma_used = 2, ma_fill = 2
• PyDict_SetItem: key = ‘z’, value = 26
  • hash = hash(‘z’) = 15616046971
  • insertdict
    • lookdict_string
      • slot index = hash & mask = 15616046971 & 7 = 3
      • slot 3 is used so probe for a different slot: 5 is free
    • init entry at index 5 with key, value and hash
    • ma_used = 3, ma_fill = 3
• PyDict_SetItem: key = ‘y’, value = 25
  hash = hash(‘y’) = 15488046584
  insertdict
  lookdict_string
  slot index = hash & mask = 15488046584 & 7 = 0
  slot 0 is used so probe for a different slot: 1 is free
  init entry at index 1 with key, value and hash
  ma_used = 4, ma_fill = 4
• PyDict_SetItem: key = ‘c’, value = 3
  hash = hash(‘c’) = 12672038114
  insertdict
  lookdict_string
  slot index = hash & mask = 12672038114 & 7 = 2
  slot 2 is free so return it
  init entry at index 2 with key, value and hash
  ma_used = 5, ma_fill = 5
• PyDict_SetItem: key = ‘x’, value = 24
  hash = hash(‘x’) = 15360046201
  insertdict
  lookdict_string
  slot index = hash & mask = 15360046201 & 7 = 1
  slot 1 is used so probe for a different slot: 7 is free
  init entry at index 7 with key, value and hash
  ma_used = 6, ma_fill = 6

This is what we have so far:

由于8個(gè)slot中的6已經(jīng)被使用了即超過了數(shù)組容量的2/3缤灵，dictresize()被調(diào)用來分配更大的內(nèi)存伦籍，該函數(shù)同時(shí)拷貝舊數(shù)據(jù)表的數(shù)據(jù)進(jìn)入新數(shù)據(jù)表。
在這個(gè)例子中腮出，dictresize()調(diào)用時(shí)帖鸦，minused是24也就是4×ma_used。當(dāng)已使用slot的數(shù)目很大的時(shí)候(超過50000)minused是2×ma_used胚嘲。為什么是4倍作儿？這樣能夠減少調(diào)整步驟的數(shù)目而且增加稀疏度。
v新數(shù)據(jù)表的大少應(yīng)該大于24馋劈，它是通過把當(dāng)前數(shù)據(jù)表的大小左移一位實(shí)現(xiàn)的攻锰，直到她大于24.例如 8 -> 16 -> 32.

arguments: dictionary object, (2 or 4) * active slots
returns: 0 if OK, -1 otherwise
function dictresize:
    calculate new dictionary size:
        set var newsize to dictionary size
        while newsize less or equal than (2 or 4) * active slots:
            set newsize to newsize left shifted by 1 bit
    set oldtable to dictionary's table
    allocate new dictionary table
    set dictionary's mask to newsize - 1
    clear dictionary's table
    set dictionary's active slots (ma_used) to 0
    set var i to dictionary's active + dummy slots (ma_fill)
    set dictionary's active + dummy slots (ma_fill) to 0
    copy oldtable entries to dictionary's table using new mask
    return 0
}

當(dāng)數(shù)據(jù)表大小進(jìn)行調(diào)整的時(shí)候所發(fā)生的：分配了一個(gè)大小是32的新數(shù)據(jù)表

removing items

函數(shù)PyDict_DelItem()用來刪除一個(gè)條目晾嘶。計(jì)算key的hash值，然后調(diào)用查找函數(shù)返回這個(gè)條目娶吞。該條目的key設(shè)置為啞元垒迂。這個(gè)啞元包含了過去使用過的key值但現(xiàn)在還是未使用的狀態(tài)。

arguments: dictionary object, key
returns 0 if OK, -1 otherwise
function PyDict_DelItem:
    if key's hash cached:
        use hash
    else:
        calculate hash
    look for key in dictionary using hash
    if slot not found:
        return -1
    set slot's key to dummy
    set slot's value to null
    decrement dictionary active slots
    return 0

如果我要從dictionary中刪除key ’c’妒蛇，將以如下的數(shù)組結(jié)束

注意：刪除操作并沒有改變數(shù)組的大小机断，即使已使用slot的數(shù)目遠(yuǎn)小于slot的總數(shù)目。