[[389930]]

 在《RealPython 基礎(chǔ)教程：Python 字典用法詳解》這篇文章中，我們介紹了 dict 的特性：

• dict 是存儲(chǔ)鍵值對(duì)的關(guān)聯(lián)容器
• dict 中的 key 是唯一的
• 可使用 dict[key] 語(yǔ)法來(lái)快速訪問(wèn) dict 中的元素
• Python 3.6 之后的版本會(huì)保持元素添加到 dict 中的順序

那么，Python 底層是如何支撐這些特性的呢?其運(yùn)行效率如何?

我們今天就來(lái)簡(jiǎn)單探索一下 dict 在 Python 中的底層實(shí)現(xiàn)，并嘗試結(jié)合 CPython 源碼來(lái)回答上邊的問(wèn)題。

【基本原理】

首先我們來(lái)思考一下如何從一批數(shù)據(jù)中快速查找一個(gè)元素。

在計(jì)算機(jī)中，對(duì)數(shù)據(jù)的訪問(wèn)是基于數(shù)據(jù)的存儲(chǔ)方式的，不同的存儲(chǔ)方式訪問(wèn)效率差別很大。

我們熟知的 list，底層是基于數(shù)組實(shí)現(xiàn)的。數(shù)組的優(yōu)點(diǎn)在于能通過(guò)索引實(shí)現(xiàn)隨機(jī)訪問(wèn)，非?？?，時(shí)間復(fù)雜度為O(1)。但前提是，你需要知道被訪問(wèn)的元素的位置。而對(duì)于 key-value 這種關(guān)聯(lián)數(shù)據(jù)，我們?cè)趹?yīng)用中并不關(guān)注其存放位置。

如果單純使用數(shù)組來(lái)存放 key-value，我們需要按順序比對(duì)數(shù)組中的每個(gè)元素，找到目的 key。當(dāng)數(shù)據(jù)量很大時(shí)，這種查找效率很低。

有沒(méi)有能實(shí)現(xiàn)高效比對(duì)的數(shù)據(jù)結(jié)構(gòu)呢?有!

學(xué)過(guò) C++ 的同學(xué)應(yīng)該知道，C++ 標(biāo)準(zhǔn)庫(kù)提供了一個(gè)關(guān)聯(lián)容器：map。它可以高效地存取鍵值對(duì)，其底層是基于紅黑樹(shù)來(lái)實(shí)現(xiàn)的。紅黑樹(shù)是一個(gè)自平衡的二叉搜索樹(shù)，查找效率很高。

那么，Python 中的 dict 是基于紅黑樹(shù)實(shí)現(xiàn)的嗎?答案是否定的。

Python 為了實(shí)現(xiàn)更快的訪問(wèn)速率，采用了另一種存儲(chǔ)結(jié)構(gòu)：哈希表。

哈希表基于數(shù)組隨機(jī)訪問(wèn)的特性，使用哈希算法來(lái)快速計(jì)算 key 的哈希值，從而定位元素在底層數(shù)組中的位置，實(shí)現(xiàn)元素的快速訪問(wèn)。

這種結(jié)構(gòu)的訪問(wèn)效率和數(shù)組相同，但是存在一定的缺點(diǎn)：哈希算法無(wú)法保證對(duì)每個(gè) key 求值結(jié)果的唯一性，因而不同的 key 可能會(huì)得到相同的存放位置。這就導(dǎo)致了沖突。

哈希表需要采取一定的策略來(lái)避免鍵沖突。當(dāng)然，存在沖突的鍵的訪問(wèn)效率也會(huì)有所降低。

下面我們就來(lái)看一下 CPython 是如何通過(guò)哈希表來(lái)實(shí)現(xiàn) dict 的。

【字典相關(guān)數(shù)據(jù)結(jié)構(gòu)】

1，字典對(duì)象 PyDictObject

