歡迎訪問我的博客：http://wangnan.tech

第五章散列表

散列表適合用于

散列函數(shù)很重要。前面的散列函數(shù)將所有的鍵都映射到一個(gè)位置，而最理想的情況是，
散列函數(shù)將鍵均勻地映射到散列表的不同位置。
如果散列表存儲(chǔ)的鏈表很長(zhǎng)，散列表的速度將急劇下降。然而，如果使用的散列函數(shù)很
好，這些鏈表就不會(huì)很長(zhǎng)！
在最糟情況下，散列表所有操作的運(yùn)行時(shí)間都為O(n)——線性時(shí)間
在平均情況下，散列表的查找（獲取給定索引處的值）速度與數(shù)組一樣快，而插入和刪除速
度與鏈表一樣快，因此它兼具兩者的優(yōu)點(diǎn)！但在最糟情況下，散列表的各種操作的速度都很慢。
因此，在使用散列表時(shí)，避開最糟情況至關(guān)重要。為此，需要避免沖突。而要避免沖突，需要有1.較低的填裝因子2.良好的散列函數(shù)。
填裝因子大于1意味著商品數(shù)量超過了數(shù)組的位置數(shù)。一旦填裝因子開始增大，你就需要在散列表中添加位置，這被稱為調(diào)整長(zhǎng)度（resizing）。
一個(gè)不錯(cuò)的經(jīng)驗(yàn)規(guī)則是：一旦填裝因子大于0.7，就調(diào)整散列表的長(zhǎng)度。
什么樣的散列函數(shù)是良好的呢？你根本不用操心——天塌下來有高個(gè)子頂著。如果你好奇，
可研究一下SHA函數(shù)

你幾乎根本不用自己去實(shí)現(xiàn)散列表，因?yàn)槟闶褂玫木幊陶Z言提供了散列表實(shí)現(xiàn)。你可使用
Python提供的散列表，并假定能夠獲得平均情況下的性能：常量時(shí)間。
散列表是一種功能強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，其操作速度快，還能讓你以不同的方式建立數(shù)據(jù)模型。
你可能很快會(huì)發(fā)現(xiàn)自己經(jīng)常在使用它。
你可以結(jié)合散列函數(shù)和數(shù)組來創(chuàng)建散列表。
沖突很糟糕，你應(yīng)使用可以最大限度減少?zèng)_突的散列函數(shù)。
散列表的查找、插入和刪除速度都非?？?。
散列表適合用于模擬映射關(guān)系。
一旦填裝因子超過0.7，就該調(diào)整散列表的長(zhǎng)度。
散列表可用于緩存數(shù)據(jù)（例如，在Web服務(wù)器上）。
散列表非常適合用于防止重復(fù)。

廣度優(yōu)先搜索指出是否有從A到B的路徑。
如果有，廣度優(yōu)先搜索將找出最短路徑。
面臨類似于尋找最短路徑的問題時(shí)，可嘗試使用圖來建立模型，再使用廣度優(yōu)先搜索來
解決問題。
有向圖中的邊為箭頭，箭頭的方向指定了關(guān)系的方向，例如，rama→adit表示rama欠adit錢。
無向圖中的邊不帶箭頭，其中的關(guān)系是雙向的，例如，ross - rachel表示“ross與rachel約
會(huì)，而rachel也與ross約會(huì)”。
隊(duì)列是先進(jìn)先出（FIFO）的。
棧是后進(jìn)先出（LIFO）的。
你需要按加入順序檢查搜索列表中的人，否則找到的就不是最短路徑，因此搜索列表必
須是隊(duì)列。
對(duì)于檢查過的人，務(wù)必不要再去檢查，否則可能導(dǎo)致無限循環(huán)。