散列表——最有用的基本數(shù)據(jù)結(jié)構(gòu)之一，用途廣泛。
散列表的內(nèi)部機(jī)制：實(shí)現(xiàn)、沖突和散列函數(shù)。
假設(shè)你在一家雜貨店上班。有顧客來買東西時(shí)，你得在一個(gè)本子中查找價(jià)格。如果本子的內(nèi)容不是按字母順序排列的，你可能為查找蘋果 （apple）的價(jià)格而瀏覽每一行，這需要很長(zhǎng)的時(shí)間。
散列函數(shù)
無論你給它什么數(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ù)來確定元素的存儲(chǔ)位置。
散列表由
鍵和值組成。
將散列表用于查找
假設(shè)你要?jiǎng)?chuàng)建一個(gè)類似這樣的電話簿，將姓名映射到電話號(hào)碼。該電話簿需要提供如下功能。添加聯(lián)系人及其電話號(hào)碼。通過輸入聯(lián)系人來獲悉其電話號(hào)碼。
phone_book = dict()
phone_book["jenny"] = 8675309
phone_book["emergency"] = 911
print phone_book["jenny"]
#8675309
如果要求你使用數(shù)組來創(chuàng)建電話簿，你將如何做呢？
散列表被用于大海撈針式的查找。訪問網(wǎng)站時(shí)，計(jì)算機(jī)必須將adit.io轉(zhuǎn)換為IP地址。無論你訪問哪個(gè)網(wǎng)站，其網(wǎng)址都必須轉(zhuǎn)換為IP地址。這不是將網(wǎng)址映射到IP地址嗎？好像非常適合使用散列表啰！這個(gè)過程被稱為DNS解析 （DNS resolution），散列表是提供這種功能的方式之一。
防止重復(fù)
假設(shè)你負(fù)責(zé)管理一個(gè)投票站。顯然，每人只能投一票，但如何避免重復(fù)投票呢？有人來投票時(shí)，你詢問他的全名，并將其與已投票者名單進(jìn)行比對(duì)。如果名字在名單中，就說明這個(gè)人投過票了，因此將他拒之門外！
voted = {}
def check_voter(name):
if voted.get(name):
print "kick them out!"
else:
voted[name] = True
print "let them vote!"
將散列表用作緩存
假設(shè)你訪問網(wǎng)站facebook.com。
(1) 你向Facebook的服務(wù)器發(fā)出請(qǐng)求。
(2) 服務(wù)器做些處理，生成一個(gè)網(wǎng)頁并將其發(fā)送給你。
(3) 你獲得一個(gè)網(wǎng)頁。
緩存的工作原理：網(wǎng)站將數(shù)據(jù)記住，而不再重新計(jì)算。
緩存是一種常用的加速方式，所有大型網(wǎng)站都使用緩存，而緩存的數(shù)據(jù)則存儲(chǔ)在散列表中！
當(dāng)你訪問Facebook的頁面時(shí)，它首先檢查散列表中是否存儲(chǔ)了該頁面。
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ù)將鍵均勻地映射到散列表的不同位置。
著無論散列表包含一個(gè)元素還是10億個(gè)元素，從其中獲取數(shù)據(jù)所需的時(shí)間都相同。
而要避免沖突，需要有：
- 較低的填裝因子；
- 良好的散列函數(shù)。
填裝因子
散列表的填裝因子很容易計(jì)算。散列表使用數(shù)組來存儲(chǔ)數(shù)據(jù)，因此你需要計(jì)算數(shù)組中被占用的位置數(shù)。
填裝因子度量的是散列表中有多少位置是空的。
填裝因子大于1意味著商品數(shù)量超過了數(shù)組的位置數(shù)。一旦填裝因子開始增大，你就需要在散列表中添加位置，這被稱為調(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ù)是良好的呢？你根本不用操心——天塌下來有高個(gè)子頂著。
