散列表——最有用的基本數(shù)據(jù)結(jié)構(gòu)之一坤候，用途廣泛。
散列表的內(nèi)部機(jī)制：實(shí)現(xiàn)枪眉、沖突和散列函數(shù)。
假設(shè)你在一家雜貨店上班预明。有顧客來(lái)買東西時(shí)，你得在一個(gè)本子中查找價(jià)格耙箍。如果本子的內(nèi)容不是按字母順序排列的撰糠，你可能為查找蘋果 （apple）的價(jià)格而瀏覽每一行，這需要很長(zhǎng)的時(shí)間辩昆。
散列函數(shù)
無(wú)論你給它什么數(shù)據(jù)阅酪，它都還你一個(gè)數(shù)字。散列函數(shù)
將輸入映射到數(shù)字
實(shí)散列函數(shù)必須滿足一些要求汁针。它必須是一致的术辐。
最理想的情況是，將不同的輸入映射到不同的數(shù)字施无。
散列表 （hash table）的數(shù)據(jù)結(jié)構(gòu)辉词。種包含額外邏輯的數(shù)據(jù)結(jié)構(gòu)。
數(shù)組和鏈表都被直接映射到內(nèi)存猾骡，但散列表更復(fù)雜瑞躺，它使用散列函數(shù)來(lái)確定元素的存儲(chǔ)位置。
散列表由
鍵和值組成兴想。
將散列表用于查找
假設(shè)你要?jiǎng)?chuàng)建一個(gè)類似這樣的電話簿隘蝎，將姓名映射到電話號(hào)碼。該電話簿需要提供如下功能襟企。添加聯(lián)系人及其電話號(hào)碼嘱么。通過(guò)輸入聯(lián)系人來(lái)獲悉其電話號(hào)碼。
phone_book = dict()
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
print phone_book["jenny"]
#8675309
如果要求你使用數(shù)組來(lái)創(chuàng)建電話簿顽悼，你將如何做呢曼振？
散列表被用于大海撈針式的查找。訪問(wèn)網(wǎng)站時(shí)蔚龙，計(jì)算機(jī)必須將adit.io轉(zhuǎn)換為IP地址冰评。無(wú)論你訪問(wèn)哪個(gè)網(wǎng)站，其網(wǎng)址都必須轉(zhuǎn)換為IP地址木羹。這不是將網(wǎng)址映射到IP地址嗎甲雅？好像非常適合使用散列表啰！這個(gè)過(guò)程被稱為DNS解析 （DNS resolution）坑填，散列表是提供這種功能的方式之一抛人。
防止重復(fù)
假設(shè)你負(fù)責(zé)管理一個(gè)投票站。顯然脐瑰，每人只能投一票妖枚，但如何避免重復(fù)投票呢？有人來(lái)投票時(shí)苍在，你詢問(wèn)他的全名绝页，并將其與已投票者名單進(jìn)行比對(duì)荠商。如果名字在名單中，就說(shuō)明這個(gè)人投過(guò)票了续誉，因此將他拒之門外莱没！
voted = {}
def check_voter(name):
if voted.get(name):
print "kick them out!"
else:
voted[name] = True
print "let them vote!"
將散列表用作緩存
假設(shè)你訪問(wèn)網(wǎng)站facebook.com。
(1) 你向Facebook的服務(wù)器發(fā)出請(qǐng)求酷鸦。
(2) 服務(wù)器做些處理饰躲，生成一個(gè)網(wǎng)頁(yè)并將其發(fā)送給你。
(3) 你獲得一個(gè)網(wǎng)頁(yè)井佑。
緩存的工作原理：網(wǎng)站將數(shù)據(jù)記住属铁，而不再重新計(jì)算。
緩存是一種常用的加速方式躬翁，所有大型網(wǎng)站都使用緩存焦蘑，而緩存的數(shù)據(jù)則存儲(chǔ)在散列表中！
當(dāng)你訪問(wèn)Facebook的頁(yè)面時(shí)盒发，它首先檢查散列表中是否存儲(chǔ)了該頁(yè)面例嘱。
cache = {}
def get_page(url):
if cache.get(url):
return cache[url] # 返回緩存的數(shù)據(jù)
else:
data = get_data_from_server(url)
cache[url] = data # 先將數(shù)據(jù)保存到緩存中
return data
沖突
給兩個(gè)鍵分配的位置相同，這種情況被稱為
沖突（collision）：
如果兩個(gè)鍵映射到了同一個(gè)位置宁舰，就在這個(gè)位置存儲(chǔ)一個(gè)鏈表拼卵。
散列函數(shù)將所有的鍵都映射到一個(gè)位置，而最理想的情況是蛮艰，散列函數(shù)將鍵均勻地映射到散列表的不同位置腋腮。
著無(wú)論散列表包含一個(gè)元素還是10億個(gè)元素，從其中獲取數(shù)據(jù)所需的時(shí)間都相同壤蚜。
而要避免沖突即寡，需要有：
- 較低的填裝因子；
- 良好的散列函數(shù)袜刷。
填裝因子
散列表的填裝因子很容易計(jì)算聪富。散列表使用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)，因此你需要計(jì)算數(shù)組中被占用的位置數(shù)著蟹。
填裝因子度量的是散列表中有多少位置是空的墩蔓。
填裝因子大于1意味著商品數(shù)量超過(guò)了數(shù)組的位置數(shù)。一旦填裝因子開(kāi)始增大萧豆，你就需要在散列表中添加位置奸披，這被稱為調(diào)整長(zhǎng)度。
填裝因子越低炕横，發(fā)生沖突的可能性越小源内，散列表的性能越高。
一個(gè)不錯(cuò)的經(jīng)驗(yàn)規(guī)則是：一旦填裝因子大于0.7份殿，就調(diào)整散列表的長(zhǎng)度膜钓。
良好的散列函數(shù)
良好的散列函數(shù)讓數(shù)組中的值呈均勻分布。糟糕的散列函數(shù)讓值扎堆卿嘲，導(dǎo)致大量的沖突颂斜。
什么樣的散列函數(shù)是良好的呢？你根本不用操心——天塌下來(lái)有高個(gè)子頂著拾枣。
