一文讓你徹底搞懂 Python 字典是怎麼實現的

楔子

上一篇文章我們介紹了列表的實現原理，那麼本次就來聊一聊字典。

首先字典是一種映射型容器對象，保存了鍵 (key) 到值 (value) 的映射關係。在 Python 裏面字典經過高度優化的，因爲不光我們在用，底層的虛擬機也在大量使用，所以通過字典可以實現鍵到值的快速查找，並且 JSON 這種數據結構也是借鑑了 Python 的字典。

在 Python 裏面我們要如何創建一個字典呢？

# 創建一個字典
d = {"a": 1, "b": 2}
print(d)
"""
{'a': 1, 'b': 2}
"""

# 或者我們還可以通過dict, 傳入關鍵字參數即可
d = dict(a=1, b=2, c=3, d=4)
print(d)  
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""

# 當然dict裏面還可以接收位置參數, 但是最多接收一個
d1 = dict({"a": 1, "b": 2}, c=3, d=4)
d2 = dict([("a", 1), ("b", 2)], c=3, d=4)
print(d1)  
print(d2)  
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""


# 還可以根據已有字典創建新的字典
d = {**{"a": 1, "b": 2}, "c": 3, **{"d": 4}}
print(d)  
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""

#當然通過dict也是可以的
#但是注意: **這種方式本質上是把字典變成多個關鍵字參數
#所以裏面的key一定要符合Python的變量命名規範
d = dict(**{"a": 1, "b": 2}, c=3, **{"d": 4})
print(d)  
"""
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
"""

try:
    # 這種是不合法的, 因爲**{1: 1}等價於1=1
    d = dict(**{1: 1})
except Exception as e:
    print(e)  # keywords must be strings
# 但下面是合法的
d = {**{1: 1, 2: 2}, **{(1, 2, 3): "嘿嘿"}}
print(d)  
"""
{1: 1, 2: 2, (1, 2, 3): '嘿嘿'}
"""

字典的底層是藉助哈希表實現的，什麼是哈希表我們一會兒說，總之字典添加元素、刪除元素、查找元素等操作的平均時間複雜度是 O(1)。當然了，在哈希不均勻的情況下，最壞時間複雜度是 O(n)，但這種情況很少發生。

那麼哈希表到底是什麼樣的數據結構，爲什麼能這麼快呢？下面來分析一下。

什麼是哈希表？

映射型容器的使用場景非常廣泛，基本上所有的主流語言都支持。例如：C++ 裏面的 map 就是一種映射型容器，但它是基於紅黑樹實現的。紅黑樹是一種平衡二叉樹，元素的插入、刪除、查詢等操作的時間複雜度均爲 O(logN)，另外 Linux 的 epoll 也使用了紅黑樹。

而對於 Python 來講，映射型容器指的就是字典，我們說字典在 Python 內部是被高度優化的。因爲不光我們在用，虛擬機在運行時也在大量使用，比如：自定義類、以及其實例對象都有自己的屬性字典，還有全局變量也是通過字典存儲的。因此基於以上種種原因，Python 對字典的性能要求會更加苛刻。

所以 Python 字典採用的數據結構，在添加、刪除、查詢元素等方面肯定是要優於紅黑樹的，沒錯，就是哈希表。其原理是將 key 通過哈希函數進行運算，得到一個哈希值，再將這個哈希值映射成索引。

我們舉例說明：

我們發現除了 key、value 之外，還有一個 index，因爲哈希表本質上也是使用了索引。雖然數組在遍歷的時候是個時間複雜度爲 O(n) 的操作，但通過索引定位元素則是一個時間複雜度爲 O(1) 的操作，不管數組有多長，通過索引總是能瞬間定位到指定元素。

所以哈希表實際上也是使用了數組的思想，將 key 映射成一個數值，作爲索引。至於它是怎麼映射的，我們後面再談，現在就假設是按照我們接下來說的方法映射的。

比如這裏有一個能容納 8 個元素的字典，如上圖所示。我們先設置 d["koishi"]=79，那麼會對 koishi 這個字符串進行哈希運算，得到一個哈希值，然後再讓哈希值對當前的總容量進行取模，這樣的話是不是能夠得到一個小於 8 的數呢？假設是 3，那麼就存在索引爲 3 的位置。

然後 d["scarlet"]=83，按照同樣的規則運算得到 6，那麼就存在索引爲 6 的位置；同理第三次設置 d["satori"]=80，對字符串 satori 進行哈希、取模，得到 1，那麼存儲在索引爲 1 的位置。

同理當我們根據鍵來獲取值的時候，比如：d["satori"]，那麼同樣會對字符串 satori 進行哈希、取模，得到索引發現是 1，然後就把索引爲 1 的 value 給取出來。

當然這種方式肯定存在缺陷，比如：

• 不同的 key 進行哈希、取模運算之後得到的結果一定是不同的嗎？

• 在運算之後得到索引的時候，發現這個位置已經有人佔了怎麼辦？

• 取值的時候，索引爲 1，可如果索引爲 1 對應的 key 和我們指定的 key 不一致怎麼辦？

所以哈希運算是會衝突的，如果衝突，那麼 Python 底層會改變策略重新映射，直到映射出來的索引沒有人用。比如我們設置一個新的鍵值對 d["tomoyo"]=88，可是 tomoyo 這個 key 映射之後得到的結果也是 1，而索引爲 1 的地方已經被 key 爲 satori 的鍵值對給佔了，那麼 Python 就會改變規則來對 tomoyo 重新運算，找到一個空位置進行添加。

但如果我們再次設置 d["satori"]=100，那麼對 satori 映射得到的結果也是 1，而 key 是一致的，那麼就會把對應的值進行修改。

