Fluent Python 筆記（四）：字典和集合

目錄：

Fluent Python 筆記（一）：數據模型

Fluent Python 筆記（二）：序列基礎

Fluent Python 筆記（三）：高效操作序列

Fluent Python 筆記（四）：字典和集合

Fluent Python 筆記（五）：把函數當做對象

好久沒更了，最近忙成狗。

這次主要總結下字典和集合相關用法，以及底層實現機制。

字典（Dict）

dict 是 Python 最核心的內容，不僅在程序中廣泛應用，也是 Python 語言實現最基礎的部分。

模塊命名空間，類和實例的屬性，函數關鍵字參數，這些都是使用字典來實現的。

內置函數保存在 __builtins__.__dict__ 中。

作為如此重要的內容，Python 中的字典被高度優化過，後面會說到其底層實現機制。

構造方式示例：

>>> a = dict(one=1, two=2, three=3)n>>> b = {one: 1, two: 2, three: 3}n>>> c = dict(zip([one, two, three], [1, 2, 3]))n>>> d = dict([(two, 2), (one, 1), (three, 3)])n>>> e = dict({three: 3, one: 1, two: 2})n>>> a == b == c == d == enTruen

字典推導示例：

和列表推導一樣好用

>>> d = {n: n**2 for n in range(5)}n>>> print dn{0: 0, 1: 1, 2: 4, 3: 9, 4: 16}n

處理缺失key值的幾種方法：

• setdefault 方法

my_dict.setdefault(key, []).append(new_value)n

等同於：

if key not in my_dict:n my_dict[key] = []nnmy_dict[key].append(new_value)n

對於已經存在的字典，臨時使用此方法可以保證安全方便地使用鏈式操作。

• defaultdict

如果一開始就知道這個字典可能經常找不到key，想提供一個默認值，那麼可以使用 defaultdict。

工作原理：

當實例化一個 defaultdict 時，提供一個函數 default_factory，每次 __getitem__ 傳入不存在的 key 參數時，產生默認值。

例如：

如果使用

dd = defaultdict(list)n

如果 new_key 不在 dd中，那麼 dd[new_key]做了下面的事情：

1. 調用 list() 來創建新的 list
2. 把新創建的 list 插入 dd 並使用 new_key 作為 key
3. 返回 list 的引用

注意：defaultdict 的 default_factory 只在 __getitem__ 調用時調用併產生默認值，其他函數無效。

例如，如果 dd 是個 defaultdict，k 是缺失的 key，那麼 dd[k] 會調用 default_factory，但是 dd.get(k) 仍然返回 None。

• __missing__ 函數

__missing__ 函數在基本的 dict 類中沒有定義，但是 dict 知道它：如果你繼承了 dict 並提供了 __missing__ 函數，標準的 dict.__getitem__ 每次找不到 key 的時候就會調用它，而不是拋出

KeyError。

__missing__ 函數只被 __getitem__ ( e.g. d[k]) 調用。__missing__ 函數對於其他查找key的函數表現沒有影響，如 get 或者 __contains__ ( 實現了 in 操作符)。這就是之前提到的為什麼 defaultdict 的 default_factory 只在 __getitem__下工作。

簡單示例（繼承自 dict 是不推薦的，這裡只是為了說明 __missing__ 用法）：

把非 str 的 key 轉化為 str 來進行查找：

class StrKeyDict0(dict):n def __missing__(self, key):n if isinstance(key, str):n raise KeyError(key)n return self[str(key)]nn def get(self, key, default=None):n try:n return self[key]n except KeyError:n return defaultnn def __contains__(self, key):n return key in self.keys() or str(key) in self.keys()n

PS：類似於 k in my_dict.keys() 這種查找在 Python 3 中是非常高效的，即使是非常大的字典，因為 dict.keys() 返回的是一個 view。而在 Python 2 中，dict.keys() 返回的是 list，dict 比較大的時候，效率就比較低了。

常用映射模塊：

在 collections 中，除了 defaultdict 還有幾個常用的映射類型。

• collections.OrderedDict

根據插入順序來管理 key，遍歷 item 的順序可以預期。 popitem 默認返回第一個 item，但是如果調用