typedef struct { 
    PyObject_HEAD 
 
    /*字典用元素的個(gè)數(shù)*/ 
    Py_ssize_t ma_used; 
 
    /*全局唯一的版本號(hào)，會(huì)在 dict 被修改時(shí)發(fā)生變化*/ 
    uint64_t ma_version_tag;  
 
    /*存放元素或元素 key，承擔(dān)哈希表的具體實(shí)現(xiàn)*/ 
    PyDictKeysObject *ma_keys;  
   
    /* 
    當(dāng)哈希表為組合（combined）模式時(shí)，value 存儲(chǔ)在 ma_keys 的每個(gè) PyDictKeyEntry 對(duì)象中，此值為 NULL。 
    當(dāng)哈希表為分離（splitted）模式時(shí)用于存儲(chǔ)元素的 value。 
    */ 
    PyObject **ma_values;  
} PyDictObject; 

每個(gè) dict 都是一個(gè) PyDictObject 對(duì)象。

此結(jié)構(gòu)中，最重要的是 ma_keys 這個(gè)成員變量，它是實(shí)現(xiàn)哈希表的關(guān)鍵所在。

2，哈希表 PyDictKeysObject

struct _dictkeysobject { 
    Py_ssize_t dk_refcnt; 
 
    /* 哈希表(dk_indices)的大小，其值為 2 的乘冪. */ 
    Py_ssize_t dk_size; 
 
    /* 用于在哈希表(dk_indices)中執(zhí)行查找的函數(shù)*/ 
    dict_lookup_func dk_lookup; 
 
    /* dk_entries 中可用 entries 的個(gè)數(shù) */ 
    Py_ssize_t dk_usable; 
 
    /* dk_entries 中已用 entries 的個(gè)數(shù) */ 
    Py_ssize_t dk_nentries; 
 
    /* 哈希表. 可動(dòng)態(tài) resize。64位系統(tǒng)上其最小尺寸為8，32位系統(tǒng)上最小尺寸為4. */ 
    char dk_indices[]; 
     
    /* "PyDictKeyEntry dk_entries[dk_usable];" */ 
}; 
 
typedef struct _dictkeysobject PyDictKeysObject; 

從名稱來(lái)看，PyDictKeysObject 是用來(lái)存儲(chǔ)字典元素的 key 的。而實(shí)際上，在組合模式下，它存儲(chǔ)的是 key-value 對(duì)。那么，無(wú)論哪種模式，至少 key 是存儲(chǔ)在這個(gè)對(duì)象中的。

這個(gè)對(duì)象是我們研究的重點(diǎn)。

PyDictKeysObject 的內(nèi)存布局如下所示：

我們?cè)谏线叴a中簡(jiǎn)單標(biāo)注了 PyDictObject 各成員變量的含義?，F(xiàn)在重點(diǎn)關(guān)注dk_indices。

dk_indices 是一個(gè) char 類型的數(shù)組，從定義來(lái)看，這是一塊裸內(nèi)存。它正是哈希表真正使用的存儲(chǔ)空間。

dk_indices 數(shù)組的前部分存放的是字典元素(鍵值對(duì))在 dk_entries 中的索引值。我們可把這部分叫做：哈希表索引內(nèi)存塊。

根據(jù)數(shù)組大小的不同，每個(gè)索引值的類型具有不同的解釋方法。

由此可見(jiàn)，數(shù)組越大，每個(gè)值表示的索引范圍也越大。

每個(gè)索引值的取值區(qū)間為[0, dk_size*2/3]，或者為：-1(內(nèi)存未被使用過(guò))，-2(內(nèi)存已使用過(guò))。

dk_indices 數(shù)組的后半部分用于存儲(chǔ) dict 中的元素。這段空間被解釋為：PyDictKeyEntry dk_entries[dk_usable]。我們可把這部分叫做：哈希表鍵值對(duì)內(nèi)存塊。

dk_entries 中元素的個(gè)數(shù)為 dk_size 的 2/3。這個(gè)值既能有效減少 key 的沖突，也可提升內(nèi)存空間的利用率。

3，字典元素

typedef struct { 
    Py_hash_t me_hash;  /* 對(duì) me_key 哈希值的緩存 */ 
    PyObject *me_key; 
    PyObject *me_value; /* 僅當(dāng)哈希表為組合模式時(shí)有意義 */ 
} PyDictKeyEntry; 

