一、介紹
1、泛映射類型
collections.abc模塊中有Mapping和MutableMapping這兩個(gè)抽象基類，它們的作用是為dict和其他類似的類型定義形式接口（在Python 2.6到Python 3.2的版本中，這些類還不屬于collections.abc模塊，而是隸屬于collections模塊）。

然而，非抽象映射類型一般不會(huì)直接繼承這些抽象基類，它們會(huì)直接對(duì)dict或是collections.UserDict進(jìn)行擴(kuò)展。
這些抽象基類的主要作用是作為形式化的文檔，它們定義了構(gòu)建一個(gè)映射類型所需要的最基本的接口。然后它們還可以跟isinstance一起被用來(lái)判定某個(gè)數(shù)據(jù)是不是廣義上的映射類型。

isinstance(my_dict, abc.Mapping)
Out[138]: True

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

1.1如果一個(gè)對(duì)象是可散列的，那么在這個(gè)對(duì)象的生命周期中，它的散列值是不變的，而且這個(gè)對(duì)象需要實(shí)現(xiàn)__hash__（　）方法。另外可散列對(duì)象還要有__eq__（　）方法，這樣才能跟其他鍵做比較。如果兩個(gè)可散列對(duì)象是相等的，那么它們的散列值一定是一樣的……
原子不可變數(shù)據(jù)類型（str、bytes和數(shù)值類型）都是可散列類型，frozenset也是可散列的，因?yàn)楦鶕?jù)其定義，frozenset里只能容納可散列類型。元組的話，只有當(dāng)一個(gè)元組包含的所有元素都是可散列類型的情況下，它才是可散列的。

tt=(1,2,[30,40])
t1=(1,2,(30,40))
hash(tt)
TypeError: unhashable type: 'list'
hash(t1)
Out[142]: -3907003130834322577

1.2 創(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
Out[148]: True

2、字典推導(dǎo)
字典推導(dǎo)（dictcomp）可以從任何以鍵值對(duì)作為元素的可迭代對(duì)象中構(gòu)建出字典。下面就展示了利用字典推導(dǎo)可以把一個(gè)裝滿元組的列表變成了字典。

country = ['China', 'Brazil', 'Russia', 'Japan']
country_code={co:len(co) for co in country}
country_code
Out[154]: {'China': 5, 'Brazil': 6, 'Russia': 6, 'Japan': 5}

3、映射類型的常見(jiàn)方法

# 返回國(guó)家對(duì)應(yīng)的值，沒(méi)有的話返回-1
country_code.get('China',-1)
Out[155]: 5
country_code.get('USA',-1)
Out[156]: -1
# 返回country_code中的所有鍵值對(duì)
country_code.items()
Out[157]: dict_items([('China', 5), ('Brazil', 6), ('Russia', 6), ('Japan', 5)])
# 隨機(jī)返回一個(gè)鍵值對(duì)，并從字典中移除它
country_code.popitem()
Out[158]: ('Japan', 5)
country_code
Out[159]: {'China': 5, 'Brazil': 6, 'Russia': 6}
# 返回brazil所對(duì)應(yīng)的值，并刪除這個(gè)鍵值對(duì)。 如果沒(méi)有，則返回默認(rèn)值
country_code.pop('Brazil')
Out[160]: 6
country_code.pop('Brazil',-1)
Out[161]: -1
country_code
Out[162]: {'China': 5, 'Russia': 6}

OrderedDict.popitem()會(huì)移除字典里最先插入的元素（先進(jìn)先出）；同時(shí)這個(gè)方法還有一個(gè)可選的last參數(shù)，若為真，則會(huì)移除最后插入的元素（后進(jìn)先出)

4、映射的彈性鍵查詢
有時(shí)候?yàn)榱朔奖闫鹨?jiàn)，就算某個(gè)鍵在映射里不存在，我們也希望在通過(guò)這個(gè)鍵讀取值的時(shí)候能得到一個(gè)默認(rèn)值。有兩個(gè)途徑能幫我們達(dá)到這個(gè)目的。

