[[389930]]

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

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

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

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

【基本原理】

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

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

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

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

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

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

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

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

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

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

哈希表需要采取一定的策略來避免鍵沖突。當然，存在沖突的鍵的訪問效率也會有所降低。

下面我們就來看一下 CPython 是如何通過哈希表來實現(xiàn) dict 的。

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

1，字典對象 PyDictObject

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

每個 dict 都是一個 PyDictObject 對象。

此結(jié)構(gòu)中，最重要的是 ma_keys 這個成員變量，它是實現(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 的個數(shù) */ 
    Py_ssize_t dk_usable; 
 
    /* dk_entries 中已用 entries 的個數(shù) */ 
    Py_ssize_t dk_nentries; 
 
    /* 哈希表. 可動態(tài) resize。64位系統(tǒng)上其最小尺寸為8，32位系統(tǒng)上最小尺寸為4. */ 
    char dk_indices[]; 
     
    /* "PyDictKeyEntry dk_entries[dk_usable];" */ 
}; 
 
typedef struct _dictkeysobject PyDictKeysObject; 

從名稱來看，PyDictKeysObject 是用來存儲字典元素的 key 的。而實際上，在組合模式下，它存儲的是 key-value 對。那么，無論哪種模式，至少 key 是存儲在這個對象中的。

這個對象是我們研究的重點。

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

我們在上邊代碼中簡單標注了 PyDictObject 各成員變量的含義。現(xiàn)在重點關(guān)注dk_indices。

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

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

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

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

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

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

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

3，字典元素

typedef struct { 
    Py_hash_t me_hash;  /* 對 me_key 哈希值的緩存 */ 
    PyObject *me_key; 
    PyObject *me_value; /* 僅當哈希表為組合模式時有意義 */ 
} PyDictKeyEntry; 

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

哈希表為分離模式時，僅通過 me_key 存儲元素是 key。

【hash 表】

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

那么， 如何理解 dk_indices 這個哈希表呢?

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

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

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

開放尋址：從哈希表中的沖突位置查找下一個可用的位置。

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

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

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

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

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

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

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

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

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

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

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

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

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

大家可仔細體會一下這個過程。

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

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

【hash 算法和沖突算法】

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

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

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

CPython 采用開放尋址的方法來解決沖突。

其沖突算法如下：

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

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

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

dict 一個有趣的特性就是會保持元素插入時的位置順序：

>>> 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] 

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

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

【resize】

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

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

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

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

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

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

【結(jié)語】

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

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