本篇主要介紹：常見(jiàn)的字典方法、如何處理查不到的鍵、標(biāo)準(zhǔn)庫(kù)中 dict 類型的變種、散列表的工作原理等。一下是全部?jī)?nèi)容：

泛映射類型

collections.abc 模塊中有 Mapping 和 MutableMapping 這兩個(gè)抽象基類，它們的作用是為 dict 和其他類似的類型定義形式接口。

標(biāo)準(zhǔn)庫(kù)里所有映射類型都是利用 dict 來(lái)實(shí)現(xiàn)的，它們有個(gè)共同的限制，即只有可散列的數(shù)據(jù)類型才能用做這些映射里的鍵。

問(wèn)題： 什么是可散列的數(shù)據(jù)類型？

在 python 詞匯表（https://docs.python.org/3/glossary.html#term-hashable）中，關(guān)于可散列類型的定義是這樣的：

如果一個(gè)對(duì)象是可散列的，那么在這個(gè)對(duì)象的生命周期中，它的散列值是不變的，而且這個(gè)對(duì)象需要實(shí)現(xiàn) __hash__() 方法。另外可散列對(duì)象還要有 __eq__() 方法，這樣才能跟其他鍵做比較。如果兩個(gè)可散列對(duì)象是相等的，那么它們的散列只一定是一樣的

根據(jù)這個(gè)定義，原子不可變類型（str，bytes和數(shù)值類型）都是可散列類型，frozenset 也是可散列的（因?yàn)楦鶕?jù)其定義，frozenset 里只能容納可散列類型），如果元組內(nèi)都是可散列類型的話，元組也是可散列的（元組雖然是不可變類型，但如果它里面的元素是可變類型，這種元組也不能被認(rèn)為是不可變的）。

一般來(lái)講，用戶自定義的類型的對(duì)象都是可散列的，散列值就是它們的 id() 函數(shù)的返回值，所以這些對(duì)象在比較的時(shí)候都是不相等的。（如果一個(gè)對(duì)象實(shí)現(xiàn)了 eq 方法，并且在方法中用到了這個(gè)對(duì)象的內(nèi)部狀態(tài)的話，那么只有當(dāng)所有這些內(nèi)部狀態(tài)都是不可變的情況下，這個(gè)對(duì)象才是可散列的。）

根據(jù)這些定義，字典提供了很多種構(gòu)造方法，https://docs.python.org/3/library/stdtypes.html#mapping-types-dict 這個(gè)頁(yè)面有個(gè)例子來(lái)說(shuō)明創(chuàng)建字典的不同方式。

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

除了這些方法以外，還可以用字典推導(dǎo)的方式來(lái)建造新 dict。

字典推導(dǎo)

自 Python2.7 以來(lái)，列表推導(dǎo)和生成器表達(dá)式的概念就移植到了字典上，從而有了字典推導(dǎo)。字典推導(dǎo)（dictcomp）可以從任何以鍵值對(duì)作為元素的可迭代對(duì)象中構(gòu)建出字典。

比如：

>>> data = [(1, 'a'), (2, 'b'), (3, 'c')]
>>> data_dict = {num: letter for num, letter in data}
>>> data_dict
{1: 'a', 2: 'b', 3: 'c'}

常見(jiàn)的映射方法

下表為我們展示了 dict、defaultdict 和 OrderedDict 的常見(jiàn)方法（后兩種是 dict 的變種，位于 collections模塊內(nèi)）。

default_factory 并不是一個(gè)方法，而是一個(gè)可調(diào)用對(duì)象，它的值 defaultdict 初始化的時(shí)候由用戶設(shè)定。 OrderedDict.popitem() 會(huì)移除字典最先插入的元素（先進(jìn)先出）；可選參數(shù) last 如果值為真，則會(huì)移除最后插入的元素（后進(jìn)先出）。用 setdefault 處理找不到的鍵