• 一個(gè)是通過(guò)defaultdict這個(gè)類型而不是普通的dict
• 另一個(gè)是給自己定義一個(gè)dict的子類，然后在子類中實(shí)現(xiàn)__missing__方法。
  4.1 defaultdict：處理找不到的鍵的一個(gè)選擇
  在實(shí)例化一個(gè)defaultdict的時(shí)候，需要給構(gòu)造方法提供一個(gè)可調(diào)用對(duì)象，這個(gè)可調(diào)用對(duì)象會(huì)在__getitem__碰到找不到的鍵的時(shí)候被調(diào)用，讓__getitem__返回某種默認(rèn)值。
  比如，我們新建了這樣一個(gè)字典：dd=defaultdict(list)，如果鍵’new-key’在dd中還不存在的話，表達(dá)式dd[‘new-key’]會(huì)按照以下的步驟來(lái)行事。
  (1)調(diào)用list（　）來(lái)建立一個(gè)新列表。
  (2)把這個(gè)新列表作為值，'new-key’作為它的鍵，放到dd中。
  (3)返回這個(gè)列表的引用。
  而這個(gè)用來(lái)生成默認(rèn)值的可調(diào)用對(duì)象存放在名為default_factory的實(shí)例屬性里。

import collections
names = collections.defaultdict(list)
names['1班'].append('李明')
names
Out[166]: defaultdict(list, {'1班': ['李明']})names.get('2班').append('李明')
Traceback (most recent call last):
AttributeError: 'NoneType' object has no attribute 'append'

defaultdict里的default_factory只會(huì)在__getitem__里被調(diào)用，在其他的方法里完全不會(huì)發(fā)揮作用。比如，dd是個(gè)defaultdict，k是個(gè)找不到的鍵， dd[k]這個(gè)表達(dá)式會(huì)調(diào)用default_factory創(chuàng)造某個(gè)默認(rèn)值，而dd.get(k)則會(huì)返回None。

所有這一切背后的功臣其實(shí)是特殊方法__missing__。它會(huì)在defaultdict遇到找不到的鍵的時(shí)候調(diào)用default_factory，而實(shí)際上這個(gè)特性是所有映射類型都可以選擇去支持的
4.2 特殊方法__missing__
所有的映射類型在處理找不到的鍵的時(shí)候，都會(huì)牽扯到__missing__方法。這也是這個(gè)方法稱作“missing”的原因。雖然基類dict并沒(méi)有定義這個(gè)方法，但是dict是知道有這么個(gè)東西存在的。也就是說(shuō)，如果有一個(gè)類繼承了dict，然后這個(gè)繼承類提供了__missing__方法，那么在__getitem__碰到找不到的鍵的時(shí)候，Python就會(huì)自動(dòng)調(diào)用它，而不是拋出一個(gè)KeyError異常。
missing__方法只會(huì)被__getitem__調(diào)用（比如在表達(dá)式d[k]中）。提供__missing__方法對(duì)get或者_(dá)_contains_（in運(yùn)算符會(huì)用到這個(gè)方法）這些方法的使用沒(méi)有影響。這也是我在上一節(jié)最后的警告中提到，defaultdict中的default_factory只對(duì)__getitem__有作用的原因。

示例 StrKeyDict0在查詢的時(shí)候把非字符串的鍵轉(zhuǎn)換為字符串

class StrKeyDict0(dict):def __missing__(self, key):if isinstance(key, str):raise KeyError(key)return self[str(key)]def get(self, key, default=None):try:return self[key]except KeyError:return default
d = StrKeyDict0([('2', 'two'),('4', 'four')])
d['2']
Out[170]: 'two'
d[4]
Out[171]: 'four'
d[1]
Traceback (most recent call last):
KeyError: '1'
d.get('2')
Out[173]: 'two'
d.get(4)
Out[174]: 'four'
d.get(1, 'N/A')
Out[175]: 'N/A'