同理，當我們獲取值的時候，比如 d["tomoyo"]，那麼對 key 進行映射，得到索引。但是發現該索引位置對應的 key 不是 tomoyo 而是 satori，於是改變規則（這個規則跟設置 key 衝突時，採用的規則是一樣的），重新映射，得到新的索引，然後發現 key 是一致的，於是將值取出來。

所以從這裏就已經能說明問題了，就是把 key 轉換成類似數組的索引。可能有人問，這些值貌似不是連續的啊。對的，肯定不是連續的。並不是說你先存，你的索引就小、就在前面，這是由 key 進行哈希運算之後的結果決定的。

另外哈希表、或者說字典也會擴容，並且它還不是像列表那樣，容量不夠才擴容，而當鍵值對個數達到容量的三分之二的時候就會擴容。

因爲字典不可能會像列表那樣，鍵值對之間是連續、一個一個挨在一起的。既然是哈希運算，得到的哈希值肯定是隨機的，再根據哈希值映射出的索引也是隨機的。那麼在鍵值對個數達到容量三分之二的時候，計算出來的索引發生碰撞的概率會非常大，不可能等到容量不夠了再去擴容，而是在鍵值對個數達到容量的三分之二時就要擴容，也就是申請一個更大的哈希表。

一句話總結：哈希表就是一種空間換時間的方法。

假設容量爲 1024，那麼就相當於數組的長度爲 1024 個位置，每個 key 都會映射成索引，找到自己的位置，將鍵值對存在裏面。但很明顯各自的位置是不固定的，肯定會空出來很多，但是無所謂，只要保證通過索引能在相應的位置找到它即可。

大量的文字會有些枯燥，我們來用兩張圖來解釋一下設置元****素和獲取元素的整個過程。

以上是設置元素，還是比較清晰的，果然圖像是個好東西。再來看看獲取元素：

以上就是哈希表的基本原理，這也是 Python 早期所採用的哈希表，但是它有一個嚴重的問題，就是內存浪費嚴重。接下來我們就來看看字典的底層結構，以及 Python 是如何對哈希表進行優化的。

字典的底層結構

下面我們來看看字典的底層實現，它對應的結構體是 PyDictObject，實現還是有點複雜的。

typedef struct {
    PyObject_HEAD
    Py_ssize_t ma_used;
    uint64_t ma_version_tag;
    PyDictKeysObject *ma_keys;
    PyObject **ma_values;
} PyDictObject;

解釋一下里面的字段的含義：

• PyObject_HEAD：定長對象的頭部信息，裏面包含了對象的引用計數和類型。

• ma_used：字典裏面鍵值對的個數，它充當了 ob_size。

• ma_version_tag：字典的版本號，對字典的每一次修改都會導致其改變；除此之外還有一個全局的字典版本計數器 pydict_global_version，任何一個字典的修改都會影響它；並且 pydict_global_version 會和最後操作的字典內部的 ma_version_tag 保持一致，當然這個成員我們沒必要關注，沒太大意義。

• ma_keys：從定義上來看它是一個指針，指向了 PyDictKeysObject。而 Python 裏面的哈希表分爲兩種，分別是 combined table 和 split table，即結合表和分離表。如果是結合表，那麼鍵值對全部由 ma_keys 維護，此時 ma_values 爲 NULL。

• ma_values：如果是分離表，那麼鍵由 ma_keys 維護，值由 ma_values 維護。而 ma_values 是一個二級指針，指向 PyObject * 類型的指針數組；

這裏先解釋一下結合表和分離表的由來。結合表的話，鍵和值就存在一起；分離表的話，鍵和值就存在不同的地方。那麼問題來了，爲什麼要將哈希表分爲兩種呢？事實上，早期的哈希表只有結合表這一種，並且現在創建一個字典使用的也是結合表。

from ctypes import *

class PyObject(Structure):
    _fields_ = [("ob_refcnt", c_ssize_t),
                ("ob_type", c_void_p)]

class PyDictObject(PyObject):

    _fields_ = [("ma_used", c_ssize_t),
                ("ma_version_tag", c_uint64),
                ("ma_keys", c_void_p),
                ("ma_values", c_void_p)]


d = {"a": 1, "b": 2}
print(
    PyDictObject.from_address(id(d)).ma_values
)  # None

我們看到 ma_values 打印的結果是一個 None，證明是結合表，值不是由 ma_values 維護，而是和鍵一起，都由 ma_keys 負責維護。

而分離表是在 PEP-0412 中被引入的，主要是爲了提高內存使用率，也就是讓不同的字典共享相同的一組 key。比如我們自定義類的實例對象，它們默認都有自己的屬性字典，如果對某個類多次實例化，那麼改成分離表會更有效率。因爲它們的屬性名稱是相同的，完全可以共享同一組 key；如果是結合表，那麼每個實例的屬性字典都要將相同的 key 單獨保存一次，這顯然是一種浪費。

from ctypes import *

class PyObject(Structure):
    _fields_ = [("ob_refcnt", c_ssize_t),
                ("ob_type", c_void_p)]

class PyDictObject(PyObject):

    _fields_ = [("ma_used", c_ssize_t),
                ("ma_version_tag", c_uint64),
                ("ma_keys", c_void_p),
                ("ma_values", c_void_p)]

class A:
    pass

a1 = A()
a2 = A()

#因爲類型我們指定的是 void *
#所以打印的就是一串地址
#我們看到輸出不爲None，說明採用的確實是分離表
print(
    PyDictObject.from_address(id(a1.__dict__)).ma_values,
    PyDictObject.from_address(id(a2.__dict__)).ma_values
)  # 2885727436352 2885727434960
#然後再查看ma_keys，既然是共享同一組key
#那麼它們的地址應該是一樣的
print(
    PyDictObject.from_address(id(a1.__dict__)).ma_keys,
    PyDictObject.from_address(id(a2.__dict__)).ma_keys
)  # 2886174469264 2886174469264

