關(guān)于我
一個(gè)有思想的程序猿曾沈，終身學(xué)習(xí)實(shí)踐者这嚣，目前在一個(gè)創(chuàng)業(yè)團(tuán)隊(duì)任team lead，技術(shù)棧涉及Android塞俱、Python姐帚、Java和Go，這個(gè)也是我們團(tuán)隊(duì)的主要技術(shù)棧障涯。
Github：https://github.com/hylinux1024
微信公眾號(hào)：終身開發(fā)者(angrycode)

字典又稱為哈希表(hashmap)罐旗、映射(map)，它是以key-value的方式進(jìn)行存儲(chǔ)像樊，通過(guò)key進(jìn)行存儲(chǔ)尤莺、查找操作的效率非常高。在Python編碼中字典也是非常非常常用的一種數(shù)據(jù)結(jié)構(gòu)生棍。
今天就看下Python中有哪些實(shí)現(xiàn)字典的數(shù)據(jù)結(jié)構(gòu)颤霎。
本文中提到的代碼都是Python3.7中執(zhí)行的。

字典的存儲(chǔ)其實(shí)很像一個(gè)數(shù)組涂滴。在字典中的key對(duì)象是必須實(shí)現(xiàn)__hash__和__eq__方法的友酱。在字典在查找時(shí)會(huì)計(jì)算key的hash值，然后通過(guò)模運(yùn)算快速的定位到“數(shù)組”的下標(biāo)柔纵，如果這個(gè)下標(biāo)只有一個(gè)元素缔杉，那么就直接返回該value；如果有多個(gè)元素都存儲(chǔ)在同一個(gè)下標(biāo)里面搁料，就再使用__eq__方法進(jìn)行比較或详，相同者返回系羞。

0x00 dict

dict估計(jì)是最常用到的一種數(shù)據(jù)結(jié)構(gòu)了，可以存儲(chǔ)Python中的對(duì)象霸琴。

>>> d = {'one':1,'two':2,'three':33}
>>> d
{'one': 1, 'two': 2, 'three': 33}
# 在for循環(huán)中默認(rèn)是遍歷keys
>>> keys = [k for k in d]
>>> keys
['one', 'two', 'three']
# 也可以使用
>>> keys = [x for x in d.keys()]
>>> keys
['one', 'two', 'three']
# 遍歷values
>>> values = [v for v in d.values()]
>>> values
[1, 2, 33]
# 如果要遍歷key,value可以使用dict.items()方法椒振，它返回一個(gè)(k,v)元組
>>> kvs = [(k,v) for k,v in d.items()]
>>> kvs
[('one', 1), ('two', 2), ('three', 33)]

現(xiàn)在Python3.6以上版本中的dict是非常強(qiáng)大的，遍歷時(shí)會(huì)保持元素插入Python中的順序

>>> d = {'z':2,'a':'111','b':0.99}
>>> d
# 輸出時(shí)保持元素的插入順序
{'z': 2, 'a': '111', 'b': 0.99}

當(dāng)獲取一個(gè)不存在的key梧乘，將會(huì)拋出KeyError澎迎。

>>> d['k']
Traceback (most recent call last):
  File "<pyshell#172>", line 1, in <module>
    d['k']
KeyError: 'k'

如果不想拋出異常錯(cuò)誤信息，那么可以使用get方法选调，并可以指定當(dāng)key不存在時(shí)夹供，返回默認(rèn)值。這個(gè)方法在實(shí)際的編碼中也是非常實(shí)用的仁堪。

# 當(dāng)`key`不存在時(shí)哮洽，指定返回默認(rèn)值
>>> d.get('k',314)
314

例如在WEB應(yīng)用解析服務(wù)器端返回的json數(shù)據(jù)時(shí)，常常會(huì)把json數(shù)據(jù)解析成一個(gè)字典弦聂，如果服務(wù)端的某個(gè)字段缺失了袁铐，而客戶端使用下標(biāo)的方法來(lái)進(jìn)行訪問(wèn)元素時(shí)，就會(huì)出現(xiàn)KeyError横浑。要讓自己的程序更加健壯，那么就可以使用get方法屉更。

0x01 collections.OrderedDict

OrderedDict能保持元素的存儲(chǔ)順序徙融，如果你使用的Python版本還比較低，或者為了兼容舊版本的Python瑰谜，而且你的需求中對(duì)元素的插入順序比較重要的話欺冀，那么可以使用這個(gè)類。

>>> import collections
>>> d = collections.OrderedDict(one=1, two=2, three=3)
>>> d
OrderedDict([('one', 1), ('two', 2), ('three', 3)])
>>> d['one']
1
>>> d['four']
# 同樣地萨脑，如果key不存在隐轩，也會(huì)拋出KeyError
KeyError: 'four'
>>> d.get('four',4)
4
>>> d.keys()
odict_keys(['one', 'two', 'three'])
>>> d.items()
odict_items([('one', 1), ('two', 2), ('three', 3)])