my_odict.popitem(last=True)，則彈出最後一個添加的條目。

• collections.Counter

持有每個 key 的數量，每次 update 一個已經有的 key 都會增加其數量。這個可以用來為可哈希的對象計數，或者用來作為多重集合（每個元素可以出現多次）。

>>> ct = collections.Counter(abracadabra)n>>> ctnCounter({a: 5, b: 2, r: 2, c: 1, d: 1})n>>> ct.update(aaaaazzz)n>>> ctnCounter({a: 10, z: 3, b: 2, r: 2, c: 1, d: 1})n>>> ct.most_common(2)n[(a, 10), (z, 3)]n

• collections.UserDict

純 Python 實現的映射，和標準的 dict 工作方式一樣，設計用來被繼承的，後面會詳述。

自定義映射類型：

如果現有的映射模塊都無法滿足你，你可能會考慮繼承 dict，實現特殊功能。然而最好的方式還是繼承 UserDict 。

UserDict 並不繼承自 dict，但是有個內部 dict 實例，叫做 data，持有實際的條目，這避免了編寫特殊函數如 __setitem__ 時可能產生的非預期遞歸，簡化了 __contains__ 的編寫。

前面 StrKeyDict0 更好的實現方式：

class StrKeyDict(collections.UserDict): n def __missing__(self, key):n if isinstance(key, str):n raise KeyError(key)n return self[str(key)]nn def __contains__(self, key):n return str(key) in self.datann def __setitem__(self, key, item):n self.data[str(key)] = itemn

這樣代碼更簡短了，而且多做了一件事：存儲所有的 key 為 str，避免了如果實例用非 str 的 key 更新可能導致的問題。

因為 UserDict 繼承自 MutableMapping，因此 StrKeyDict 也擁有了 MutableMapping 和 Mapping 中的函數。以下函數值得一提：

• MutableMapping.update

這個強大的函數可以直接調用，也被用在 __init__ 中從其他映射中，或者可迭代的 (key, value) 對中，或者關鍵字參數中載入實例。因為它使用 self[key] = value 來添加條目，最終調用了 __setitem__ 的實現。

• Mapping.get

不用像之前一樣自己實現了。

不可變映射：

從Python 3.3 開始，types 模塊提供了一個包裝類，叫做 MappingProxyType，給定一個映射，返回一個 mappingproxy 的實例，只讀，但是能跟蹤原映射的改變。

>>> from types import MappingProxyTypen>>> d = {1: A}n>>> d_proxy = MappingProxyType(d)n>>> d_proxynmappingproxy({1: A})n>>> d_proxy[1]nAn>>> d_proxy[2] = xnTraceback (most recent call last):nFile "<stdin>", line 1, in <module>nTypeError: mappingproxy object does not support item assignmentn>>> d[2] = Bn>>> d_proxynmappingproxy({1: A, 2: B})n>>> d_proxy[2]nBn>>>n

集合（Set）

集合的主要作用還是去重：

>>> l = [spam, spam, eggs, spam]n>>> set(l)n{eggs, spam}n>>> list(set(l))n[eggs, spam]n

集合元素必須是可哈希的，set 類型不是可哈希的，但是 frozenset 是的，所以你可以在

set 中加入 frozenset。

構造方式：

s = {1, 2, 3}ns = set()n

集合推導：

s = {x for x in range(1, 100) if x % 2}n

字典及集合底層實現

在 dict 或者 set 中進行查找的時間是微不足道的，無論多大，只要內存中放得下。

原因在於，dict 內部實現使用的是哈希表。

（哈希表在任何一本數據結構教材中都會有說明，有興趣的建議找本書看。如果你不知道該看哪一本，推薦這本 《數據結構與演算法分析:C語言描述(原書第2版)》）

哈希表是個稀疏數組。在標準的數據結構文本中，哈希表中的 cell 通常被叫做 buckets。

在一個 dict 的哈希表中，每個元素都有一個

bucket，它包含兩個域：

• 一個指向key的引用
• 一個指向value的引用

因為所有的 buckets 都是相同大小，訪問獨立的 bucket 通過索引就可以了。

