楔子

Python 的字典是一種映射型容器對象，保存了鍵（key）到值（value）的映射關系。通過字典，我們可以實現快速查找，JSON 這種數據結構也是借鑒了 Python 的字典。另外字典是經過高度優化的，因為 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)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}
print(d2)  # {'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}}
print(d)  # {1: 1, 2: 2}

字典的底層是借助哈希表實現的，關于哈希表我們一會兒說，總之字典添加元素、刪除元素、查找元素等操作的平均時間復雜度是 O(1)。

我們來測試一下字典的執行效率吧，看看它和列表之間的區別。

import time
import numpy as np

def test(count: int, value: int):
    """
    :param count: 循環次數
    :param value: 查詢的元素
    :return:
    """
    # 包含一千個隨機數的列表
    lst = list(np.random.randint(0, 2 ** 30, size=1000))
    # 基于列表構建一個字典
    d = dict.fromkeys(lst)

    # 查詢元素 value 是否在列表中，循環 count 次，并統計時間
    t1 = time.perf_counter()
    for _ in range(count):
        value in lst
    t2 = time.perf_counter()
    print("列表查詢耗時:", round(t2 - t1, 2))

    # 查詢元素 value 是否在字典中，循環 count 次，并統計時間
    t1 = time.perf_counter()
    for _ in range(count):
        value in d
    t2 = time.perf_counter()
    print("字典查詢耗時:", round(t2 - t1, 2))


# 分別查詢一千次、一萬次、十萬次、二十萬次
test(10 ** 3, 22333)
"""
列表查詢耗時: 0.13
字典查詢耗時: 0.0
"""
test(10 ** 4, 22333)
"""
列表查詢耗時: 1.22
字典查詢耗時: 0.0
"""
test(10 ** 5, 22333)
"""
列表查詢耗時: 12.68
字典查詢耗時: 0.01
"""
test(10 ** 5 * 2, 22333)
"""
列表查詢耗時: 25.72
字典查詢耗時: 0.01
"""

字典的查詢速度非常快，從測試中我們看到，隨著循環次數越來越多，列表所花費的總時間越來越長。但是字典由于查詢所花費的時間極少，查詢速度非常快，所以即便循環 50 萬次，花費的總時間也不過才 0.01 秒左右。

此外字典還有一個特點，就是它的快不會受到數據量的影響，從含有一萬個鍵值對的字典中查找，和從含有一千萬個鍵值對的字典中查找，兩者花費的時間幾乎是沒有區別的。

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

什么是哈希表

映射型容器的使用場景非常廣泛，基本上所有的主流語言都支持。例如 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"]=95，按照同樣的規則運算得到 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 都會映射成索引，找到自己的位置，將鍵值對存在里面。但很明顯各自的位置是不固定的，肯定會空出來很多，但是無所謂，只要保證通過索引能在相應的位置找到它即可。

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

圖片

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

圖片

以上就是哈希表的基本原理，說白了它就是個數組。存儲鍵值對的時候，先將 key 映射成索引，然后基于索引找到數組中的指定位置，將鍵值對存進去。

小結

目前介紹的正是 Python 早期所采用的哈希表，但是它有一個嚴重的問題，就是內存浪費嚴重。