哈希表為組合模式時(shí)，這里邊存放的就是我們的鍵值對(duì)。

哈希表為分離模式時(shí)，僅通過(guò) me_key 存儲(chǔ)元素是 key。

【hash 表】

從上邊數(shù)據(jù)結(jié)構(gòu)的定義中，我們已經(jīng)知道，dict 會(huì)將鍵值對(duì)存放在一塊連續(xù)的內(nèi)存空間 dk_indices 中。dk_indices 正是 dict 使用的哈希表。

那么， 如何理解 dk_indices 這個(gè)哈希表呢?

通常，哈希表有兩種實(shí)現(xiàn)方式：沖突鏈和開(kāi)放尋址。這兩種方式對(duì)應(yīng)的是兩種解決鍵沖突的方法。

沖突鏈：將哈希值相同的 key 組織為一個(gè)鏈表。

哈希表只存放指向元素鏈表的指針，哈希值相同的元素依次追加到每個(gè)鏈表的尾部。

開(kāi)放尋址：從哈希表中的沖突位置查找下一個(gè)可用的位置。

元素存放在哈希表中，若發(fā)現(xiàn)沖突，從沖突位置(如 kv1 所在位置)開(kāi)始通過(guò)某種策略查找下一個(gè)可用的位置(如 kv3)。

CPython 采用的是開(kāi)放尋址方式，并且使用了一種優(yōu)化的存儲(chǔ)結(jié)構(gòu)。

dk_indices 數(shù)組的前部分用來(lái)存儲(chǔ)鍵值對(duì)的位置索引，后部分用來(lái)存儲(chǔ)鍵值對(duì)。這是一種高效緊湊的存儲(chǔ)結(jié)構(gòu)。

我們從 dictobject.c 的 insert_dict() 函數(shù)中截取一段代碼，來(lái)驗(yàn)證這個(gè)結(jié)構(gòu)。

insertdict(PyDictObject *mp, PyObject *key, Py_hash_t hash, PyObject *value) 函數(shù)用于向字典 mp 中插入一個(gè)哈希值為 hash 的 key-value 鍵值對(duì)。

這個(gè)片段開(kāi)頭的 if (ix == DKIX_EMPTY) 表明可以將這個(gè)鍵值對(duì)插入哈希表的一個(gè)未曾使用過(guò)的位置(稱為 slot)中。

代碼接下來(lái)檢查哈希表剩余空間是否可用，不足則 resize。

接下來(lái)調(diào)用 find_empty_slot() 獲取 slot 在哈希表索引內(nèi)存塊中的位置索引 hashpos，這個(gè)函數(shù)實(shí)現(xiàn)了沖突算法。

通過(guò) DK_ENTRIES 宏獲取 ma_keys 中下一塊可用的內(nèi)存 ep，由于哈希表鍵值對(duì)內(nèi)存塊是連續(xù)的，下一塊可用的內(nèi)存可通過(guò)當(dāng)前已存儲(chǔ)的鍵值對(duì)個(gè)數(shù) dk_nentries 加上 dk_indices 前部分的偏移計(jì)算而來(lái)。

#define DK_ENTRIES(dk) \ 
    ((PyDictKeyEntry*)(&((int8_t*)((dk)->dk_indices))[DK_SIZE(dk) * DK_IXSIZE(dk)])) 

我們通過(guò) DK_ENTRIES 的宏定義能清楚地看到它是在訪問(wèn) dk_indices 的鍵值對(duì)內(nèi)存塊。

現(xiàn)在，我們知道了元素在哈希表索引內(nèi)存塊中的位置 hashpos 和在鍵值對(duì)內(nèi)存塊中的“相對(duì)位置” dk_nentries，調(diào)用 dictkeys_set_index() 即可在哈希表中設(shè)置這兩者的關(guān)系：indices[hashpos] = dk_nentries.

接下來(lái)的代碼對(duì) ep 指向的內(nèi)存數(shù)據(jù)進(jìn)行了更新，并累加 dk_nentries。

大家可仔細(xì)體會(huì)一下這個(gè)過(guò)程。

