本篇主要介紹dict和set的高級用法以及它們背後的哈希表。

1. 前言

dict類型不但在各種程序中廣泛使用，它也是Python的基石。模塊的命名空間、實例的屬性和函數的關鍵字參數等都用到了dict。與dict先關的內置函數都在__builtins__.__dict__模塊中。

由於字典至關重要，Python對其實現做了高度優化，而散列表（哈希函數，Hash）則是字典性能突出的根本原因。而且集合(set)的實現也依賴於散列表。

本片的大綱如下：

• 常見的字典方法；

• 如何處理找不到的鍵；

• 標準庫中dict類型的變種；

• set和frozenset類型；

• 散列表工作原理；

• 散列表帶來的潛在影響（什麼樣的數據可以作為鍵、不可預知的順序等）。

2. 字典

和上一篇一樣，先來看看collections.abc模塊中的兩個抽象基類：Mapping和MutableMapping。它們的作用是為dict和其他類似的類型定義形式接口:

然而，非抽象映射類型一般不會直接繼承這些抽象基類，它們會直接對dict或者collections.UserDict進行擴展。

2.1 創建字典

首先總結下常用的創建字典的方法：

2.2 字典推導

列表推導和生成器表達式可以用在字典上。字典推導（dictcomp）可從任何以鍵值對作為元素的可迭代對象中構建出字典。

2.3 兩個重要的映射方法update和setdefault

2.3.1 update方法

它的參數列表如下：

update方法處理參數m的方法是典型的“鴨子類型”。該方法首先檢測m是否有keys方法，如果有，那麼update方法就把m當做映射對象來處理（即使它並不是映射對象）；否則退一步，把m當做包含了鍵值對(key, value)元素的迭代器。

Python中大多數映射類的構造方法都採用了類似的邏輯，因此既可用一個映射對象來新建一個映射對象，也可以用包含(key, value)元素的可迭代對象來初始化一個映射對象。

2.3.2 setdefault處理不存在的鍵

當更新字典時，如果遇到原字典中不存在的鍵時，我們一般最開始會想到如下兩種方法：

以上兩種方法至少進行2次鍵查詢，如果鍵不存在，第一種方法要查詢3次，非常低效。但如果使用setdefault方法，則只需一次就可以完成上述操作：

2.4 映射的彈性鍵查詢

上述的setdefault方法在每次調用時都要我們手動指定默認值，那有沒有什麼辦法能方便一些，在鍵不存在時，直接返回我們指定的默認值？兩個常用的方法是：①使用defaultdict類；②自定義一個dict子類，在子類中實現__missing__方法，而這個方法又有至少兩種方法。

2.4.1 defaultdict類

collections.defaultdict能優雅的解決3.3.2中的問題：

在實例化defaultdict時，需要給構造方法提供一個可調用對象（實現了__call__方法的對象），這個可調用對象存儲在defaultdict類的屬性default_factory中，當__getitem__找不到所需的鍵時就會通過default_factory來調用這個可調用對象來創建默認值。

上述代碼中 my_dict[key] 的內部過程如下(假設key是新鍵)：

1. 調用list()來創建一個新列表；

2. 把這個新列表作為值，key作為它的鍵，放到my_dict中；

3. 返回這個列表的引用。

注意：

• 如果在實例化defaultdict時未指定default_factory，那麼在查詢不存在的鍵時則會觸發KeyError；

• defaultdict中的default_factory只會在__getitem__裡被調用，在其它的方法裡完全不會發揮作用！比如，dd是個defaultdict，k是個不存在的鍵，dd[k]這個表達式則會調用default_factory，並返回默認值，而dd.get(k)則會返回None。

特殊方法__missing__

其實上述的功能都得益於特殊方法__missing__，實際調用default_factory的就是該特殊方法，且該方法只會被__getitem__調用。即：

下面通過編寫一個繼承自dict的類來說明如何使用__missing__實現字典查詢，不過這裡並沒有在找不到鍵時調用一個可調用對象，而是拋出異常。