#結果確實是一樣的
#不同實例對象的屬性字典裏面的key是共享的
#因爲是同一個類的實例對象，屬性字典的key是相同的
#所以沒必要將同一組key保存多次

以上就是結合表和分離表之間的區別，只需要知道分離表是 Python 爲了提高內存使用率而專門引入的即可。我們平時自己創建的字典，使用的都是結合表，因此我們的重點也將會放在結合表身上。

而結合表的話，鍵值都由 ma_keys 維護，它是一個指向 PyDictKeysObject 的指針，因此玄機就隱藏在這個結構體裏面。

typedef struct _dictkeysobject PyDictKeysObject;

struct _dictkeysobject {
    Py_ssize_t dk_refcnt;
    Py_ssize_t dk_size;
    dict_lookup_func dk_lookup;
    Py_ssize_t dk_usable;
    Py_ssize_t dk_nentries;
    char dk_indices[];  
};

字段含義如下：

• dk_refcnt：key 的引用計數，也就是 key 被多少個字典所使用。如果是結合表，那麼該成員始終是 1，因爲結合表獨佔一組 key；如果是分離表，那麼該成員大於等於 1，因爲分離表可以共享一組 key；

• dk_size：哈希表大小，並且大小是 2 的 n 次方，這樣可將模運算優化成按位與運算；

• dk_lookup：探測函數，基於 key 的哈希值映射成索引。一個好的探測函數應該能儘量少的避免衝突，因爲它對哈希表的性能起着至關重要的作用。所以底層的探測函數有很多種，會根據對象的種類選擇最合適的一個。

• dk_usable：鍵值對數組的長度，關於什麼是鍵值對數組下面會解釋。

• dk_nentries：哈希表中已使用的 entry 數量，這個 entry 你可以理解爲鍵值對的載體，或者乾脆就理解爲鍵值對。

• dk_indices：哈希索引數組，後面會解釋。

• dk_entries：鍵值對數組，雖然結構體裏面沒有寫，但它確實存在，是一個 PyDictKeyEntry 類型的數組，用於存儲鍵值對、也就是上面說的 entry。所以這也說明了，字典的一個鍵值對，在底層就是一個 PyDictKeyEntry 結構體實例。

然後再來看看 PyDictKeyEntry 對象、也就是鍵值對長什麼樣子。

typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

顯然 me_key 和 me_value 指向了鍵和值，我們之前說 Python 的變量、以及容器內部的元素都是泛型指針 PyObject *，這裏也得到了證明。但是我們看到 entry 除了有鍵和值之外，還有一個 me_hash，它表示鍵對應的哈希值，這樣可以避免重複計算。

至此，字典的整個底層結構就非常清晰了。

字典的真正實現藏在 PyDictKeysObject 中，它的內部包含兩個關鍵數組：一個是哈希索引數組 dk_indices，另一個是鍵值對數組 dk_entries。

字典所維護的鍵值對 (entry) 會按照先來後到的順序保存在鍵值對數組中，而哈希索引數組則保存鍵值對在鍵值對數組中的索引。另外，哈希索引數組中的一個位置我們稱之爲一個槽，比如圖中的哈希索引數組便有 8 個槽，其數量由 dk_size 維護。

比如我們創建一個空字典，注意：雖然字典是空的，但是容量已經有了，然後往裏面插入鍵值對 "komeiji":99 的時候，Python 會執行以下步驟：

1. 將鍵值對保存在 dk_entries 中，由於初始字典是空的，所以會保存在 dk_entries 數組中索引爲 0 的位置。

2. 通過哈希函數計算出 "komeiji" 的哈希值，然後將哈希值映射成索引，假設是 5。

3. 將 "鍵值對" 在 "鍵值對數組" 中的索引 0，保存在哈希索引數組中索引爲 5 的槽裏面。

然後當我們在查找鍵 "komeiji" 對應的值的時候，便可瞬間定位。過程如下：

1. 通過哈希函數計算出 "komeiji" 的哈希值，然後映射成索引。因爲在設置的時候索引是 5，所以在獲取時，映射出來的索引肯定也是 5。

2. 找到哈希索引數組中索引爲 5 的槽，得到其保存的 0，這裏的 0 對應鍵值對數組的索引

3. 找到鍵值對數組中索引爲 0 的位置存儲的 entry，先比較 key、也就是 entry->me_key 是否一致，不一致則重新映射。如果一致，則取出 me_value，然後返回。

由於哈希值計算以及數組索引查找均是 O(1) 的時間複雜度，所以字典的查詢速度纔會這麼快。當然我們上面沒有涉及到索引衝突，關於索引衝突我們會在後面詳細說，但是鍵值對的存儲和獲取就是上面那個流程。

另外介紹哈希表的時候，爲了避免牽扯太多，說的相對簡化了。比如："xxx": 80，假設 "xxx" 映射出來的索引是 2，那麼鍵值對就直接存在索引爲 2 的地方。這實際上是簡化了，因爲這相當於把哈希索引數組和鍵值對數組合在一塊了，而早期的 Python 也確實是這麼做的。

但是從上面字典的結構圖中我們看到，實際上是先將鍵值對按照先來後到的順序存在一個數組 (鍵值對數組) 中，然後再將它在鍵值對數組中的索引存放在另一個數組 (哈希索引數組) 的某個槽裏面，因爲 "xxx" 映射出來的是 2，所以就存在索引爲 2 的槽裏面。

