楔子

Python 的字典是一種映射型容器對象，保存了鍵（key）到值（value）的映射關系。通過字典，我們可以實現(xiàn)快速查找，JSON 這種數(shù)據(jù)結構也是借鑒了 Python 的字典。另外字典是經(jīng)過高度優(yōu)化的，因為 Python 底層也在大量地使用字典。

在 Python 里面我們要如何創(chuàng)建一個字典呢？

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

# 或者我們還可以調(diào)用 dict，傳入關鍵字參數(shù)即可
d = dict(a=1, b=2, c=3, d=4)
print(d)  # {'a': 1, 'b': 2, 'c': 3, 'd': 4}

# 當然 dict 里面還可以接收位置參數(shù)，但是最多接收一個
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}


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

# 當然通過調(diào)用 dict 也是可以的
# 但是注意：** 這種方式本質(zhì)上是把字典變成多個關鍵字參數(shù)
# 所以里面的 key 一定要符合 Python 的變量命名規(guī)范
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}

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

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

import time
import numpy as np

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

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

    # 查詢元素 value 是否在字典中，循環(huán) count 次，并統(tǒng)計時間
    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
"""

字典的查詢速度非?？?，從測試中我們看到，隨著循環(huán)次數(shù)越來越多，列表所花費的總時間越來越長。但是字典由于查詢所花費的時間極少，查詢速度非?？欤约幢阊h(huán) 50 萬次，花費的總時間也不過才 0.01 秒左右。

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

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

什么是哈希表

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

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

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

我們舉例說明：

圖片

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

所以哈希表本質(zhì)上就是一個數(shù)組，通過將 key 映射成一個數(shù)值，作為數(shù)組的索引，然后將鍵值對存在數(shù)組里面。至于它是怎么映射的，我們后面再談，現(xiàn)在就假設是按照我們接下來說的方法映射的。

比如這里有一個能容納 8 個元素的字典，如上圖所示。我們先設置 d["koishi"]=79，那么會對 "koishi" 這個字符串進行哈希運算，得到一個哈希值，然后再讓哈希值對當前的總?cè)萘窟M行取模，這樣的話是不是能夠得到一個小于 8 的數(shù)呢？假設是 3，那么就存在索引為 3 的位置。

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

同理當我們根據(jù)鍵來獲取值的時候，比如：d["satori"]，那么同樣會對字符串 "satori" 進行哈希、取模，得到索引發(fā)現(xiàn)是1，然后就把索引為 1 的 value 給取出來。

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

• 不同的 key 進行哈希、取模運算之后得到的結果一定是不同的嗎？
• 在運算之后得到索引的時候，發(fā)現(xiàn)這個位置已經(jīng)有人占了怎么辦？
• 取值的時候，索引為 1，可如果索引為 1 對應的 key 和我們指定的 key 不一致怎么辦？

所以哈希運算是會沖突的，如果沖突，那么 Python 底層會改變策略重新映射，直到映射出來的索引沒有人用。比如我們設置一個新的鍵值對 d["tomoyo"]=88，可是 "tomoyo" 這個 key 映射之后得到的結果也是 1，而索引為 1 的地方已經(jīng)被 key 為 "satori" 的鍵值對給占了，那么 Python 就會改變規(guī)則來對 "tomoyo" 重新映射，直到找到一個空位置。

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

同理，當我們獲取值的時候，比如 d["tomoyo"]，那么對 key 進行映射，得到索引。但是發(fā)現(xiàn)該索引對應的 key 不是 "tomoyo" 而是 "satori"，于是改變規(guī)則（這個規(guī)則跟設置 key 沖突時，采用的規(guī)則是一樣的），重新映射，得到新的索引，然后發(fā)現(xiàn) key 是一致的，于是將值取出來。

所以從這里就已經(jīng)能說明問題了，就是把 key 轉(zhuǎn)換成數(shù)組的索引?？赡苡腥藛?，這些鍵值對貌似不是連續(xù)的啊。對的，肯定不是連續(xù)的。并不是說你先存，你的索引就小、就在前面，這是由 key 進行哈希運算之后的結果決定的。

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

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

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

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

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

圖片

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

圖片

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

小結

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