歡迎訪問(wèn)我的博客：http://wangnan.tech
第五章 散列表
- 散列函數(shù)“將輸入映射到數(shù)字”
- 散列函數(shù)總是將同樣的輸入映射到相同的索引
- 散列函數(shù)將不同的輸入映射到不同的索引
- 散列函數(shù)知道數(shù)組有多大我擂，只返回有效的索引
- 而散列表也使用數(shù)組來(lái)存儲(chǔ)數(shù)據(jù)勤篮，因此其獲取元素的速度與數(shù)組一樣快中剩。
散列表適合用于
模擬映射關(guān)系；
防止重復(fù)师崎；
緩存/記住數(shù)據(jù)，以免服務(wù)器再通過(guò)處理來(lái)生成它們冲茸。
如果兩個(gè)鍵映射到了同一個(gè)位置邪乍，就在這個(gè)位置儲(chǔ)存一個(gè)鏈表
經(jīng)驗(yàn)
散列函數(shù)很重要。前面的散列函數(shù)將所有的鍵都映射到一個(gè)位置磷杏，而最理想的情況是溜畅，
散列函數(shù)將鍵均勻地映射到散列表的不同位置。如果散列表存儲(chǔ)的鏈表很長(zhǎng)极祸，散列表的速度將急劇下降慈格。然而，如果使用的散列函數(shù)很
好遥金，這些鏈表就不會(huì)很長(zhǎng)浴捆！在最糟情況下，散列表所有操作的運(yùn)行時(shí)間都為O(n)——線性時(shí)間
在平均情況下稿械，散列表的查找（獲取給定索引處的值）速度與數(shù)組一樣快选泻，而插入和刪除速
度與鏈表一樣快，因此它兼具兩者的優(yōu)點(diǎn)！但在最糟情況下页眯，散列表的各種操作的速度都很慢梯捕。因此，在使用散列表時(shí)窝撵，避開(kāi)最糟情況至關(guān)重要科阎。為此，需要避免沖突忿族。而要避免沖突，需要有1.較低的填裝因子2.良好的散列函數(shù)蝌矛。
填裝因子大于1意味著商品數(shù)量超過(guò)了數(shù)組的位置數(shù)道批。一旦填裝因子開(kāi)始增大，你就需要在散列表中添加位置入撒，這被稱為調(diào)整長(zhǎng)度（resizing）隆豹。
一個(gè)不錯(cuò)的經(jīng)驗(yàn)規(guī)則是：一旦填裝因子大于0.7，就調(diào)整散列表的長(zhǎng)度茅逮。
什么樣的散列函數(shù)是良好的呢璃赡？你根本不用操心——天塌下來(lái)有高個(gè)子頂著。如果你好奇献雅，
可研究一下SHA函數(shù)
小結(jié)
你幾乎根本不用自己去實(shí)現(xiàn)散列表碉考，因?yàn)槟闶褂玫木幊陶Z(yǔ)言提供了散列表實(shí)現(xiàn)。你可使用
Python提供的散列表挺身，并假定能夠獲得平均情況下的性能：常量時(shí)間侯谁。散列表是一種功能強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)，其操作速度快章钾，還能讓你以不同的方式建立數(shù)據(jù)模型墙贱。
你可能很快會(huì)發(fā)現(xiàn)自己經(jīng)常在使用它。你可以結(jié)合散列函數(shù)和數(shù)組來(lái)創(chuàng)建散列表贱傀。
沖突很糟糕惨撇，你應(yīng)使用可以最大限度減少?zèng)_突的散列函數(shù)。
散列表的查找府寒、插入和刪除速度都非晨茫快。
散列表適合用于模擬映射關(guān)系椰棘。
一旦填裝因子超過(guò)0.7纺棺，就該調(diào)整散列表的長(zhǎng)度。
散列表可用于緩存數(shù)據(jù)（例如邪狞，在Web服務(wù)器上）祷蝌。
散列表非常適合用于防止重復(fù)。
第六章 廣度優(yōu)先搜索
- 廣度優(yōu)先搜索指出是否有從A到B的路徑帆卓。
- 如果有巨朦，廣度優(yōu)先搜索將找出最短路徑米丘。
- 面臨類似于尋找最短路徑的問(wèn)題時(shí)，可嘗試使用圖來(lái)建立模型糊啡，再使用廣度優(yōu)先搜索來(lái)
解決問(wèn)題拄查。 - 有向圖中的邊為箭頭，箭頭的方向指定了關(guān)系的方向棚蓄，例如堕扶，rama→adit表示rama欠adit錢(qián)。
- 無(wú)向圖中的邊不帶箭頭梭依，其中的關(guān)系是雙向的稍算，例如，ross - rachel表示“ross與rachel約
會(huì)役拴，而rachel也與ross約會(huì)”糊探。 - 隊(duì)列是先進(jìn)先出（FIFO）的。
- 棧是后進(jìn)先出（LIFO）的河闰。
- 你需要按加入順序檢查搜索列表中的人科平，否則找到的就不是最短路徑，因此搜索列表必
須是隊(duì)列姜性。 - 對(duì)于檢查過(guò)的人瞪慧，務(wù)必不要再去檢查，否則可能導(dǎo)致無(wú)限循環(huán)部念。