當(dāng)字典 d[k] 不能找到正確的鍵的時(shí)候，Python 會(huì)拋出異常，平時(shí)我們都使用d.get(k, default) 來(lái)代替 d[k]，給找不到的鍵一個(gè)默認(rèn)值，還可以使用效率更高的 setdefault

my_dict.setdefault(key, []).append(new_value)
# 等同于
if key not in my_dict:
 my_dict[key] = []
my_dict[key].append(new_value)

這兩段代碼的效果一樣，只不過(guò)，后者至少要進(jìn)行兩次鍵查詢，如果不存在，就是三次，而用 setdefault 只需一次就可以完成整個(gè)操作。

那么，我們?nèi)≈档臅r(shí)候，該如何處理找不到的鍵呢？

映射的彈性查詢

有時(shí)候，就算某個(gè)鍵在映射里不存在，我們也希望在通過(guò)這個(gè)鍵讀取值的時(shí)候能得到一個(gè)默認(rèn)值。有兩個(gè)途徑能幫我們達(dá)到這個(gè)目的，一個(gè)是通過(guò) defaultdict 這個(gè)類型而不是普通的 dict，另一個(gè)是給自己定義一個(gè) dict 的子類，然后在子類中實(shí)現(xiàn) __missing__ 方法。

defaultdict：處理找不到的鍵的一個(gè)選擇

首先我們看下如何使用 defaultdict ：

import collections

index = collections.defaultdict(list)
index[new_key].append(new_value)

這里我們新建了一個(gè)字典 index，如果鍵 new_key 在 index 中不存在，表達(dá)式 index[new_key] 會(huì)按以下步驟來(lái)操作：

調(diào)用 list() 來(lái)建立一個(gè)新的列表把這個(gè)新列表作為值，'new_key' 作為它的鍵，放入 index 中返回這個(gè)列表的引用。

而這個(gè)用來(lái)生成默認(rèn)值的可調(diào)用對(duì)象存放在名為 default_factory 的實(shí)例屬性中。

defaultdict 中的 default_factory 只會(huì)在 getitem 里調(diào)用，在其他方法中不會(huì)發(fā)生作用。比如 index[k] 這個(gè)表達(dá)式會(huì)調(diào)用 default_factory 創(chuàng)造的某個(gè)默認(rèn)值，而 index.get(k) 則會(huì)返回 None。（這是因?yàn)樘厥夥椒?missing 會(huì)在 defaultdict 遇到找不到的鍵的時(shí)候調(diào)用 default_factory，實(shí)際上，這個(gè)特性所有映射方法都可以支持）。

特殊方法 missing

所有映射在處理找不到的鍵的時(shí)候，都會(huì)牽扯到 missing 方法。但基類 dict 并沒(méi)有提供 這個(gè)方法。不過(guò)，如果有一個(gè)類繼承了 dict ，然后這個(gè)繼承類提供了 missing 方法，那么在 getitem 碰到找不到鍵的時(shí)候，Python 會(huì)自動(dòng)調(diào)用它，而不是拋出一個(gè) KeyError 異常。

__missing__ 方法只會(huì)被 __getitem__ 調(diào)用。提供 missing 方法對(duì) get 或者 __contains__(in 運(yùn)算符會(huì)用到這個(gè)方法)這些方法的是有沒(méi)有影響。

下面這段代碼實(shí)現(xiàn)了 StrKeyDict0 類，StrKeyDict0 類在查詢的時(shí)候把非字符串的鍵轉(zhuǎn)化為字符串。