2.4.2 自定義映射類：繼承自dict

某些情況下可能希望在查詢字典時，映射裡的鍵通通轉換成str類，但為了方便，也允許使用非字符串作為建，比如我們希望實現如下效果：

以下便是這個類的實現：

說明：

• 第3行：這裡的isinstance(key, str)測試是必需的。如果沒有這個測試，那麼當str(key)是個不存在的鍵時便會發生無限遞歸，因為第4行self[str(key)]會調用__getitem__，進而又調用__missing__，然後一直重複下去。

• 第13行：為了保持一致性，__contains__方法在這裡也是必需的，因為k in d這個操作會調用該方法。但是從dict繼承到的__contains__方法在找不到鍵的時候不會調用__missing__（間接調用，不會直接調用）。

• 第14行：這裡並沒有使用更具Python風格的寫法：key in my_dict，因為這樣寫會使__contains__也發生遞歸調用，所以這裡採用了更顯式的方法 key in self.keys。同時需要注意的是，這裡有兩個判斷，因為我們本沒有強行限制所有的鍵都必須是str，所以字典中可能存在非字符串的鍵（key in self.keys()）。

• 像k in my_dict.keys()這種操作在Python3中很快，即使映射類型對象很龐大也很快，因為dict.keys()返回的是一個”視圖“，在視圖中查找一個元素的速度很快。

2.4.3 子類化UserDict

如果要自定義一個映射類型，更好的策略是繼承collections.UserDict類。它是把標準dict用純Python又實現了一遍。之所以更傾向於從UserDict而不是從dict繼承，是因為後者有時會在某些方法的實現上走一些捷徑，導致我們不得不在它的子類中重寫這些方法，而UserDict則沒有這些問題。也正是由於這個原因，如果上個例子要實現將所有的鍵都轉換成字符串，還需要做很多工作，而從UserDict繼承則能很容易實現。

注意

下面使用UserDict來實現一遍StrKeyDict，它實現了__setitem__方法，將所有的鍵都轉換成str。注意這裡並沒有自行實現get方法，原因在後面。

因為UserDict繼承自MutableMapping，所以StrKeyDict裡剩下的映射類型的方法都是從UserDict、MutableMapping和Mapping繼承而來，這些方法中有兩個值得關注：

MutableMapping.update：

這個方法不但可以直接用，它還用在__init__裡，使其能支持各種格式的參數。而這個update方法內部則使用self[key] = value來添加新值，所以它其實是在使用我們定義的__setitem__方法。

Mapping.get：

對比StrKeyDict0和StrKeyDict的代碼可以發現，我們並沒有為後者定義get方法。前者如果不定義get方法，則會出現如下情況：

而在StrKeyDict中則沒有必要，因為UserDict繼承了Mapping的get方法，而查看源代碼可知，這個方法的實現和StrKeyDict0.get一模一樣。

2.5 其他字典

2.5.1 collections.OrderedDict

這個類型在添加鍵的時候會保持原序，即對鍵的迭代次序就是添加時的順序。它的popitem方法默認刪除並返回字典中的最後一個元素。值得注意的是，從Python3.6開始，dict中鍵的順序也保持了原序。但出於兼容性考慮，如果要保持有序，還是推薦使用OrderedDict。

2.5.2 collections.ChainMap

該類型可容納多個不同的映射對象，然後在查找元素時，這些映射對象會被當成一個整體被逐個查找。這個功能在給有嵌套作用域的語言做解釋器的時候很有用，可以用一個映射對象來代表一個作用域的上下文。

2.5.3 collections.Counter

這個類會給鍵準備一個整數計數器，每次更新一個鍵時就會自動增加這個計數器。所以這個類型可以用來給可散列對象計數，或者當成多重集來使用（相同元素可以出現不止一次的集合）。

2.5.4 不可變映射類型