而在查找的時候，映射出來的索引 2 其實是哈希索引數組中的索引。然後索引爲 2 的槽又存儲了一個索引，這個索引是鍵值對數組中的索引，會再根據該索引從鍵值對數組裏面獲取指定的 entry。最後比較 key 是否相同、如果相同則返回指定的 value。

所以能看出兩者整體思想是基本類似的，理解起來區別不大，甚至第一種方式實現起來還更簡單一些。但爲什麼採用後者這種實現方式，以及這兩者之間的區別，我們一會再專門分析，之所以採用後者主要是基於內存的考量。

容量策略

因爲字典可以擴容，那麼字典肯定和列表一樣有着預分配機制，爲了避免頻繁申請內存，所以在擴容的是時候會將容量申請的比鍵值對個數要多一些。那麼字典的容量策略是怎麼樣的呢？

在 Object/dictobject.c 源文件中我們可以看到一個宏定義：

#define PyDict_MINSIZE 8

從這個宏定義中我們可以得知，一個字典的最小容量是 8，或者說內部哈希索引數組的長度最小是 8。

哈希表越密集，索引衝突則越頻繁，性能也就越差。因此哈希表必須是一種稀疏的表結構，越稀疏則性能越好。但由於內存開銷的制約，哈希表也不可能無限地稀疏，所以需要在時間和空間上進行權衡。

而實踐經驗表明，一個 1/2 到 2/3 滿的哈希表，性能較爲理想，能以相對合理的內存換取相對高效的執行性能。所以爲保證哈希表的稀疏程度，進而控制索引衝突的頻率，Python 通過宏 USABLE_FRACTION 將哈希表的元素控制在容量的 2/3 以內。

宏 USABLE_FRACTION 會根據哈希表的長度，計算哈希表可存儲的元素個數，也就是鍵值對數組的長度。以長度爲 8 的哈希表爲例，最多可以保存 5 個鍵值對，超出則需要擴容。

#define USABLE_FRACTION(n) (((n) << 1)/3)

哈希表規模一定是 2 的 n 次方，也就是說 Python 採用翻倍擴容的策略。例如長度爲 8 的哈希表擴容後，長度會變爲 16。另外，這裏的哈希表長度和哈希索引數組的長度是等價的。

哈希表的內存優化

在早期，哈希表並沒有分成兩個數組實現，而是隻由一個鍵值對數組實現，這個數組也承擔哈希索引數組的角色：

我們看到這種結構不正是我們在介紹哈希表時說的嗎？一個鍵值對數組既用來存儲，又用來充當索引，無需分成兩個步驟，而且這種方式也似乎更簡單、更直觀。沒錯，Python 在早期確實是通過這種方式實現的哈希表，只是這種實現方式有一個弊端，就是太耗費內存了。

因爲哈希表必須保持一定程度的稀疏，最多隻有 2/3 滿，這意味着至少要浪費 1/3 的空間。

所以 Python 爲了儘量節省內存，將鍵值對數組壓縮到原來的 2/3，只用來存儲，而對 key 進行映射得到的索引由另一個數組 (哈希索引數組) 來承載。假設映射的索引是 4，那麼就去找哈希索引數組中索引爲 4 的槽，該槽存儲的便是鍵值對在鍵值對數組中的索引。

之所以這麼設計，是因爲鍵值對數組裏面一個元素要佔用 24 字節，而哈希索引數組在容量不超過 255 的時候，裏面一個元素只佔一個字節；容量不超過 65535 的時候，裏面一個元素只佔兩個字節，其它以此類推。

所以哈希索引數組裏面的元素大小比鍵值對數組要小很多，將哈希表分成兩個數組 (避免鍵值對數組的浪費) 來實現會更加的節省內存。我們可以舉個例子計算一下，假設有一個容量爲 65535 的哈希表。

如果是通過第一種方式，只用一個數組來存儲的話：

# 總共需要1572840字節
>>> 65535 * 24
1572840  
# 除以3, 會浪費524280字節
>>> 65535  * 24 // 3
524280
>>>

如果是通過第二種方式，使用兩個數組來存儲的話：

#容量雖然是65535
#但鍵值對數組是容量的2 / 3
#然後加上哈希索引數組的大小
>>> 65535 * 24 * 2 // 3 + 65535 * 2
1179630
>>>

所以一個數組存儲比兩個數組存儲要多用 393210 字節的內存，因此 Python 選擇使用兩個數組來存儲。

最後再來提一下字典的順序問題，Python 從 3.6 開始，字典的遍歷是有序的，那麼這是怎麼實現的呢？

其實很簡單，在存儲時，雖然映射之後的索引是隨機的，但鍵值對本身始終是按照先來後到的順序被添加進鍵值對數組中。而字典在 for 循環時，會直接遍歷鍵值對數組，所以遍歷的結果是有序的。但即便如此，我們也不應該依賴此特性。

所以通過研究字典的具體實現，我們可以得到以下結論：

• 字典是一種高效的映射型容器，能夠以 O(1) 的時間複雜度執行查詢和寫入操作；

• 字典之所以這麼快，是因爲它由哈希表實現。但快是要付出代價的，哈希表必須保證一定的稀疏性，否則會頻繁出現索引衝突，導致哈希表性能下降，因爲在索引映射的時候是隨機的；

• 既然哈希表要保證稀疏性，就意味着內存開銷大，因爲會有內存浪費。所以爲平衡內存開銷與搜索效率，哈希表最好在 1/2 到 2/3 滿；

• 但 Python 爲優化內存使用，選擇使用兩個數組來實現哈希表，通過避免鍵值對數組的浪費，來減少內存佔用；