class StrKeyDict0(dict): # 繼承 dict
 def __missing__(self, key):
 if isinstance(key, str):
  # 如果找不到的鍵本身就是字符串，拋出 KeyError 
  raise KeyError(key)
 # 如果找不到的鍵不是字符串，轉(zhuǎn)化為字符串再找一次
 return self[str(key)]
 def get(self, key, default=None):
 # get 方法把查找工作用 self[key] 的形式委托給 __getitem__，這樣在宣布查找失敗錢，還能通過(guò) __missing__ 再給鍵一個(gè)機(jī)會(huì)
 try:
  return self[key]
 except KeyError:
  # 如果拋出 KeyError 說(shuō)明 __missing__ 也失敗了，于是返回 default 
  return default
 def __contains__(self, key):
 # 先按傳入的鍵查找，如果沒(méi)有再把鍵轉(zhuǎn)為字符串再找一次
 return key in self.keys() or str(key) in self.keys()

contains 方法存在是為了保持一致性，因?yàn)?k in d 這個(gè)操作會(huì)調(diào)用它，但我們從 dict 繼承到的 contains 方法不會(huì)在找不到鍵的時(shí)候用 missing 方法。

my_dict.keys() 在 Python3 中返回值是一個(gè) "視圖","視圖"就像是一個(gè)集合，而且和字典一樣速度很快。但在 Python2中，my_dict.keys() 返回的是一個(gè)列表。 所以 k in my_dict.keys() 操作在 python3中速度很快，但在 python2 中，處理效率并不高。

如果要自定義一個(gè)映射類型，合適的策略是繼承 collections.UserDict 類。這個(gè)類就是把標(biāo)準(zhǔn) dict 用 python 又實(shí)現(xiàn)了一遍，UserDict 是讓用戶繼承寫(xiě)子類的，改進(jìn)后的代碼如下：

import collections

class StrKeyDict(collections.UserDict):
 
 def __missing__(self, key):
 if isinstance(key, str):
  raise KeyError(key)
 return self[str(key)]
 
 def __contains__(self, key):
 # 這里可以放心假設(shè)所有已經(jīng)存儲(chǔ)的鍵都是字符串。因此只要在 self.data 上查詢就好了
 return str(key) in self.data
 
 def __setitem__(self, key, item):
 # 這個(gè)方法會(huì)把所有的鍵都轉(zhuǎn)化成字符串。
 self.data[str(key)] = item

因?yàn)?UserDict 繼承的是 MutableMapping，所以 StrKeyDict 里剩下的那些映射類型都是從 UserDict、MutableMapping 和 Mapping 這些超類繼承而來(lái)的。

Mapping 中提供了 get 方法，和我們?cè)?StrKeyDict0 中定義的一樣，所以我們?cè)谶@里不需要定義 get 方法。

字典的變種

在 collections 模塊中，除了 defaultdict 之外還有其他的映射類型。

collections.OrderedDict collections.ChainMap collections.Counter 不可變的映射類型

問(wèn)題：標(biāo)準(zhǔn)庫(kù)中所有的映射類型都是可變的，如果我們想給用戶提供一個(gè)不可變的映射類型該如何處理呢？

從 Python3.3 開(kāi)始 types 模塊中引入了一個(gè)封裝類名叫 MappingProxyType。如果給這個(gè)類一個(gè)映射，它會(huì)返回一個(gè)只讀的映射視圖（如果原映射做了改動(dòng)，這個(gè)視圖的結(jié)果頁(yè)會(huì)相應(yīng)的改變）。例如

>>> from types import MappingProxy Type
>>> d = {1: 'A'}
>>> d_proxy = MappingProxyType(d)
>>> d_proxy
mappingproxy({1: 'A'})
>>> d_proxy[1]
'A'
>>> d_proxy[2] = 'x'
Traceback(most recent call last):
 File "<stdin", line 1, in <module>
TypeError: 'MappingProxy' object does not support item assignment
>>> d[2] = 'B'
>>> d_proxy[2] # d_proxy 是動(dòng)態(tài)的，d 的改動(dòng)會(huì)反饋到它上邊
'B'

字典中的散列表

