本篇主要介紹dict和set的高級(jí)用法以及它們背后的哈希表。
dict類(lèi)型不但在各種程序中廣泛使用，它也是Python的基石。模塊的命名空間、實(shí)例的屬性和函數(shù)的關(guān)鍵字參數(shù)等都用到了dict。與dict先關(guān)的內(nèi)置函數(shù)都在__builtins__.__dict__模塊中。
由于字典至關(guān)重要，Python對(duì)其實(shí)現(xiàn)做了高度優(yōu)化，而散列表（哈希函數(shù)，Hash）則是字典性能突出的根本原因。而且集合(set)的實(shí)現(xiàn)也依賴(lài)于散列表。
本片的大綱如下：
常見(jiàn)的字典方法；
如何處理找不到的鍵；
標(biāo)準(zhǔn)庫(kù)中dict類(lèi)型的變種；
set和frozenset類(lèi)型；
散列表工作原理；
散列表帶來(lái)的潛在影響（什么樣的數(shù)據(jù)可以作為鍵、不可預(yù)知的順序等）。
和上一篇一樣，先來(lái)看看collections.abc模塊中的兩個(gè)抽象基類(lèi)：Mapping和MutableMapping。它們的作用是為dict和其他類(lèi)似的類(lèi)型定義形式接口:
然而，非抽象映射類(lèi)型一般不會(huì)直接繼承這些抽象基類(lèi)，它們會(huì)直接對(duì)dict或者collections.UserDict進(jìn)行擴(kuò)展。
首先總結(jié)下常用的創(chuàng)建字典的方法：
列表推導(dǎo)和生成器表達(dá)式可以用在字典上。字典推導(dǎo)（dictcomp）可從任何以鍵值對(duì)作為元素的可迭代對(duì)象中構(gòu)建出字典。
它的參數(shù)列表如下：
update方法處理參數(shù)m的方法是典型的“鴨子類(lèi)型”。該方法首先檢測(cè)m是否有keys方法，如果有，那么update方法就把m當(dāng)做映射對(duì)象來(lái)處理（即使它并不是映射對(duì)象）；否則退一步，把m當(dāng)做包含了鍵值對(duì)(key, value)元素的迭代器。
Python中大多數(shù)映射類(lèi)的構(gòu)造方法都采用了類(lèi)似的邏輯，因此既可用一個(gè)映射對(duì)象來(lái)新建一個(gè)映射對(duì)象，也可以用包含(key, value)元素的可迭代對(duì)象來(lái)初始化一個(gè)映射對(duì)象。
當(dāng)更新字典時(shí)，如果遇到原字典中不存在的鍵時(shí)，我們一般最開(kāi)始會(huì)想到如下兩種方法：
以上兩種方法至少進(jìn)行2次鍵查詢(xún)，如果鍵不存在，第一種方法要查詢(xún)3次，非常低效。但如果使用setdefault方法，則只需一次就可以完成上述操作：
上述的setdefault方法在每次調(diào)用時(shí)都要我們手動(dòng)指定默認(rèn)值，那有沒(méi)有什么辦法能方便一些，在鍵不存在時(shí)，直接返回我們指定的默認(rèn)值？?jī)蓚€(gè)常用的方法是：①使用defaultdict類(lèi)；②自定義一個(gè)dict子類(lèi)，在子類(lèi)中實(shí)現(xiàn)__missing__方法，而這個(gè)方法又有至少兩種方法。
collections.defaultdict能優(yōu)雅的解決3.3.2中的問(wèn)題：
在實(shí)例化defaultdict時(shí)，需要給構(gòu)造方法提供一個(gè)可調(diào)用對(duì)象（實(shí)現(xiàn)了__call__方法的對(duì)象），這個(gè)可調(diào)用對(duì)象存儲(chǔ)在defaultdict類(lèi)的屬性default_factory中，當(dāng)__getitem__找不到所需的鍵時(shí)就會(huì)通過(guò)default_factory來(lái)調(diào)用這個(gè)可調(diào)用對(duì)象來(lái)創(chuàng)建默認(rèn)值。
上述代碼中 my_dict[key] 的內(nèi)部過(guò)程如下(假設(shè)key是新鍵)：
調(diào)用list()來(lái)創(chuàng)建一個(gè)新列表；
把這個(gè)新列表作為值，key作為它的鍵，放到my_dict中；
返回這個(gè)列表的引用。
注意：
如果在實(shí)例化defaultdict時(shí)未指定default_factory，那么在查詢(xún)不存在的鍵時(shí)則會(huì)觸發(fā)KeyError；
defaultdict中的default_factory只會(huì)在__getitem__里被調(diào)用，在其它的方法里完全不會(huì)發(fā)揮作用！比如，dd是個(gè)defaultdict，k是個(gè)不存在的鍵，dd[k]這個(gè)表達(dá)式則會(huì)調(diào)用default_factory，并返回默認(rèn)值，而dd.get(k)則會(huì)返回None。
特殊方法__missing__
其實(shí)上述的功能都得益于特殊方法__missing__，實(shí)際調(diào)用default_factory的就是該特殊方法，且該方法只會(huì)被__getitem__調(diào)用。即：__getitem__調(diào)用__missing__，__missing__調(diào)用default_factory。
所有的映射類(lèi)型在處理找不到鍵的情況是，都會(huì)牽扯到該特殊方法?；?lèi)dict沒(méi)有定義這個(gè)方法，但dict有該方法的聲明。
下面通過(guò)編寫(xiě)一個(gè)繼承自dict的類(lèi)來(lái)說(shuō)明如何使用__missing__實(shí)現(xiàn)字典查詢(xún)，不過(guò)這里并沒(méi)有在找不到鍵時(shí)調(diào)用一個(gè)可調(diào)用對(duì)象，而是拋出異常。
某些情況下可能希望在查詢(xún)字典時(shí)，映射里的鍵通通轉(zhuǎn)換成str類(lèi)，但為了方便，也允許使用非字符串作為建，比如我們希望實(shí)現(xiàn)如下效果：
以下便是這個(gè)類(lèi)的實(shí)現(xiàn)：
說(shuō)明：
第3行：這里的isinstance(key, str)測(cè)試是必需的。如果沒(méi)有這個(gè)測(cè)試，那么當(dāng)str(key)是個(gè)不存在的鍵時(shí)便會(huì)發(fā)生無(wú)限遞歸，因?yàn)榈?行self[str(key)]會(huì)調(diào)用__getitem__，進(jìn)而又調(diào)用__missing__，然后一直重復(fù)下去。
第13行：為了保持一致性，__contains__方法在這里也是必需的，因?yàn)閗 in d這個(gè)操作會(huì)調(diào)用該方法。但是從dict繼承到的__contains__方法在找不到鍵的時(shí)候不會(huì)調(diào)用__missing__（間接調(diào)用，不會(huì)直接調(diào)用）。
第14行：這里并沒(méi)有使用更具Python風(fēng)格的寫(xiě)法：key in my_dict，因?yàn)檫@樣寫(xiě)會(huì)使__contains__也發(fā)生遞歸調(diào)用，所以這里采用了更顯式的方法 key in self.keys。同時(shí)需要注意的是，這里有兩個(gè)判斷，因?yàn)槲覀儽緵](méi)有強(qiáng)行限制所有的鍵都必須是str，所以字典中可能存在非字符串的鍵（key in self.keys()）。
像k in my_dict.keys()這種操作在Python3中很快，即使映射類(lèi)型對(duì)象很龐大也很快，因?yàn)閐ict.keys()返回的是一個(gè)”視圖“，在視圖中查找一個(gè)元素的速度很快。
如果要自定義一個(gè)映射類(lèi)型，更好的策略是繼承collections.UserDict類(lèi)。它是把標(biāo)準(zhǔn)dict用純Python又實(shí)現(xiàn)了一遍。之所以更傾向于從UserDict而不是從dict繼承，是因?yàn)楹笳哂袝r(shí)會(huì)在某些方法的實(shí)現(xiàn)上走一些捷徑，導(dǎo)致我們不得不在它的子類(lèi)中重寫(xiě)這些方法，而UserDict則沒(méi)有這些問(wèn)題。也正是由于這個(gè)原因，如果上個(gè)例子要實(shí)現(xiàn)將所有的鍵都轉(zhuǎn)換成字符串，還需要做很多工作，而從UserDict繼承則能很容易實(shí)現(xiàn)。
注意：如果我們想在上個(gè)例子中實(shí)現(xiàn)__setitem__，使其將所有的鍵都轉(zhuǎn)換成str，則會(huì)發(fā)生無(wú)限遞歸：
下面使用UserDict來(lái)實(shí)現(xiàn)一遍StrKeyDict，它實(shí)現(xiàn)了__setitem__方法，將所有的鍵都轉(zhuǎn)換成str。注意這里并沒(méi)有自行實(shí)現(xiàn)get方法，原因在后面。
因?yàn)閁serDict繼承自MutableMapping，所以StrKeyDict里剩下的映射類(lèi)型的方法都是從UserDict、MutableMapping和Mapping繼承而來(lái)，這些方法中有兩個(gè)值得關(guān)注：
MutableMapping.update：
這個(gè)方法不但可以直接用，它還用在__init__里，使其能支持各種格式的參數(shù)。而這個(gè)update方法內(nèi)部則使用self[key] = value來(lái)添加新值，所以它其實(shí)是在使用我們定義的__setitem__方法。
Mapping.get：
對(duì)比StrKeyDict0和StrKeyDict的代碼可以發(fā)現(xiàn)，我們并沒(méi)有為后者定義get方法。前者如果不定義get方法，則會(huì)出現(xiàn)如下情況：
而在StrKeyDict中則沒(méi)有必要，因?yàn)閁serDict繼承了Mapping的get方法，而查看源代碼可知，這個(gè)方法的實(shí)現(xiàn)和StrKeyDict0.get一模一樣。
這個(gè)類(lèi)型在添加鍵的時(shí)候會(huì)保持原序，即對(duì)鍵的迭代次序就是添加時(shí)的順序。它的popitem方法默認(rèn)刪除并返回字典中的最后一個(gè)元素。值得注意的是，從Python3.6開(kāi)始，dict中鍵的順序也保持了原序。但出于兼容性考慮，如果要保持有序，還是推薦使用OrderedDict。
該類(lèi)型可容納多個(gè)不同的映射對(duì)象，然后在查找元素時(shí)，這些映射對(duì)象會(huì)被當(dāng)成一個(gè)整體被逐個(gè)查找。這個(gè)功能在給有嵌套作用域的語(yǔ)言做解釋器的時(shí)候很有用，可以用一個(gè)映射對(duì)象來(lái)代表一個(gè)作用域的上下文。
這個(gè)類(lèi)會(huì)給鍵準(zhǔn)備一個(gè)整數(shù)計(jì)數(shù)器，每次更新一個(gè)鍵時(shí)就會(huì)自動(dòng)增加這個(gè)計(jì)數(shù)器。所以這個(gè)類(lèi)型可以用來(lái)給可散列對(duì)象計(jì)數(shù)，或者當(dāng)成多重集來(lái)使用（相同元素可以出現(xiàn)不止一次的集合）。
標(biāo)準(zhǔn)庫(kù)中所有的映射類(lèi)型都是可變的，但有時(shí)候會(huì)有這樣的需要，比如不能讓用戶錯(cuò)誤地修改某個(gè)映射。從Python3.3開(kāi)始，types模塊中引入了一個(gè)封裝類(lèi)MappingProxyType。如果給這個(gè)類(lèi)一個(gè)映射，它返回一個(gè)只讀的映射視圖。雖然是個(gè)只讀視圖，但它是動(dòng)態(tài)的，如果原映射被修改，我們也能通過(guò)這個(gè)視圖觀察到變化。以下是它的一個(gè)例子：
和前面的字典一樣，先來(lái)看看集合的超類(lèi)的繼承關(guān)系：
集合的本質(zhì)是許多唯一對(duì)象的聚集。即，集合可以用于去重。集合中的元素必須是可散列的，set類(lèi)型本身是不可散列的，但是frozenset可以。也就是說(shuō)可以創(chuàng)建一個(gè)包含不同frozenset的set。
集合的操作
注意兩個(gè)概念：字面量句法，構(gòu)造方法：
字面量句法相對(duì)于構(gòu)造方法更快更易讀。后者速度之所以慢是因?yàn)镻ython必須先從set這個(gè)名字來(lái)查詢(xún)構(gòu)造方法，然后新建一個(gè)列表，最后再把這個(gè)列表傳入到構(gòu)造方法里。而對(duì)于字面量句法，Python會(huì)利用一個(gè)專(zhuān)門(mén)的叫做BUILD_SET的字節(jié)碼來(lái)創(chuàng)建集合。
集合的字面量——{1}，{1, 2}等——看起來(lái)和它的數(shù)學(xué)形式一模一樣。但要注意空集，如果要?jiǎng)?chuàng)建一個(gè)空集，只能是 temp = set()，而不是 temp = {}，后者創(chuàng)建的是一個(gè)空字典。
frozenset的標(biāo)準(zhǔn)字符串表示形式看起來(lái)就像構(gòu)造方法調(diào)用一樣：
對(duì)于frozenset，一旦創(chuàng)建便不可更改，常用作字典的鍵的集合。
除此之外，集合還實(shí)現(xiàn)了很多基礎(chǔ)的中綴運(yùn)算符，如交集a & b，合集a | b，差集a - b等，還有子集，真子集等操作，由于這類(lèi)操作太多，這里不再一一列出。下面代碼得到兩個(gè)可迭代對(duì)象中共有的元素個(gè)數(shù)，這是一個(gè)常用操作：
集合推導(dǎo)
和列表推導(dǎo)，字典推導(dǎo)一樣，集合也有推導(dǎo)（setcomps）：
有人做過(guò)實(shí)驗(yàn)（就在普通筆記本上），在1,000,000個(gè)元素中找1,000個(gè)元素，dict與set兩者的耗時(shí)比較接近，大約為0.000337s，而使用列表list，耗時(shí)是97.948056s，list的耗時(shí)是dict和set的約29萬(wàn)倍。而造成這種差距的最根本的原因是，list中找元素是按位置一個(gè)一個(gè)找（雖然有像折半查找這類(lèi)的算法，但本質(zhì)依然是一個(gè)位置接一個(gè)位置的比較），而dict是根據(jù)某個(gè)信息直接計(jì)算元素的位置，顯然后者速度要比挨個(gè)找快很多。而這個(gè)計(jì)算方法統(tǒng)稱(chēng)為哈希函數(shù)（hash），即 hash(key)–>position。
礙于篇幅，關(guān)于哈希算法的原理（哈希函數(shù)的選擇，沖突的解決等）這里便不再贅述，相信經(jīng)常和算法打交道或者考過(guò)研的老鐵們一定不陌生。
哈希表（也叫散列表）其實(shí)是個(gè)稀疏數(shù)組（有很多空元素的數(shù)組），每個(gè)單元叫做表元（bucket），Python中每個(gè)表元由對(duì)鍵的引用和對(duì)值的引用兩部分組成。因?yàn)樗斜碓拇笮∫恢?，所以?dāng)計(jì)算出位置后，可以通過(guò)偏移量來(lái)讀取某個(gè)元素（變址尋址）。
Python會(huì)設(shè)法保證大概還有三分之一的表元是空的，當(dāng)快要達(dá)到這個(gè)閾值的時(shí)候，原有的哈希表會(huì)被復(fù)制到一個(gè)更大的空間中。
如果要把一個(gè)對(duì)象放入哈希表中，首先要計(jì)算這個(gè)元素的哈希值。Python中可以通過(guò)函數(shù)hash()來(lái)計(jì)算。內(nèi)置的hash()可用于所有的內(nèi)置對(duì)象。如果是自定義對(duì)象調(diào)用hash()，實(shí)際上運(yùn)行的是自定義的__hash__。如果兩個(gè)對(duì)象在比較的時(shí)候相等的，那么它們的哈希值必須相等，否則哈希表就不能正常工作。比如，如果 1 == 1.0 為真，那么hash(1) == hash(1.0)也必須為真，但其實(shí)這兩個(gè)數(shù)字的內(nèi)部結(jié)構(gòu)完全不一樣。而相等性的檢測(cè)則是調(diào)用特殊方法__eq__。
_補(bǔ)充_：從Python3.3開(kāi)始，為了防止DOS攻擊，str、bytes和datetime對(duì)象的哈希值計(jì)算過(guò)程中多了隨機(jī)的“加鹽”步驟。所加的鹽值是Python進(jìn)程中的一個(gè)常量，但每次啟動(dòng)Python解釋器都會(huì)生成一個(gè)不同的鹽值。
為獲取my_dict[search_key]背后的值（不是哈希值），Python首先會(huì)調(diào)用hash(search_key)計(jì)算哈希值，然后取這個(gè)值最低的幾位數(shù)字當(dāng)作偏移量（這只是一種哈希算法）去獲取所要的值，如果發(fā)生了沖突，則再取哈希值的另外幾位，知道不沖突為止。
在插入新值的時(shí)候，Python可能會(huì)按照哈希表的擁擠程度來(lái)決定是否要重新分配內(nèi)存為它擴(kuò)容。如果增加了散列表的大小，散列值所占的位數(shù)和用作索引的位數(shù)都會(huì)隨之增加（目的是為了減少?zèng)_突發(fā)生的概率）。
這個(gè)算法看似費(fèi)事，但實(shí)際上就算dict中有數(shù)百萬(wàn)個(gè)元素，多數(shù)的搜索過(guò)程中并不會(huì)發(fā)生沖突，平均下來(lái)每次搜索可能會(huì)有一到兩次沖突。
1、鍵必須是可散列的
一個(gè)可散列對(duì)象必須滿足一下要求：
（1）支持hash()函數(shù)，并且通過(guò)__hash__()方法得到的哈希值是不變的；
（2）支持通過(guò)__eq__()方法來(lái)檢測(cè)相等性；
（3）若 a == b為真，則 hash(a) == hash(b)也必須為真。
所有自定義的對(duì)象默認(rèn)都是可散列的，因?yàn)樗鼈兊墓Ｖ涤衖d()函數(shù)來(lái)獲取，而且它們都是不相等的。如果你實(shí)現(xiàn)了一個(gè)類(lèi)的__eq__方法，并且希望它是可散列的，那請(qǐng)務(wù)必保證這個(gè)類(lèi)滿足上面的第3條要求。
2、字典在內(nèi)存上的開(kāi)銷(xiāo)巨大
典型的用空間換時(shí)間的算法。因?yàn)楣１硎窍∈璧?，這導(dǎo)致它的空間利用率很低。
如果需要存放數(shù)量巨大的記錄，那么放在由元組或命名元組構(gòu)成的列表中會(huì)是比較好的選擇；最好不要根據(jù)JSON的風(fēng)格，用由字典組成的列表來(lái)存放這些記錄。
用元組代替字典就能節(jié)省空間的原因有兩個(gè)：①避免了哈希表所耗費(fèi)的空間；②無(wú)需把記錄中字段的名字在每個(gè)元素里都存一遍。
關(guān)于空間優(yōu)化：如果你的內(nèi)存夠用，那么空間優(yōu)化工作可以等到真正需要的時(shí)候再開(kāi)始，因?yàn)閮?yōu)化往往是可維護(hù)性的對(duì)立面。
3、鍵查詢(xún)很快
本節(jié)最開(kāi)始的實(shí)驗(yàn)已經(jīng)證明，字典的查詢(xún)速度非?？臁Ｈ绻俸?jiǎn)單計(jì)算一下，上面的實(shí)驗(yàn)中，在有1000萬(wàn)個(gè)元素的字典里，每秒能進(jìn)行200萬(wàn)次鍵查詢(xún)。
這里之所以說(shuō)的是“鍵查詢(xún)”，而不是“查詢(xún)”，是因?yàn)橛锌赡苤档臄?shù)據(jù)不在內(nèi)存，內(nèi)在磁盤(pán)中。一旦涉及到磁盤(pán)這樣的低速設(shè)備，查詢(xún)速度將大打折扣。
4、鍵的次序取決于添加順序
當(dāng)往dict里添加新鍵而又發(fā)生沖突時(shí)，新鍵可能會(huì)被安排存放到另一個(gè)位置。并且同一組數(shù)據(jù)，每次按不同順序進(jìn)行添加，那么即便是同一個(gè)鍵，同一個(gè)算法，最后的位置也可能不同。最典型的就是這組數(shù)據(jù)全沖突（所有的hash值都一樣），然后采用的是線性探測(cè)再散列解決沖突，這時(shí)的順序就是添加時(shí)的順序。
5、向字典中添加新鍵可能會(huì)改變已有鍵的順序。
無(wú)論何時(shí)往字典中添加新的鍵，Python解釋器都有可能做出擴(kuò)容的決定。擴(kuò)容時(shí)，在將原有的元素添加到新表的過(guò)程中就有可能改變?cè)性氐捻樞?。如果在迭代一個(gè)字典的過(guò)程中同時(shí)對(duì)修改字典，那么這個(gè)循環(huán)就很有可能會(huì)跳過(guò)一些鍵。
_補(bǔ)充_：Python3中，.keys()、.items()和.values()方法返回的都是字典視圖。
set和frozenset也由哈希表實(shí)現(xiàn)，但它們的哈希表中存放的只有元素的引用（類(lèi)似于在字典里只存放了鍵而沒(méi)放值）。在set加入到Python之前，都是把字典加上無(wú)意義的值來(lái)當(dāng)集合用。5.3中對(duì)字典的幾個(gè)特點(diǎn)也同樣適用于集合。
字典是Python的基石。除了基本的dict，標(biāo)準(zhǔn)庫(kù)中還有特殊的映射類(lèi)型：defaultdict、OrderedDict、ChainMap、Counter和UserDict，這些類(lèi)都在collections模塊中。
大多數(shù)映射都提供了兩個(gè)強(qiáng)大的方法：setdefault和update。前者可避免重復(fù)搜索，后者可批量更新。
在映射類(lèi)型的API中，有個(gè)很好用的特殊方法__missing__，可以通過(guò)這個(gè)方法自定義當(dāng)對(duì)象找不到某個(gè)鍵時(shí)的行為。
set和dict的實(shí)現(xiàn)都用到了哈希表，兩者的查找速度都很快，但空間消耗大，典型的以空間換時(shí)間的算法。
聯(lián)系客服