0x02 collections.defaultdict

當(dāng)獲取一個(gè)不存在的key時(shí)提供默認(rèn)值。defaultdict在構(gòu)造的時(shí)候就需要提供一個(gè)默認(rèn)類型渤早，用于當(dāng)key不存在時(shí)职车，構(gòu)造默認(rèn)的類型。

例如我構(gòu)造一個(gè)用戶未讀數(shù)列表鹊杖，通過(guò)用戶ID來(lái)獲取用戶的未讀數(shù)悴灵，當(dāng)在字典中沒有找到用戶ID時(shí)，默認(rèn)的未讀數(shù)就是0骂蓖。

>>> from collections import defaultdict
# 使用defaultdict構(gòu)造一個(gè)用戶未讀數(shù)字典积瞒，并傳入int類型作為默認(rèn)值的類型
>>> user_unreads = defaultdict(int)
# 給ID為123，121登下，120的用戶添加的未讀數(shù)
>>> user_unreads[123]=2
>>> user_unreads['121']=3
>>> user_unreads['120']=9
>>> user_unreads
defaultdict(<class 'int'>, {123: 2, '121': 3, '120': 9})
>>> user_unreads['121']
3
# 當(dāng)獲取一個(gè)不存在的字典中的用戶ID時(shí)茫孔，使用默認(rèn)值
>>> user_unreads['129']
0

defaultdict構(gòu)造函數(shù)還是可以使用其它類型叮喳，例如list

>>> dd = defaultdict(list)
>>> dd
defaultdict(<class 'list'>, {})
>>> dd['user_list']
[]
>>> dd['user_list'].append('jack')
>>> dd['user_list'].append('tom')
>>> dd['user_list'].append('rose')
>>> dd
defaultdict(<class 'list'>, {'user_list': ['jack', 'tom', 'rose']})

0x03 collections.ChainMap

ChainMap類可以方便地處理多個(gè)字典的操作。例如將兩個(gè)字典拼接到一起

>>> from collections import ChainMap
>>> d1 = {'one': 1, 'two': 2}
>>> d2 = {'three': 3, 'four': 4}
>>> chain = ChainMap(d1, d2)
>>> chain
ChainMap({'one': 1, 'two': 2}, {'three': 3, 'four': 4})
>>> chain['two']
2
>>> chain['five']
# 獲取一個(gè)不存在的key缰贝，會(huì)拋出KeyError
KeyError: 'five'

0x04 types.MappingProxyType

types.MappingProxyType類可以構(gòu)造一個(gè)只讀的字典馍悟，這個(gè)對(duì)數(shù)據(jù)的封裝和控制非常有用。例如當(dāng)我們不希望有人修改我們的數(shù)據(jù)時(shí)揩瞪，可以考慮使用這個(gè)類赋朦。

該類內(nèi)部其實(shí)是對(duì)內(nèi)置dict的封裝，對(duì)外提供一個(gè)只讀接口李破，當(dāng)被封裝的類修改了宠哄，這MappingProxyType的對(duì)象也會(huì)發(fā)生變化。

>>> from types import MappingProxyType
# 構(gòu)造一個(gè)普通的字典
>>> writable = {'one': 1, 'two': 2}
# 通過(guò)MappingProxyType構(gòu)造函數(shù)封裝字典
>>> read_only = MappingProxyType(writable)
>>> read_only['one']
1
>>> read_only['one'] = 23
# 如果對(duì)mappingproxy對(duì)象進(jìn)行修改嗤攻，則會(huì)拋出異常
TypeError: 'mappingproxy' object does not support item assignment
# 可以對(duì)原始對(duì)象進(jìn)行修改毛嫉，這個(gè)修改也會(huì)立刻響應(yīng)到mappingproxy對(duì)象中去
>>> writable['one'] = 42
>>> read_only
mappingproxy({'one': 42, 'two': 2})

0x05 總結(jié)一下

一般來(lái)說(shuō)，內(nèi)置dict對(duì)象已經(jīng)足以滿足我們大部分的需求開發(fā)妇菱，這也是我們使用字典這種數(shù)據(jù)類型的首選的數(shù)據(jù)結(jié)構(gòu)承粤。如果你有其它一些特殊需求，可以看看這里列出的OrderedDict闯团、defaultdict辛臊、ChainMap和MappingProxyType。

0x06 學(xué)習(xí)資料

• https://docs.python.org/3/library/collections.html#collections.OrderedDict
• Python Tricks: A Buffet of Awesome Python Features
  ——Dan Bader