標準庫中所有的映射類型都是可變的，但有時候會有這樣的需要，比如不能讓用戶錯誤地修改某個映射。從Python3.3開始，types模塊中引入了一個封裝類MappingProxyType。如果給這個類一個映射，它返回一個只讀的映射視圖。雖然是個只讀視圖，但它是動態的，如果原映射被修改，我們也能通過這個視圖觀察到變化。以下是它的一個例子：

3. 集合

和前面的字典一樣，先來看看集合的超類的繼承關係：

集合的本質是許多唯一對象的聚集。即，集合可以用於去重。集合中的元素必須是可散列的，set類型本身是不可散列的，但是frozenset可以。也就是說可以創建一個包含不同frozenset的set。

集合的操作

注意兩個概念：字面量句法，構造方法：

字面量句法相對於構造方法更快更易讀。後者速度之所以慢是因為Python必須先從set這個名字來查詢構造方法，然後新建一個列表，最後再把這個列表傳入到構造方法裡。而對於字面量句法，Python會利用一個專門的叫做BUILD_SET的字節碼來創建集合。

集合的字面量——{1}，{1, 2}等——看起來和它的數學形式一模一樣。但要注意空集，如果要創建一個空集，只能是 temp = set()，而不是 temp = {}，後者創建的是一個空字典。

frozenset的標準字符串表示形式看起來就像構造方法調用一樣：

對於frozenset，一旦創建便不可更改，常用作字典的鍵的集合。

除此之外，集合還實現了很多基礎的中綴運算符，如交集a & b，合集a | b，差集a - b等，還有子集，真子集等操作，由於這類操作太多，這裡不再一一列出。下面代碼得到兩個可迭代對象中共有的元素個數，這是一個常用操作：

集合推導

和列表推導，字典推導一樣，集合也有推導（setcomps）：

4. dict和set的背後

有人做過實驗（就在普通筆記本上），在1,000,000個元素中找1,000個元素，dict與set兩者的耗時比較接近，大約為0.000337s，而使用列表list，耗時是97.948056s，list的耗時是dict和set的約29萬倍。而造成這種差距的最根本的原因是，list中找元素是按位置一個一個找（雖然有像折半查找這類的算法，但本質依然是一個位置接一個位置的比較），而dict是根據某個信息直接計算元素的位置，顯然後者速度要比挨個找快很多。而這個計算方法統稱為哈希函數（hash），即 hash(key)–>position。

礙於篇幅，關於哈希算法的原理（哈希函數的選擇，衝突的解決等）這裡便不再贅述，相信經常和算法打交道或者考過研的老鐵們一定不陌生。

哈希表（也叫散列表）其實是個稀疏數組（有很多空元素的數組），每個單元叫做表元（bucket），Python中每個表元由對鍵的引用和對值的引用兩部分組成。因為所有表元的大小一致，所以當計算出位置後，可以通過偏移量來讀取某個元素（變址尋址）。

Python會設法保證大概還有三分之一的表元是空的，當快要達到這個閾值的時候，原有的哈希表會被複制到一個更大的空間中。

4.1 哈希值和相等性

如果要把一個對象放入哈希表中，首先要計算這個元素的哈希值。Python中可以通過函數hash()來計算。內置的hash()可用於所有的內置對象。如果是自定義對象調用hash()，實際上運行的是自定義的__hash__。如果兩個對象在比較的時候相等的，那麼它們的哈希值必須相等，否則哈希表就不能正常工作。比如，如果 1 == 1.0 為真，那麼hash(1) == hash(1.0)也必須為真，但其實這兩個數字的內部結構完全不一樣。而相等性的檢測則是調用特殊方法__eq__。

_補充_：從Python3.3開始，為了防止DOS攻擊，str、bytes和datetime對象的哈希值計算過程中多了隨機的“加鹽”步驟。所加的鹽值是Python進程中的一個常量，但每次啟動Python解釋器都會生成一個不同的鹽值。

4.2 Python中的哈希算法

為獲取my_dict[search_key]背後的值（不是哈希值），Python首先會調用hash(search_key)計算哈希值，然後取這個值最低的幾位數字當作偏移量（這只是一種哈希算法）去獲取所要的值，如果發生了衝突，則再取哈希值的另外幾位，知道不衝突為止。

