[[389930]]

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

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

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

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

【基本原理】

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

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

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

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

有沒有能實現高效比對的數據結構呢?有!

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

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

Python 為了實現更快的訪問速率，采用了另一種存儲結構：哈希表。

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

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

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

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

【字典相關數據結構】

1，字典對象 PyDictObject

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

每個 dict 都是一個 PyDictObject 對象。

此結構中，最重要的是 ma_keys 這個成員變量，它是實現哈希表的關鍵所在。

2，哈希表 PyDictKeysObject

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

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

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

PyDictKeysObject 的內存布局如下所示：

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

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

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

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

索引類型	數組大小 dk_size
int8	dk_size <= 128
int16	256   <= dk_size <= 2**15
int32	2**16 <= dk_size <= 2**31
int64	dk_size >= 2**32

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

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

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

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

3，字典元素

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

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

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

【hash 表】

從上邊數據結構的定義中，我們已經知道，dict 會將鍵值對存放在一塊連續的內存空間 dk_indices 中。dk_indices 正是 dict 使用的哈希表。

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

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

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

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

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

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

CPython 采用的是開放尋址方式，并且使用了一種優化的存儲結構。

dk_indices 數組的前部分用來存儲鍵值對的位置索引，后部分用來存儲鍵值對。這是一種高效緊湊的存儲結構。

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

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

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

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

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

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

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

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

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

接下來的代碼對 ep 指向的內存數據進行了更新，并累加 dk_nentries。

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

這種存儲結構，也保證了使用 key 訪問元素的效率。

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

【hash 算法和沖突算法】

實現哈希表有三個重要的元素：數據結構、hash 算法和沖突算法。

我們已經了解了數據結構。那么，CPython 使用什么 hash 算法呢?

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

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

其沖突算法如下：

首先初始化哈希表的位置索引 i，然后獲取 i 處存放的鍵值對內存塊的索引 ix。在循環中不斷更新 i 并檢測 ix 的值，直到 ix < 0，即此時哈希表索引內存塊的 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] 

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

當我們打印 dict，或調用其 keys() 方法時，dict 直接訪問鍵值對內存塊。因而可按照元素插入時的順序將它們返回。

【resize】

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

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

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

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

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

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

【結語】

本文簡單介紹了 Python 字典的底層數據結構和實現算法，通過使用內存優化的哈希表，dict 很好地支持了快速查找和插入有序等特性。這種數據結構設計方法非常很值得我們在開發中借鑒使用。

本文轉載自微信公眾號「python學與思」，可以通過以下二維碼關注。轉載本文請聯系python學與思公眾號。