5、字典的變種
這一節(jié)總結(jié)了標(biāo)準(zhǔn)庫(kù)里collections模塊中，除了defaultdict之外的不同映射類型。
5.1 collections.OrderedDict：這個(gè)類型在添加鍵的時(shí)候會(huì)保持順序，因此鍵的迭代次序總是一致的。OrderedDict的popitem方法默認(rèn)刪除并返回的是字典里的最后一個(gè)元素，但是如果像my_odict.popitem(last=False)這樣調(diào)用它，那么它刪除并返回第一個(gè)被添加進(jìn)去的元素。
5.2 collections.ChainMap：該類型可以容納數(shù)個(gè)不同的映射對(duì)象，然后在進(jìn)行鍵查找操作的時(shí)候，這些對(duì)象會(huì)被當(dāng)作一個(gè)整體被逐個(gè)查找，直到鍵被找到為止。這個(gè)功能在給有嵌套作用域的語(yǔ)言做解釋器的時(shí)候很有用，可以用一個(gè)映射對(duì)象來(lái)代表一個(gè)作用域的上下文。在collections文檔介紹ChainMap對(duì)象的那一部分里有一些具體的使用示例，其中包含了下面這個(gè)Python變量查詢規(guī)則的代碼片段：

import collections
chain_map = collections.ChainMap({'a':1, 'b':2},{'c':3},{'d':4})
all_dict = dict(chain_map)
all_dict
Out[5]: {'d': 4, 'c': 3, 'a': 1, 'b': 2}

5.3 Counter:這個(gè)映射類型會(huì)給鍵準(zhǔn)備一個(gè)整數(shù)計(jì)數(shù)器。每次更新一個(gè)鍵的時(shí)候都會(huì)增加這個(gè)計(jì)數(shù)器。所以這個(gè)類型可以用來(lái)給可散列表對(duì)象計(jì)數(shù)，或者是當(dāng)成多重集來(lái)用——多重集合就是集合里的元素可以出現(xiàn)不止一次。Counter實(shí)現(xiàn)了+和-運(yùn)算符用來(lái)合并記錄，還有像most_common([n])這類很有用的方法。

ct = collections.Counter('ababdadfawwwwweijisafl')
ct
Out[7]: Counter({'a': 5, 'b': 2,'d': 2,'f': 2,'w': 5,'e': 1, 'i': 2,'j': 1,'s': 1, 'l': 1})
ct.update('ddddddeeeeeee')
ct
Out[9]: Counter({'a': 5, 'b': 2, 'd': 8, 'f': 2, 'w': 5,'e': 8,'i': 2,'j': 1,'s': 1,'l': 1})
ct.most_common(3)
Out[10]: [('d', 8), ('e', 8), ('a', 5)]

5.4 collections.UserDict:就創(chuàng)造自定義映射類型來(lái)說(shuō)，以UserDict為基類，總比以普通的dict為基類要來(lái)得方便。

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):return str(key) in self.datadef __setitem__(self, key, item):self.data[str(key)] = item

因?yàn)閁serDict繼承的是MutableMapping，所以StrKeyDict里剩下的那些映射類型的方法都是從UserDict、MutableMapping和Mapping這些超類繼承而來(lái)的。特別是最后的Mapping類，它雖然是一個(gè)抽象基類（ABC），但它卻提供了好幾個(gè)實(shí)用的方法。以下兩個(gè)方法值得關(guān)注。

• MutableMapping.update:這個(gè)方法不但可以為我們所直接利用，它還用在__init__里，讓構(gòu)造方法可以利用傳入的各種參數(shù)（其他映射類型、元素是(key, value)對(duì)的可迭代對(duì)象和鍵值參數(shù)）來(lái)新建實(shí)例。因?yàn)檫@個(gè)方法在背后是用self[key]=value來(lái)添加新值的，所以它其實(shí)是在使用我們的__setitem__方法。
• Mapping.get:在StrKeyDict0中，我們不得不改寫(xiě)get方法，好讓它的表現(xiàn)跟__getitem__一致。而在示例3-8中就沒(méi)這個(gè)必要了，因?yàn)樗^承了Mapping.get方法，