Python 嘗試保持至少 1/3 的 bucket 是空的；如果哈希表太過於擁擠，則會被拷貝到一個新的位置，以便有更多的空間來放 bucket。

為了取得

my_dict[search_key] 的值， Python 調用

hash(search_key) 來獲取哈希值，然後使用這個數值最小標誌性的位作為 offset 來在哈希表中查找一個bucket（位的數量取決於當前表的大小）。如果找到的 bucket 是空的，則拋出

KeyError。否則，找到的 bucket 有一個條目 （found_key:found_value）然後Python檢查 search_key 和 found_key 是否相等。如果相等，則返回

found_value。

然而， 如果 search_key 和 found_key 不相等， 則 哈希碰撞。為了解決碰撞，演算法使用哈希中不同的位，用特定的方式處理，然後使用這個作為 offset 來查找另一個bucket。如果那個bucket是空的，則拋出KeyError，否則如果相等則返回，不等繼續處理碰撞。如下圖：

插入或者更新條目的過程是相同的，除了當找到空 bucket 時，放入新 item，當找到符合的 key 時，覆蓋原有 value。

此外，當插入 item 時，Python 會判斷哈希表是否太大，並在新的位置重新構建。隨著哈希表的增漲，哈希值中作為 offset 的位數也增加，這樣保持碰撞幾率較低。

這個實現看起來要做很多工作，但是即使是百萬個 item 在一個 dict 中，很多搜索也都沒有碰撞，每次搜索的的平均碰撞個數是1到2個。低於平均情況下，即使是最不走運的 key 也能在屈指可數的碰撞後被解決。

字典（Dict）實用工作結論

如果理解內部實現比較困難，那麼可以嘗試記住下面的結論。

• dict 的 key 必須是可哈希的

一個對象滿足下面所有條件時就是可哈希的：

1. 支持hash() 函數，並且通過hash()函數在整個生命周期中都返回相同的值。
2. 支持相等性判斷，通過 eq() 方法。
3. 如果 a == b is True 那麼 hash(a) ==
   hash(b) 必須也是 True。

如果你實現了一個類有

__eq__ 方法，那麼必須也實現一個 __hash__ ，因為必須保證上述第3點，否則就打破了哈希演算法，這樣 dict 和 set 就不能以可靠的方式處理你的對象。

如果自定義的

__eq__ 方法依賴於可變狀態，那麼 __hash__ 必須拋出

TypeError 如 unhashable type : MyClass

• dict 會使用較多的內存

因為dict內部使用哈希表，而且哈希表必須是稀疏的，因此它們不是空間高效的。

把 dict 替換為 tuple 從兩方面減少了內存使用：

1. 移除了每個記錄多餘的哈希表
2. 每個 record 不用單獨存儲欄位

• key 搜索非常快

dict 實現是一個空間換時間的典型。

我們可以在1s之內從1000萬條目中搜索200萬條目。

• key 的順序依賴於插入的順序
• 在 dict 中添加條目可能會改變已有 key 的順序

添加新條目到 dict 中時，Python解釋器可能會覺得字典的哈希表需要擴大，然後構建一個新的，更大的哈希表，並把現在的條目都加到新的裡面。這個過程可能會發生全新的碰撞，key的順序可能改變。這些是與具體實現相關的，無法預測。如果在迭代字典的過程中改變，可能不會遍歷所有條目。

如果你需要掃描並在字典中添加新條目，分為兩步做：

1. 從頭到尾讀取第一個dict，並把需要用到的改變放到第二個dict
2. 用first.update(second)

在Python 3 中， .keys(), .items(), .values() 都會返回字典 view，表現更像集合而不是

Python 2中的list。這些view也是動態的：他們不會複製dict的內容，並且會立刻反應出dict中的改變。

總結：

字典可以說是 Python 中最最最重要的數據結構，當你不清楚一個模塊的內部結構，你可以先把它想像成字典，多半沒錯。

字典的各種特殊需求，在 Python 中都有現成的模塊，或者約定俗稱的方式，想造輪子之前，先查一查，需不需要造，或者怎麼造比較合適。

集合和字典的底層實現是一樣的，早期 Python 中的集合就是用 key 和 value 相同的字典來實現的，因此它們的用法基本差不多。

推薦閱讀：