所謂Python中字典的概念，簡單理解就是一個(gè)鍵值對(duì)映射的數(shù)據(jù)模型。在collections庫中有abc.Mapping和abc.MutableMapping兩個(gè)抽象基類，用于定義標(biāo)準(zhǔn)的鍵值對(duì)數(shù)據(jù)結(jié)構(gòu)接口。一般情況下，可以通過自定義繼承dict或者collections.User.Dict來實(shí)現(xiàn)自定義的鍵值對(duì)映射數(shù)據(jù)結(jié)構(gòu)。
Python中的dict內(nèi)部使用散列表(Hash Table)來優(yōu)化查找效率。這就要求dict（包括各種自定義實(shí)現(xiàn)）內(nèi)的元素的鍵（值沒有要求）必須是可散列的。
關(guān)于可散列：

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

一般來講，不可變數(shù)據(jù)結(jié)構(gòu)都是可散列的，但這并不絕對(duì)，準(zhǔn)確來說，只有當(dāng)數(shù)據(jù)結(jié)構(gòu)中所有元素都是不可變的時(shí)候，不可變元素才是可散列的。

一般來講用戶自定義的類型的對(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ì)象才是可散列的。

在dict的實(shí)際使用當(dāng)中，經(jīng)常面對(duì)對(duì)于不存在鍵給出一個(gè)默認(rèn)值的情況。

1. setdefault

import sys
import re

WORD_RE = re.compile(r'\w+')

index = {}
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start()+1
            location = (line_no, column_no)
            index.setdefault(word, []).append(location) 

# 以字母順序打印出結(jié)果
for word in sorted(index, key=str.upper):
    print(word, index[word])

上面代碼段中：

index.setdefault(word, []).append(location) 

其實(shí)是和下面代碼段等效的：

if word not in index:
    index[key] = []
index[key].append(new_value)

不過后者需要兩次鍵查詢，而前者只需要一次。

2. defaultdict
   collections內(nèi)置的數(shù)據(jù)結(jié)構(gòu)defaultdict目的就是為了解決不存在鍵默認(rèn)值的問題。

import sys
import re
import collections

WORD_RE = re.compile(r'\w+')

index = collections.defaultdict(list) 
with open(sys.argv[1], encoding='utf-8') as fp:
    for line_no, line in enumerate(fp, 1):
        for match in WORD_RE.finditer(line):
            word = match.group()
            column_no = match.start()+1
            location = (line_no, column_no)
            index[word].append(location) 

for word in sorted(index, key=str.upper):
    print(word, index[word])

需要注意的是，defaultdict初始化時(shí)的默認(rèn)值方法，針對(duì)的是__getitem__，也就是說在index[word]這種調(diào)用形式，而使用index.get(word)返回值依舊是None。

3. __missing__
   當(dāng)映射找不到鍵的時(shí)候，都會(huì)觸發(fā)__missing__方法。

__missing__方法只會(huì)被 __getitem__ 調(diào)用（比如在表達(dá)式 d[k] 中）。提供__missing__ 方法對(duì) get 或者 __contains__ （ in 運(yùn)算符會(huì)用到這個(gè)方法）這些方法的使用沒有影響。這也是 defaultdict 中的 default_factory 只對(duì) __getitem__ 有作用的原因。

Python中的集合同樣在內(nèi)部使用了散列來優(yōu)化查找，不同的是，集合本身不是鍵值對(duì)，而是一個(gè)對(duì)象的集合。（set無序，frozenset有序）

在dict當(dāng)中：

1. 鍵必須是可散列的
   所謂可散列，需要滿足下面要求：

(1) 支持 hash() 函數(shù)，并且通過 hash() 方法所得到的散列值是不變的。
(2) 支持通過 eq() 方法來檢測相等性。
(3) 若 a == b 為真，則 hash(a) == hash(b) 也為真。

2.字典在內(nèi)存上的開銷巨大
散列表本身就是一種用空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)，當(dāng)存在大量數(shù)據(jù)需要處理的時(shí)候，可能會(huì)對(duì)內(nèi)存造成很大的壓力。
如果你手頭有幾百萬個(gè)對(duì)象，而你的機(jī)器有幾個(gè) GB 的內(nèi)存，那么空間的優(yōu)化工作可以等到真正需要的時(shí)候再開始計(jì)劃，因?yàn)閮?yōu)化往往是可維護(hù)性的對(duì)立面。

3. 鍵查詢很快
   鍵查詢是O（1）級(jí)別的。

4. 鍵的次序取決于添加順序
   當(dāng)往 dict 里添加新鍵而又發(fā)生散列沖突的時(shí)候，新鍵可能會(huì)被安排存放到另一個(gè)位置。請(qǐng)記住，一個(gè)良好設(shè)計(jì)的散列函數(shù)發(fā)生沖突的概率是極低的。

5. 往字典里添加新鍵可能會(huì)改變已有鍵的順序
   無論何時(shí)往字典里添加新的鍵，Python 解釋器都可能做出為字典擴(kuò)容的決定。擴(kuò)容導(dǎo)致的結(jié)果就是要新建一個(gè)更大的散列表，并把字典里已有的元素添加到新表里。在此過程中如果發(fā)生新的沖突，有可能會(huì)改變鍵的次序。

在set和frozenset中：

? 集合里的元素必須是可散列的。
? 集合很消耗內(nèi)存。
? 可以很高效地判斷元素是否存在于某個(gè)集合。
? 元素的次序取決于被添加到集合里的次序。
? 往集合里添加元素，可能會(huì)改變集合里已有元素的次序。