6、不可變映射類型
標(biāo)準(zhǔn)庫(kù)里所有的映射類型都是可變的，但有時(shí)候你會(huì)有這樣的需求，比如不能讓用戶錯(cuò)誤地修改某個(gè)映射。從Python 3.3開(kāi)始，types模塊中引入了一個(gè)封裝類名叫MappingProxyType。如果給這個(gè)類一個(gè)映射，它會(huì)返回一個(gè)只讀的映射視圖。雖然是個(gè)只讀視圖，但是它是動(dòng)態(tài)的。這意味著如果對(duì)原映射做出了改動(dòng)，我們通過(guò)這個(gè)視圖可以觀察到，但是無(wú)法通過(guò)這個(gè)視圖對(duì)原映射做出修改。

from types import MappingProxyType
d = {1:'A'}
d_proxy = MappingProxyType(d)
d_proxy
Out[12]: mappingproxy({1: 'A'})
d_proxy[1]
Out[13]: 'A'
d_proxy[2] = 'b'
Traceback (most recent call last):
TypeError: 'mappingproxy' object does not support item assignment
d[2] = 'c'
d_proxy
Out[16]: mappingproxy({1: 'A', 2: 'c'})

7、集合論
集合的本質(zhì)是許多唯一對(duì)象的聚集。因此，集合可以用于去重

l = ['spam', 'spam', 'eggs', 'spam']
set(l)
Out[18]: {'eggs', 'spam'}
list(set(l))
Out[19]: ['spam', 'eggs']

除了保證唯一性，集合還實(shí)現(xiàn)了很多基礎(chǔ)的中綴運(yùn)算符。給定兩個(gè)集合a和b，a | b返回的是它們的合集，a & b得到的是交集，而a-b得到的是差集。

7.1 集合字面量
除空集之外，集合的字面量——{1}、{1, 2}，等等——看起來(lái)跟它的數(shù)學(xué)形式一模一樣。如果是空集，那么必須寫(xiě)成set（　）的形式。
7.2 集合操作
集合的數(shù)學(xué)運(yùn)算：這些方法或者會(huì)生成新集合，或者會(huì)在條件允許的情況下就地修改集合。

# 定義集合
a = {1, 2, 3, 4, 5, 6}
b = {4,5,6,7,8,9,20}
# 求交集操作
a.__and__(b)
Out[25]: {4, 5, 6}
a&b
Out[26]: {4, 5, 6}
# 把a(bǔ)更新為a與b的交集
a.__iand__(b)
Out[28]: {4, 5, 6}
a
Out[29]: {4, 5, 6}
a &= b
Out[30]: {4, 5, 6}
# a和b的并集
a|b
Out[30]: {4, 5, 6, 7, 8, 9, 20}
a.__or__(b)
Out[32]: {4, 5, 6, 7, 8, 9, 20}
# 把a(bǔ)更新為a和b的并集
a.__ior__(b)
Out[33]: {4, 5, 6, 7, 8, 9, 20}
a
Out[34]: {4, 5, 6, 7, 8, 9, 20}
# 求a和b的差集
a -b
Out[37]: set()
a.__sub__(b)
Out[38]: set()
# 把a(bǔ)更新為a和b的差集
a -= b
a
Out[40]: set()

8、set和dict的背后
8.1 字典中的散列表
散列表其實(shí)是一個(gè)稀疏數(shù)組（總是有空白元素的數(shù)組稱為稀疏數(shù)組）。
因?yàn)镻ython會(huì)設(shè)法保證大概還有三分之一的表元是空的，所以在快要達(dá)到這個(gè)閾值的時(shí)候，原有的散列表會(huì)被復(fù)制到一個(gè)更大的空間里面。如果要把一個(gè)對(duì)象放入散列表，那么首先要計(jì)算這個(gè)元素鍵的散列值。Python中可以用hash（　）方法來(lái)做這件事情，接下來(lái)會(huì)介紹這一點(diǎn)。