不過還沒有結束，哈希表的背後還隱藏了很多細節。比如：key 到底是如何映射成索引的？索引衝突了怎麼辦？哈希攻擊又是什麼？以及刪除元素也會面臨一些問題，又是如何解決的？

下面我們就來逐一回答。

對象的哈希值

Python 內置函數 hash 可以計算對象的哈希值，哈希表依賴於哈希值。而根據哈希表的性質，我們知道鍵對象必須滿足以下兩個條件，否則它無法容納在哈希表中。

• 哈希值在對象的整個生命週期內不可以改變；

• 可比較，如果兩個對象相等，那麼它們的哈希值一定相同；

滿足這兩個條件的對象便是可哈希 (hashable) 對象，只有可哈希對象纔可以作爲哈希表的鍵 (key)。因此像字典、集合等底層由哈希表實現的數據結構，其元素必須是可哈希對象。

Python 內置的不可變對象都是可哈希對象，比如：整數、浮點數、字符串、只包含不可變對象的元組等等；而像可變對象，比如列表、字典等等便不可作爲哈希表的鍵。

#鍵是可哈希的就行，值是否可哈希則沒有要求
>>> {1: 1, "xxx": [1, 2, 3], 3.14: 333}  
{1: 1, 'xxx': [1, 2, 3], 3.14: 333}
>>>
# 列表是可變對象，因此無法哈希
>>> {[]: 123}  
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>
# 元組也是可哈希的
>>> {(1, 2, 3): 123}  
{(1, 2, 3): 123}
#但如果元組裏麪包含了不可哈希的對象
#那麼整體也會變成不可哈希對象
>>> {(1, 2, 3, []): 123} 
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>>

而我們自定義類的實例對象也是可哈希的，並且哈希值是通過對象的地址計算得到的。

class A:
    pass

a1 = A()
a2 = A()
print(hash(a1), hash(a2)) 
"""
141215868971 141215869022
"""

當然 Python 也支持我們重寫哈希函數，比如：

class A:

    def __init__(self, name):
        self.name = name

    def __hash__(self):
        return 123

    def __repr__(self):
        return self.name

a1 = A("ping")
a2 = A("pong")

print(hash(a1), hash(a2))  # 123 123
print({a1: 1, a2: 2})  # {ping: 1, pong: 2}

我們看到雖然哈希值一樣，但是在作爲字典的鍵的時候，如果發生了衝突，會改變規則重新映射，因爲類的實例對象之間默認是不相等的。

注意：我們自定義類的實例對象默認都是可哈希的，但如果類裏面重寫了__eq__方法，且沒有重寫__hash__方法的話，那麼這個類的實例對象就不可哈希了。

class A:

    def __eq__(self, other):
        return True

a1 = A()
a2 = A()
try:
    print(hash(a1), hash(a2))
except Exception as e:
    print(e)  # unhashable type: 'A'

爲什麼會有這種現象呢？首先我們說，在沒有重寫__hash__的時候，哈希值默認是根據對象的地址計算得到的。而且對象如果相等，那麼哈希值一定是一樣的。

但是我們重寫了__eq__，相當於控制了 == 操作符的比較結果，兩個對象是否相等就是由我們來控制了，可哈希值卻還是根據地址計算得到的。因此兩個對象地址不同，哈希值不同，但是對象卻可以相等、又可以不相等，這就導致了矛盾。所以在重寫了__eq__、但是沒有重寫__hash__的情況下，其實例對象便不可哈希了。

但如果重寫了__hash__，那麼哈希值計算方式就不再通過地址計算了，因此此時是可以哈希的。

class A:

    def __init__(self, name):
        self.name = name

    def __hash__(self):
        return 123

    def __repr__(self):
        return self.name

    def __eq__(self, other):
        return True

a1 = A("ping")
a2 = A("pong")

print(hash(a1), hash(a2))  # 123 123
print({a1: 1, a2: 2})  # {ping: 2}

我們看到字典裏面只有一個元素，因爲重寫了__hash__方法之後，計算得到哈希值都是一樣的。如果沒有重寫__eq__，實例對象之間默認是不相等的。因此哈希值一樣，但是對象不相等，那麼會重新映射。但我們重寫了__eq__，返回的結果是 True，所以 Python 認爲對象是相等的，由於 key 的不重複性，保留了後面的鍵值對。

class A:

    def __init__(self, name):
        self.name = name

    def __hash__(self):
        return 123

    def __repr__(self):
        return self.name

    def __eq__(self, other):
        return False

a1 = A("ping")
a2 = A("pong")

# 我們看到 a1 == a1 爲 False
print(a1 == a1)  # False
# 但是隻保留了一個key，原因是地址一樣
# 在比較是否相等之前，會先判斷地址是否一樣
# 如果地址一樣，那麼認爲是同一個key
print({a1: 1, a1: 2})  # {ping: 2}

# 此時會保留兩個key
# 因爲 a1 和 a2 地址不同，a1 == a2 也爲False
# 所以哈希表認爲這是兩個不同的 key
# 但由於哈希值一樣，那麼映射出來的索引也一樣
# 因此寫入 a2:2 時相當於發生了索引衝突，於是會重新映射
# 但總之這兩個key都會被保留
print({a1: 1, a2: 2})  # {ping: 1, pong: 2}

同樣的，我們再來看一個 Python 字典的例子。

d = {1: 123}

d[1.0] = 234
print(d)  # {1: 234}

d[True] = 345
print(d)  # {1: 345}

天哪嚕，這是咋回事？首先整數在計算哈希值的時候，得到結果就是其本身；而浮點數顯然不是，但如果浮點數的小數點後面是 0，那麼它和整數是等價的。