這種存儲(chǔ)結(jié)構(gòu)，也保證了使用 key 訪問(wèn)元素的效率。

由 key 的哈希值能快速映射到元素在哈希表索引內(nèi)存塊的位置 hashpos，再由 hashpos 中保存的鍵值對(duì)內(nèi)存塊的位置偏移“索引”就可以直接訪問(wèn)對(duì)應(yīng)的鍵值對(duì)。

【hash 算法和沖突算法】

實(shí)現(xiàn)哈希表有三個(gè)重要的元素：數(shù)據(jù)結(jié)構(gòu)、hash 算法和沖突算法。

我們已經(jīng)了解了數(shù)據(jù)結(jié)構(gòu)。那么，CPython 使用什么 hash 算法呢?

如果你沒(méi)有手動(dòng)實(shí)現(xiàn) __hash__ 方法，它就使用內(nèi)置的 hash() 函數(shù)來(lái)計(jì)算 key 的哈希值。

CPython 采用開(kāi)放尋址的方法來(lái)解決沖突。

其沖突算法如下：

首先初始化哈希表的位置索引 i，然后獲取 i 處存放的鍵值對(duì)內(nèi)存塊的索引 ix。在循環(huán)中不斷更新 i 并檢測(cè) ix 的值，直到 ix < 0，即此時(shí)哈希表索引內(nèi)存塊的 i 處代表著一個(gè)從未使用的 slot。

更新 i 的算法不太容易理解，可不用深究。

【如何保持元素插入順序】

dict 一個(gè)有趣的特性就是會(huì)保持元素插入時(shí)的位置順序：

>>> d={} 
>>> d[3]="Three" 
>>> d[1]="One" 
>>> d[2]="Two" 
>>> d[0]="Zero" 
>>> d 
{3: 'Three', 1: 'One', 2: 'Two', 0: 'Zero'} 
>>> 
>>> list(d.keys()) 
[3, 1, 2, 0] 

從上邊對(duì)哈希表的分析中，我們很容易就能明白其中的原因：元素被逐個(gè)追加到鍵值對(duì)內(nèi)存塊的尾部。

當(dāng)我們打印 dict，或調(diào)用其 keys() 方法時(shí)，dict 直接訪問(wèn)鍵值對(duì)內(nèi)存塊。因而可按照元素插入時(shí)的順序?qū)⑺鼈兎祷亍?/p>

【resize】

既然 dict 使用了連續(xù)的內(nèi)存塊來(lái)實(shí)現(xiàn)哈希表，那么當(dāng)插入較多元素時(shí)，其內(nèi)存空間有可能不足，這時(shí)就需要擴(kuò)大內(nèi)存。另一方面，如果之前已分配了較大內(nèi)存空間，而后執(zhí)行了大量刪除元素的操作，這時(shí)候也有必要減小內(nèi)存，避免浪費(fèi)。

static int 
insertion_resize(PyDictObject *mp) 
{ 
    return dictresize(mp, GROWTH_RATE(mp)); 
} 

insertion_resize() 調(diào)用 dictresize() 來(lái)調(diào)整 dict 的大小。dictresize() 的第二個(gè)參數(shù)就是調(diào)整后的大小，這里是一個(gè)宏。在 CPython 3.9.2 中，其定義為：

#define GROWTH_RATE(d) ((d)->ma_used*3)

可以看到，dict 的大小會(huì)被調(diào)整為原來(lái)已使用(包含有效鍵值對(duì))內(nèi)存的 3 倍。

這個(gè)調(diào)整幅度還是蠻大的，其好處是可以避免頻繁 resize。

【結(jié)語(yǔ)】

本文簡(jiǎn)單介紹了 Python 字典的底層數(shù)據(jù)結(jié)構(gòu)和實(shí)現(xiàn)算法，通過(guò)使用內(nèi)存優(yōu)化的哈希表，dict 很好地支持了快速查找和插入有序等特性。這種數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)方法非常很值得我們?cè)陂_(kāi)發(fā)中借鑒使用。

本文轉(zhuǎn)載自微信公眾號(hào)「python學(xué)與思」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系python學(xué)與思公眾號(hào)。