Python的字典是如何工作的
在Python中喇勋，字典也就是一個(gè)個(gè)的“映射”，將key映射到value：
# 對(duì)一個(gè)特定的key可以得到一個(gè)value value = d[key]
為了實(shí)現(xiàn)這個(gè)功能偎行，Python必須能夠做到川背，給出一個(gè)key，找到哪一個(gè)value與這個(gè)key對(duì)應(yīng)蛤袒。先來(lái)考慮一種比較簡(jiǎn)單的實(shí)現(xiàn)熄云，將所有的key-value鍵值對(duì)存放到一個(gè)list中，每當(dāng)需要的時(shí)候妙真，就去遍歷這個(gè)list缴允，用key去和鍵值對(duì)的key匹配，如果相等珍德，就拿到value练般。但是這種實(shí)現(xiàn)在數(shù)據(jù)量很大的時(shí)候就變得很低效。它的算法復(fù)雜度是O(n)锈候，n是存放鍵值對(duì)的數(shù)量薄料。
為此，Python使用了hash（哈希）的方法來(lái)實(shí)現(xiàn)泵琳，要求每一個(gè)存放到字典中的對(duì)象都要實(shí)現(xiàn)hash函數(shù)摄职，這個(gè)函數(shù)可以產(chǎn)生一個(gè)int值誊役，叫做hash value（哈希值），通過(guò)這個(gè)int值谷市，就可以快速確定對(duì)象在字典中的位置蛔垢。
這個(gè)查詢的大致過(guò)程如下：
def lookup(d, key): '''字典的查詢過(guò)程概括為下面3步: 1. 通過(guò)hash函數(shù)將key計(jì)算為哈希值. 2. 通過(guò)hash值確定一個(gè)位置，這個(gè)位置是一個(gè)存放著 可能存在沖突的元素的數(shù)組（很多地方叫做“桶”迫悠，bucket）鹏漆， 每一個(gè)元素都是一個(gè)鍵值對(duì)，理想情況下及皂，這個(gè)數(shù)組里只有1個(gè)元素. 3. 遍歷這個(gè)數(shù)組甫男，找到目標(biāo)key，返回對(duì)應(yīng)的value. ''' h = hash(key)# step 1 cl = d.data[h]# step 2 for pairin cl:# step 3 if key == pair[0]: return pair[1] else: raise KeyError, "Key %s not found." % key
要使這個(gè)查找過(guò)程正常工作验烧，hash函數(shù)必須滿足條件： 如果兩個(gè)key產(chǎn)生了不同的hash value，那么這兩個(gè)key對(duì)象是不想等的又跛。 即
for alli1, i2, if hash(i1) != hash(i2), then i1 != i2
否則的話碍拆，hash value不同，對(duì)象卻相同慨蓝，那么相同的對(duì)象產(chǎn)生不同的hash value感混，查找的時(shí)候就會(huì)進(jìn)錯(cuò)桶（step 2），在錯(cuò)誤的桶里永遠(yuǎn)也找不到你要找的value礼烈。
另外弧满，要讓字典保持高查找效率，還要保證： 當(dāng)兩個(gè)key產(chǎn)生相同的hash value此熬，那么他們是相等的庭呜。
for alli1, i2, if hash(i1) == hash(i2), then i1 == i2
這樣做的目的是，盡量滿足每個(gè)hash桶只有一個(gè)元素犀忱。為什么要這樣呢募谎？ 考慮下面這個(gè)hash函數(shù)。
def hash(obj): return 1
這個(gè)hash函數(shù)是滿足上面我們談的第一個(gè)條件的：如果兩個(gè)key的hash value不同阴汇，那么兩個(gè)key對(duì)象不相同数冬。因?yàn)樗械膶?duì)象產(chǎn)生的hash value都是1，所以不存在能產(chǎn)生不同hash value的key搀庶，也就不存在不滿足的情況拐纱。但是這樣做的壞處是，因?yàn)樗械膆ash value都相同哥倔，所以就把所有的對(duì)象分到了同一個(gè)地方秸架。查找的時(shí)候，進(jìn)行到第三步未斑，遍歷的效率就變成了O(n).
Hash函數(shù)應(yīng)該保證所有的元素平均的分配到每一個(gè)桶中咕宿，理想的情況是币绩，每一個(gè)位置只有一個(gè)元素。
字典Key要滿足的要求
經(jīng)過(guò)上面的討論府阀，我們應(yīng)該明白Python為什么對(duì)字典的key有這樣的要求了：
要作為字典的key缆镣，對(duì)象必須要支持hash函數(shù)（即__hash__），相等比較(__eq__或__cmp__）试浙，并且滿足上面我們討論過(guò)的條件董瞻。
List為什么不能作為key
至于這個(gè)問(wèn)題，最直接的答案就是：list沒(méi)有支持__hash__方法田巴，那么為什么呢钠糊？
對(duì)于list的hash函數(shù)，我們可能有下面兩種實(shí)現(xiàn)的方式：
第一種壹哺，基于id抄伍。這滿足條件，“如果hash值不同管宵，那么他們的id當(dāng)然不同”截珍。但考慮到list一般是作為容器，基于id來(lái)hash可能會(huì)導(dǎo)致下面兩種情況：
用相同的list作為key去字典中找某個(gè)元素可能會(huì)得到不同的結(jié)果箩朴，因?yàn)槭腔趇d hash的岗喉，所以即使他們的內(nèi)容相同，字典依然將他們作為不同的元素對(duì)待炸庞。 創(chuàng)建一個(gè)一模一樣的list用字典查找永遠(yuǎn)會(huì)得到一個(gè)KeyError钱床。
第二種，基于內(nèi)容埠居。tuple就是這樣做的查牌，但是要注意一點(diǎn)，list是可以修改的拐格。當(dāng)list修改之后僧免，你就永遠(yuǎn)別想再?gòu)淖值渲心没貋?lái)了。見下面的代碼捏浊。
>>> l = [1, 2] >>> d = {} >>> d[l] = 42 >>> l.append(3) >>> d[l] # 原來(lái)的hash值是基于[1, 2]hash的懂衩， # 現(xiàn)在是基于[1, 2, 3]，所以找不到 Traceback (mostrecentcalllast): File "", line 1, in ? KeyError: [1, 2, 3] >>> d[[1, 2]] # 基于hash [1, 2] # 但是遍歷的時(shí)候找不到key相等的鍵值對(duì) #（因?yàn)樽值淅锏膋ey變成了[1, 2, 3] Traceback (mostrecentcalllast): File "", line 1, in ? KeyError: [1, 2]
鑒于兩種實(shí)現(xiàn)的方式都存在一定的副作用金踪，所以Python規(guī)定：
內(nèi)置的list不能作為字典的key.
但tuple是不可變浊洞，所以tuple可以作為字典的key。
自定義的類型作為字典的Key
用戶自定義的類型就可以作為key了胡岔，默認(rèn)的 hash(object) 是 id(object) , 默認(rèn)的 cmp(object1,object2) 是 cmp(id(object1),id(object2))法希， 同樣是可以修改的對(duì)象，為什么這里就沒(méi)有上面說(shuō)的問(wèn)題呢靶瘸？
一般來(lái)說(shuō)苫亦，在映射中比較常見的需求是用一個(gè)object替換掉原來(lái)的毛肋，所以id比內(nèi)容更重要，就可以基于id來(lái)hash 如果內(nèi)容重要的話屋剑，自定義的類型可以通過(guò)覆蓋__hash__函數(shù)和__cmp__函數(shù)或__eq__函數(shù)來(lái)實(shí)現(xiàn)
值得注意的是：將對(duì)象和一個(gè)value關(guān)聯(lián)起來(lái)润匙，更好的做法是將value設(shè)置為對(duì)象的一個(gè)屬性。