因此 1 和 1.0 的哈希值一樣，並且兩者也是相等的，因此它們被視爲同一個 key，所以相當於是更新。同理 True 也一樣，因爲 bool 繼承自 int，所以它等價於 1，比如：9 + True = 10。因此 True 和 1 相等，並且哈希值也相等，那麼索引 d[True] = 345 同樣相當於更新。

但是問題來了，值更新了我們可以理解，字典裏面只有一個元素也可以理解，可爲什麼 key 一直是 1 呢？理論上最終結果應該是 True 纔對啊。其實這算是 Python 偷了個懶吧 (開個玩笑)，因爲 key 的哈希值是一樣的，並且也相等，所以 Python 不會對 key 進行替換。

從字典在設置元素的時候我們也知道，如果對 key 映射成索引之後，發現哈希索引數組的該槽沒有人用，那麼就按照先來後到的順序將鍵值對存儲在鍵值對數組中，再把它在鍵值對數組中的索引存在哈希索引數組的指定槽中。

但如果發現槽有人用了，那麼根據槽裏面存的索引，去鍵值對數組中查找指定的 entry，然後比較兩個 key 是否相等。如果對應的 key 不相等，則重新映射找一個新的槽；如果相等，則說明是同一個 key，那麼把 value 換掉即可。

所以在替換元素的整個過程中，根本沒有涉及到對鍵的修改，因此上面那個例子的最終結果，value 會變、但鍵依舊是 1，而不是 True。

總之理想的哈希函數必須保證哈希值儘量均勻地分佈於整個哈希空間中，越是相近的值，其哈希值差別應該越大。還是那句話，哈希函數對哈希表的好壞起着至關重要的作用。

索引衝突

不同的對象，計算出的哈希值有可能相同，即使哈希值不同，映射出的索引也可能相同。因爲與哈希值空間相比，哈希表的槽位是非常有限的。如果不同的對象在經過映射之後，得到的索引相同，或者說它們被映射到了同一個槽，那麼便發生了索引衝突。

解決索引衝突的常用方法有兩種：

• 分離鏈接法 (separate chaining)

• 開放尋址法 (open addressing)

其中 Python 採用的便是開放尋址法，下面來看看這兩種做法之間的區別。

分離鏈接法

分離鏈接法爲每個哈希槽維護一個鏈表，所有哈希到同一槽位的鍵都保存到對應的鏈表中：

如上圖所示，哈希表的每一個槽都連接着一個鏈表，初始狀態爲空，映射到哈希表同一個槽的鍵則保存在對應的鏈表中。而使用分離鏈接法的哈希表，一般都是基於一個數組實現。

開放尋址法

首先依舊是將 key 映射成索引，並存在哈希索引數組的槽中，若發現槽被佔了，那麼就嘗試另一個。

key2 被映射到索引爲 3 的槽時，發現這個坑被 key1 給佔了，所以只能重新找個坑了。但是爲什麼找到 5 呢？顯然在解決索引衝突的時候是有策略的，一般而言，如果是第 i 次嘗試，那麼會在首槽的基礎上加上一個偏移量 d(i)。比如映射之後的索引是 n，那麼首槽就是 n，然而索引爲 n 的槽被佔了，於是重新映射，而重新映射之後的索引就是 n+d(i)。

所以可以看出探測方式因函數 d(i) 而異，而常見的探測函數也有兩種：

• 線性探測 (linear probing)

• 平方探測 (quadratic probing)

線性探測很好理解，d(i) 是一個線性函數，例如 d(i)=2*i+1

假設哈希之後對應的槽是 1，但是被佔了，這個時候會在首槽的基礎上加一個偏移量 d(i)。第 1 次嘗試，偏移量是 2；第 2 次嘗試，偏移量是 4；第 3 次嘗試，偏移量是 6。然後再加上首槽的 1，所以嘗試之後的位置分別是 3、5、7。

平方探測也很好理解，d(i) 是一個平方函數，比如 i 的平方。如果是平方探測，假設首槽還是 1，那麼衝突之後重試的槽就是 1 + 1、1 + 4、1+ 9。

線性探測和平方探測都比較簡單，但從效果上來看，平方探測似乎更勝一籌。如果哈希表存在局部熱點，線性探測很難快速跳過熱點區域，而平方探測則可以解決這一點。但其實這兩種方法其實都不夠好，因爲固定的探測序列加大了衝突的概率。比如：

key1 和 key2 都映射到了索引爲 **1 **的槽，而由於探測序列是相同的，因此後續可能出現多次衝突。

所以 Python 對此進行了優化，探測函數會參考對象哈希值，生成不同的探測序列，進一步降低索引衝突的可能性：

Python 的這種做法被稱爲迭代探測，當然迭代探測也屬於開放尋址法的一種。所以當出現索引衝突時，Python 並不是簡簡單單地加上一個偏移量，而是使用專門設計的探測函數進行二次探查，也就是之前說的改變規則、重新映射，然後在函數內部會參考對象的哈希值來計算出一個新的索引。

探測函數

Python 爲哈希表搜索提供了多種探測函數，例如 lookdict, lookdict_unicode, lookdict_index，一般通用的是 lookdict。

lookdict_unicode 是專門針對 key 爲字符串的 entry，lookdict_index 針對 key 爲整數的 entry，可以把 lookdict_unicode 和 lookdict_index 看成是 lookdict 的特殊實現，只不過 key 是整數和字符串的場景非常常見，因此爲其單獨實現了一個函數。

當要存儲一個鍵值對時，會通過探測函數爲 key 尋找一個合適的槽，如果探測函數執行的時候發現索引衝突了，並且 key 還不相等，那麼會改變規則重新映射。也就是說，在探測函數里面，會不斷嘗試解決衝突，直到映射出一個可用的索引。

函數的具體源代碼，感興趣的話可以自己去查看，我這裏簡單說一下大致流程。