• 內(nèi)置的hash（　）方法可以用于所有的內(nèi)置類型對(duì)象。如果是自定義對(duì)象調(diào)用hash（　）的話，實(shí)際上運(yùn)行的是自定義的__hash__。如果兩個(gè)對(duì)象在比較的時(shí)候是相等的，那它們的散列值必須相等，否則散列表就不能正常運(yùn)行了。例如，如果1==1.0為真，那么hash(1)==hash(1.0)也必須為真，但其實(shí)這兩個(gè)數(shù)字（整型和浮點(diǎn)）的內(nèi)部結(jié)構(gòu)是完全不一樣的。
• 如果search_key和found_key不匹配的話，這種情況稱為散列沖突。發(fā)生這種情況是因?yàn)?#xff0c;散列表所做的其實(shí)是把隨機(jī)的元素映射到只有幾位的數(shù)字上，而散列表本身的索引又只依賴于這個(gè)數(shù)字的一部分。為了解決散列沖突，算法會(huì)在散列值中另外再取幾位，然后用特殊的方法處理一下，把新得到的數(shù)字再當(dāng)作索引來(lái)尋找表元。[插圖]若這次找到的表元是空的，則同樣拋出KeyError；若非空，或者鍵匹配，則返回這個(gè)值；或者又發(fā)現(xiàn)了散列沖突，則重復(fù)以上的步驟。
  8.2 dict的實(shí)現(xiàn)及其導(dǎo)致的結(jié)果
  8.2.1 下面的內(nèi)容會(huì)討論使用散列表給dict帶來(lái)的優(yōu)勢(shì)和限制都有哪些。
• 鍵必須是可散列的： 一個(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（　）來(lái)獲取，而且它們都是不相等的。
  **如果你實(shí)現(xiàn)了一個(gè)類的__eq__方法，并且希望它是可散列的，那么它一定要有個(gè)恰當(dāng)?shù)腳_hash__方法，保證在ab為真的情況下hash(a)==hash(b)也必定為真。否則就會(huì)破壞恒定的散列表算法，導(dǎo)致由這些對(duì)象所組成的字典和集合完全失去可靠性，這個(gè)后果是非常可怕的。另一方面，如果一個(gè)含有自定義的__eq__依賴的類處于可變的狀態(tài)，那就不要在這個(gè)類中實(shí)現(xiàn)__hash__方法，因?yàn)樗膶?shí)例是不可散列的**
• 字典在內(nèi)存上的開(kāi)銷巨大：由于字典使用了散列表，而散列表又必須是稀疏的，這導(dǎo)致它在空間上的效率低下。
• 鍵查詢很快：dict的實(shí)現(xiàn)是典型的空間換時(shí)間：字典類型有著巨大的內(nèi)存開(kāi)銷，但它們提供了無(wú)視數(shù)據(jù)量大小的快速訪問(wèn)——只要字典能被裝在內(nèi)存里。
• 鍵的次序取決于添加順序：當(dāng)往dict里添加新鍵而又發(fā)生散列沖突的時(shí)候，新鍵可能會(huì)被安排存放到另一個(gè)位置。于是下面這種情況就會(huì)發(fā)生：由dict([(key1, value1), (key2,value2)])和dict([(key2,value2), (key1, value1)])得到的兩個(gè)字典，在進(jìn)行比較的時(shí)候，它們是相等的；但是如果在key1和key2被添加到字典里的過(guò)程中有沖突發(fā)生的話，這兩個(gè)鍵出現(xiàn)在字典里的順序是不一樣的。
  8.3 set的實(shí)現(xiàn)以及導(dǎo)致的結(jié)果
  set和frozenset的實(shí)現(xiàn)也依賴散列表，但在它們的散列表里存放的只有元素的引用（就像在字典里只存放鍵而沒(méi)有相應(yīng)的值）。在set加入到Python之前，我們都是把字典加上無(wú)意義的值當(dāng)作集合來(lái)用的。
• 集合里的元素必須是可散列的
• 集合很消耗內(nèi)存。
• 可以很高效地判斷元素是否存在于某個(gè)集合。
• 元素的次序取決于被添加到集合里的次序。
• 往集合里添加元素，可能會(huì)改變集合里已有元素的次序。