在插入新值的時候，Python可能會按照哈希表的擁擠程度來決定是否要重新分配內存為它擴容。如果增加了散列表的大小，散列值所佔的位數和用作索引的位數都會隨之增加（目的是為了減少衝突發生的概率）。

這個算法看似費事，但實際上就算dict中有數百萬個元素，多數的搜索過程中並不會發生衝突，平均下來每次搜索可能會有一到兩次衝突。

4.3 dict的優劣

1、鍵必須是可散列的

一個可散列對象必須滿足一下要求：

（1）支持hash()函數，並且通過__hash__()方法得到的哈希值是不變的；

（2）支持通過__eq__()方法來檢測相等性；

（3）若 a == b為真，則 hash(a) == hash(b)也必須為真。

所有自定義的對象默認都是可散列的，因為它們的哈希值有id()函數來獲取，而且它們都是不相等的。如果你實現了一個類的__eq__方法，並且希望它是可散列的，那請務必保證這個類滿足上面的第3條要求。

2、字典在內存上的開銷巨大

典型的用空間換時間的算法。因為哈希表是稀疏的，這導致它的空間利用率很低。

如果需要存放數量巨大的記錄，那麼放在由元組或命名元組構成的列表中會是比較好的選擇；最好不要根據JSON的風格，用由字典組成的列表來存放這些記錄。

用元組代替字典就能節省空間的原因有兩個：①避免了哈希表所耗費的空間；②無需把記錄中字段的名字在每個元素裡都存一遍。

關於空間優化：如果你的內存夠用，那麼空間優化工作可以等到真正需要的時候再開始，因為優化往往是可維護性的對立面。

3、鍵查詢很快

本節最開始的實驗已經證明，字典的查詢速度非常快。如果再簡單計算一下，上面的實驗中，在有1000萬個元素的字典裡，每秒能進行200萬次鍵查詢。

這裡之所以說的是“鍵查詢”，而不是“查詢”，是因為有可能值的數據不在內存，內在磁盤中。一旦涉及到磁盤這樣的低速設備，查詢速度將大打折扣。

4、鍵的次序取決於添加順序

當往dict裡添加新鍵而又發生衝突時，新鍵可能會被安排存放到另一個位置。並且同一組數據，每次按不同順序進行添加，那麼即便是同一個鍵，同一個算法，最後的位置也可能不同。最典型的就是這組數據全衝突（所有的hash值都一樣），然後採用的是線性探測再散列解決衝突，這時的順序就是添加時的順序。

5、向字典中添加新鍵可能會改變已有鍵的順序。

無論何時往字典中添加新的鍵，Python解釋器都有可能做出擴容的決定。擴容時，在將原有的元素添加到新表的過程中就有可能改變原有元素的順序。如果在迭代一個字典的過程中同時對修改字典，那麼這個循環就很有可能會跳過一些鍵。

_補充_：Python3中，.keys()、.items()和.values()方法返回的都是字典視圖。

4.4 set的實現

set和frozenset也由哈希表實現，但它們的哈希表中存放的只有元素的引用（類似於在字典裡只存放了鍵而沒放值）。在set加入到Python之前，都是把字典加上無意義的值來當集合用。5.3中對字典的幾個特點也同樣適用於集合。

5. 總結

字典是Python的基石。除了基本的dict，標準庫中還有特殊的映射類型：defaultdict、OrderedDict、ChainMap、Counter和UserDict，這些類都在collections模塊中。

大多數映射都提供了兩個強大的方法：setdefault和update。前者可避免重複搜索，後者可批量更新。

在映射類型的API中，有個很好用的特殊方法__missing__，可以通過這個方法自定義當對象找不到某個鍵時的行為。

set和dict的實現都用到了哈希表，兩者的查找速度都很快，但空間消耗大，典型的以空間換時間的算法。

閱讀更多 VPointer701 的文章

關鍵字: JSON 而散 前言