先用哈希函數計算出 key 的哈希值，然後作爲參數傳遞到探測函數中。在探測函數里面，會將哈希值和 mask 按位與得到索引。

mask 等於哈希表的容量減 1，這裏涉及到了一個小技巧，如果 n 是 2 的整數次冪，那麼 m % n 和 m & (n - 1) 是等價的，但按位與的速度要比取模快很多。所以哈希表的容量是 2 的整數次冪，就是爲了在映射索引的時候，將取模優化成按位與。

理想情況下，得到的索引是不衝突的。但如果衝突了，那麼探測函數內部會改變規則，重新映射，這裏的規則如下：

//將當前哈希值右移PERTURB_SHIFT個位
perturb >>= PERTURB_SHIFT;
//然後將哈希值加上 i*5 + 1，這個 i 就是當前衝突的索引
//運算之後的結果再和mask按位與，得到一個新的 i
//然後判斷變量 i 是否可用，不可用則重複當前邏輯
//直到出現一個可用的槽
i = (i*5 + perturb + 1) & mask;

至於爲什麼這麼做，可以認爲是 Python 總結出的經驗，這種做法在避免索引衝突時的表現比較好。總之在重新映射的時候，會參考對象的哈希值，探測序列因哈希值而異。

哈希攻擊

假設有一些想搞事的人向我們的接口傳遞了大量哈希值相同的 key，會發生什麼事情呢？顯然哈希表將頻繁發生索引衝突，探測函數會不斷地重新映射，從而導致性能由 O(1) 急劇下降爲 O(N)，這便是哈希攻擊。

哈希攻擊是一種 DOS 攻擊，一旦後端接口存在合適的攻擊面，攻擊者就能輕鬆讓服務器陷入癱瘓。而 Python 在 3.3 以前，就存在這種漏洞，當時哈希函數只根據對象本身計算哈希值。因此只要解釋器版本相同，對象哈希值也會相同，這是很危險的。

問題雖然很嚴重，但解決方法很簡單，直接往對象身上撒把鹽 (salt) 即可。解釋器啓動後，會產生一個隨機數作爲鹽，哈希函數同時參考對象本身以及隨機數計算哈希值。

這樣一來，攻擊者由於無法獲取解釋器內部的隨機數，也就無法構造出哈希值相同的 key 了。Python 自 3.3 以後，哈希函數均採用加鹽模式，杜絕了哈希攻擊的可能性。Python 哈希算法在 pyhash.c 源文件中實現，有興趣可以自己去了解一下，這裏就不展開了。

我們只需要知道索引衝突時，Python 是怎麼做的即可，至於如何設計一個哈希函數，以及 Python 底層使用的哈希函數的具體邏輯，就不在我們的展開範圍之內了。

哈希表能直接刪除元素嗎？

現在我們已經知道哈希表是先通過哈希函數計算出鍵的哈希值，然後將哈希值傳遞到探測函數中，再將哈希值映射爲一個索引，最終通過索引去訪問連續的內存區域。而哈希表這種數據結構，最終目的就是加速鍵的搜索過程。

並且我們知道，當鍵值對數量越多，在映射成索引之後就越容易出現衝突。而如果衝突了，就改變規則重新映射，這種方法叫做開放尋址法。當發生衝突時，在探測函數內部會參考哈希值以及衝突的索引，計算下一個候選位置，如果可用就設置進去。如果不可用，會繼續重複此過程，直到找到一個可用的位置。

通過多次探測，可以從一個位置到達多個位置，我們認爲這些位置就形成了一個衝突探測鏈 (探測序列)。比如當我們插入一個 key="satori" 的鍵值對時，在位置 a 發現不行，又走到位置 b，發現也被人佔了，於是到達位置 c，而位置 c 沒有鍵值對，於是就存在了這裏。

那麼經過以上流程，a -> b -> c 便形成了一條衝突探測鏈，同理我們查找的時候也會按照這個順序進行查找。

顯然上面這些東西，現在理解起來已經沒什麼難度了，但是問題來了。

如果我此時把上面位置 b 的 entry 給刪掉的話，會引發什麼後果？

首先當我們獲取 d["satori"] 時，肯定會先到達位置 a，發現存在 entry（鍵值對）、但 key 不是字符串 satori，於是重新映射；然後走到位置 b，發現還不對，再走到位置 c，發現 key 是 satori，於是就把值取出來了。顯然這符合我們的預期，但是，我要說但是了。

如果我們把位置 b 上的 entry 刪掉呢？那麼老規矩，映射成索引，先走到位置 a，但是發現坑被佔；於是又走到位置 b，結果發現居然沒有 entry，那麼直接就報出了一個 KeyError。

所以繼續尋找的前提是，這個地方要存儲了 entry，並且存在的 entry -> me_key 和指定的 key 不相同；但如果沒有的話，就說明根本沒有這個 key，直接 KeyError。

然而 satori 這個 key 確實是存在的，因此這種情況我們稱之爲探測鏈斷裂。本來應該走到位置 c 的，但由於位置 b 沒有元素，導致探測函數在位置 b 就停止了。

因此我們發現，當一個元素只要位於任何一條探測鏈當中，在刪除時都不能真正意義上的刪除。所以元素的刪除，其實是一種僞刪除操作。

//一個鍵值對就是一個entry
//在底層就是一個 PyDictKeyEntry 實例
typedef struct {
    Py_hash_t me_hash;
    PyObject *me_key;
    PyObject *me_value;
} PyDictKeyEntry;

而當一個 PyDictObject 對象發生變化時，其中的 entry 會在三種不同的狀態之間進行切換：unused 態、active 態、dummy 態。

unused 態