散列表其實(shí)是一個(gè)稀疏數(shù)組（總有空白元素的數(shù)組叫稀疏數(shù)組），在 dict 的散列表中，每個(gè)鍵值都占用一個(gè)表元，每個(gè)表元都有兩個(gè)部分，一個(gè)是對(duì)鍵的引用，另一個(gè)是對(duì)值的引用。因?yàn)樗斜碓拇笮∫恢拢钥梢酝ㄟ^(guò)偏移量來(lái)讀取某個(gè)表元。
python 會(huì)設(shè)法保證大概有1/3 的表元是空的，所以在快要達(dá)到這個(gè)閾值的時(shí)候，原有的散列表會(huì)被復(fù)制到一個(gè)更大的空間。

如果要把一個(gè)對(duì)象放入散列表，那么首先要計(jì)算這個(gè)元素的散列值。
Python內(nèi)置的 hash() 方法可以用于計(jì)算所有的內(nèi)置類型對(duì)象。

如果兩個(gè)對(duì)象在比較的時(shí)候是相等的，那么它們的散列值也必須相等。例如 1==1.0 那么，hash(1) == hash(1.0)

散列表算法

為了獲取 my_dict[search_key] 的值，Python 會(huì)首先調(diào)用 hash(search_key) 來(lái)計(jì)算 search_key 的散列值，把這個(gè)值的最低幾位當(dāng)做偏移量在散列表中查找元。若表元為空，拋出 KeyError 異常。若不為空，則表元會(huì)有一對(duì) found_key:found_value。
這時(shí)需要校驗(yàn) search_key == found_key，如果相等，返回 found_value。
如果不匹配（散列沖突），再在散列表中再取幾位，然后處理一下，用處理后的結(jié)果當(dāng)做索引再找表元。 然后重復(fù)上面的步驟。

取值流程圖如下：

添加新值和上述的流程基本一致，只不過(guò)對(duì)于前者，在發(fā)現(xiàn)空表元的時(shí)候會(huì)放入一個(gè)新元素，而對(duì)于后者，在找到相應(yīng)表元后，原表里的值對(duì)象會(huì)被替換成新值。

另外，在插入新值是，Python 可能會(huì)按照散列表的擁擠程度來(lái)決定是否重新分配內(nèi)存為它擴(kuò)容，如果增加了散列表的大小，那散列值所占的位數(shù)和用作索引的位數(shù)都會(huì)隨之增加字典的優(yōu)勢(shì)和限制

1、鍵必須是可散列的

可散列對(duì)象要求如下：

支持 hash 函數(shù)，并且通過(guò)__hash__() 方法所得的散列值不變支持通過(guò) __eq__() 方法檢測(cè)相等性若 a == b 為真， 則 hash(a) == hash(b) 也為真

2、字典開(kāi)銷巨大

因?yàn)樽值涫褂昧松⒘斜?，而散列表又必須是稀疏的，這導(dǎo)致它在空間上效率低下。

3、鍵查詢很快

dict 的實(shí)現(xiàn)是典型的空間換時(shí)間：字典類型由著巨大的內(nèi)存開(kāi)銷，但提供了無(wú)視數(shù)據(jù)量大小的快速訪問(wèn)。

4、鍵的次序決定于添加順序

當(dāng)往 dict 里添加新鍵而又發(fā)生散列沖突時(shí)，新建可能會(huì)被安排存放在另一個(gè)位置。

5、往字典里添加新鍵可能會(huì)改變已有鍵的順序

無(wú)論何時(shí)向字典中添加新的鍵，Python 解釋器都可能做出為字典擴(kuò)容的決定。擴(kuò)容導(dǎo)致的結(jié)果就是要新建一個(gè)更大的散列表，并把原有的鍵添加到新的散列表中，這個(gè)過(guò)程中可能會(huì)發(fā)生新的散列沖突，導(dǎo)致新散列表中次序發(fā)生變化。
因此，不要對(duì)字典同時(shí)進(jìn)行迭代和修改。