當一個 entry 的 me_key 和 me_value 都是 NULL 的時候，entry 處於 unused 態。unused 態表明該 entry 中並沒有存儲 key、value，並且在此之前也沒有存儲過它們，每一個 entry 在初始化的時候都會處於這個狀態。

不過 me_value 的話，即使不是 unused 態也可能爲 NULL，更準確的說不管何時它都可能會爲 NULL，這取決於哈希表到底是結合表、還是分離表。

如果是分離表的話，value 是不存在這裏的，只有 key 存在這裏，因此 me_value 永遠是 NULL。而如果是結合表，那麼 key 和 value 都存在這裏面。所以對於 me_key，只在 unused 態的時候纔可能爲 NULL。

active 態

當 entry 存儲了 key 時，那麼此時 entry 便從 unused 態變成了 active 態。

dummy 態

當某個 key 被刪除時，它所在的 entry 便從 active 態變成 dummy 態，否則就會發生我們之前說的探測鏈斷裂。至於這個 dummy 到底是啥，我們一會兒說。總之 entry 進入 dummy 態，就是我們剛纔提到的僞刪除技術。

當 Python 沿着某條探測鏈搜索時，如果發現一個 entry 處於 dummy 態，就會明白雖然當前的 entry 是無效的，但是後面的 entry 可能是有效的。所以不會報錯，而是會繼續搜索，這樣就保證了探測鏈的連續性。

至於報錯，是在找到了 unused 態的 entry 時纔會報錯，因爲這裏確實一直都沒有存儲過 key。但索引又是當前這個位置，因此指定的 key 就真的不存在哈希表中，此時纔會報錯。

以上是三種狀態之間的轉換，unused 態只能轉換爲 active 態；active 態只能轉換爲 dummy 態；dummy 態只能轉化爲 active 態。

當 entry 被使用時，它便由 unused 態轉爲 active 態，此時 me_key 由 NULL 變成非 NULL；當刪除某個 key 時，它所在的 entry 便由 active 態轉爲 dummy 態。

那麼問題來了，dummy 態轉爲 active 態，你能猜到會在什麼時候發生嗎？

很容易想到，如果新來了一個 key，這個 key 在存儲的時候發生衝突，也就是找到的 entry 存儲了別的 key，那麼會沿着衝突探測鏈繼續查找。在查找的時候要是遇到了處於 dummy 態的 entry，那麼該 entry 就會從 dummy 態變成 active 態。

換句話說，對於處於 dummy 態的 entry，Python 不會主動處理它，只是說這個元素被標記爲刪除了，但內存還會繼續佔用。如果新來的 key，沒有發生衝突，一上來就有位置可以存儲，那麼不會理會 dummy 態的 entry。

只有當發生衝突的時候，正好撞上了 dummy 態的 entry，纔會將 dummy 態的 entry 給替換掉。此時 entry 就變成了 active 態，然後內部維護的就是新的鍵值對。另外當哈希表滿了發生擴容的時候，會將所有的 active 態的 entry 都搬過去，而處於 dummy 態的 entry 則直接丟棄。

之所以可以丟棄，原因是 dummy 態的 entry 存在是爲了保證探測鏈不斷裂，但現在所有 active 態的 entry 都拷貝到新的內存當中了，它們會形成一條新的探測鏈，因此也就不需要這些 dummy 態的 entry 了。

所以再讓我們回顧一下字典的底層結構，它裏面有一個 ma_used 字段，維護的是鍵值對的數量；還有一個 dk_nentries，它維護鍵值對數組中已使用的 entry 數量，而這個 entry 又可以理解爲鍵值對。那麼問題來了，這兩者有什麼區別呢？

相信你已經猜到了，如果不涉及元素的刪除，那麼兩者的值會是一樣的。而一旦刪除某個已存在的 key，那麼 ma_used 會減 1，而 dk_nentries 則保持不變。

首先 ma_used 減 1 表示鍵值對數量相比之前少了一個，這顯然符合我們在 Python 裏面使用字典時的表現；但我們知道元素的刪除其實是僞刪除，會將對應的 entry 從 active 態變成 dummy 態，然而 entry 的總數量並沒有改變。

也就是說，ma_used 其實等於 active 態的 entry 總數；如果將 dk_nentries 減去 dummy 態的 entry 總數，那麼得到的就是 ma_used。所以這就是兩者的區別，我們對一個字典使用 len 函數，獲取的也是 ma_used，而不是 dk_nentries。

static Py_ssize_t
dict_length(PyDictObject *mp)
{
    return mp->ma_used;
}

小結

以上就是 Python 的字典，建議大家在工作中多多使用它，它的性能是非常高效的。因爲不光我們在用，虛擬機本身也在大量使用。那麼問題來了，虛擬機內部都有哪些結構使用了字典呢？這裏隨便舉兩個：

類和類的實例對象

class A:
    pass

# 類有自己的屬性字典
print(type(A.__dict__))
"""
<class 'mappingproxy'>
"""
# mappingproxy 本質上是對字典的一個封裝
# 屏蔽了字典增刪改操作，只允許讀取

# 類的實例對象有自己的屬性字典
print(type(A().__dict__))
"""
<class 'dict'>
"""

全局名字空間

Python 的所有全局變量都保存在一個字典中，我們可以通過 globals 函數獲取它。

# 等價於往字典中寫入一個鍵值對
name = "古明地覺"
# 等價於從字典中獲取
print(name)
print(globals()["name"])
"""
古明地覺
古明地覺
"""

globals()["address"] = "地靈殿"
print(address)
"""
地靈殿
"""

所以全局變量的存儲和寫入都是基於字典操作的，這就決定了字典必須經過高度優化。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/ub1PTpoM9NG1X9dLn00f-w