? ? 1散列思想

? ? ? ? 散列表的英文叫“Hash Table”，所以也闊以叫它“哈希表”或者“Hash表”侨颈。

? ? ? ? 散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)數(shù)據(jù)的特性县恕，所以說(shuō)散列表就是數(shù)組的一種擴(kuò)展峰搪，由數(shù)組演化而來(lái)「鲩牛可以說(shuō)篡石，如果沒(méi)有數(shù)組，就沒(méi)有散列表西采。

? ? ? ? 舉個(gè)例子夏志，我們有100位學(xué)生參加運(yùn)動(dòng)會(huì)，它們的編號(hào)依次是1-100苛让，我們希望實(shí)現(xiàn)通過(guò)編號(hào)快速找到對(duì)應(yīng)的選手信息的功能沟蔑。我們就可以把它們存在數(shù)組里，數(shù)組下標(biāo)為1的位置存放編號(hào)為1的選手信息狱杰，數(shù)組下標(biāo)為2的位置存放編號(hào)為2的選手信息瘦材，依次類推，數(shù)組下標(biāo)為k的位置存放編號(hào)為k的選手信息仿畸。

? ? ? ? 因?yàn)閰①惥幪?hào)跟數(shù)組下標(biāo)一一對(duì)應(yīng)食棕，所以我們想要查詢編號(hào)為x的選手信息時(shí)，直接訪問(wèn)數(shù)組下標(biāo)為x的位置的數(shù)據(jù)就好啦错沽，時(shí)間復(fù)雜度是O(1)簿晓，效率超高噠。

? ? ? ? 上面這個(gè)例子其實(shí)已經(jīng)蘊(yùn)含了散列的思想千埃，但是它比較簡(jiǎn)單憔儿，散列的思想體現(xiàn)的還不夠明顯。下面我們?cè)賮?lái)一個(gè)例子放可。

? ? ? ? 假設(shè)我們想要通過(guò)學(xué)號(hào)快速找到對(duì)應(yīng)的學(xué)生信息谒臼，我們都知道朝刊，學(xué)號(hào)比較長(zhǎng)，比如這樣：17011133401蜈缤，每一位都有它的含義拾氓，這個(gè)時(shí)候我們就不能簡(jiǎn)單的將學(xué)號(hào)對(duì)應(yīng)到相應(yīng)的數(shù)組下標(biāo)上，因?yàn)閿?shù)字太大啦底哥。

? ? ? ? 盡管我們不能直接取學(xué)號(hào)作為下標(biāo)咙鞍，但是我們可以取學(xué)號(hào)的后兩位作為數(shù)組下標(biāo)，存儲(chǔ)對(duì)應(yīng)的學(xué)生信息趾徽。然后想要獲取學(xué)生信息的時(shí)候奶陈，直接用學(xué)號(hào)后兩位來(lái)找到對(duì)應(yīng)下標(biāo)的數(shù)組位置。

? ? ? ? 這就是典型的散列思想附较。其中，學(xué)號(hào)我們稱作鍵（key）或者關(guān)鍵字潦俺，用它來(lái)標(biāo)識(shí)一個(gè)學(xué)生拒课。將學(xué)號(hào)轉(zhuǎn)化為數(shù)組下標(biāo)的映射方法叫散列函數(shù)（或者哈希函數(shù)），而散列函數(shù)計(jì)算得到的值就是散列值（或者哈希值）事示。

? ? 2散列函數(shù)

? ? ? ? 剛剛我們有提到散列函數(shù)早像，它在散列表中起著非常關(guān)鍵的作用。我們可以把它定義成hash(key)肖爵。

? ? ? ? 剛剛我們?nèi)W(xué)號(hào)最后兩位作為散列值的方法就可以寫(xiě)成下面這樣卢鹦，偽代碼如下圖所示：

? ? ? ? 但是，鍵值并不總是像學(xué)號(hào)那樣是簡(jiǎn)單的并且有規(guī)律的數(shù)字劝堪，它有可能是隨機(jī)生成的數(shù)字冀自，也有可能是字符串，我們就需要用其他方法來(lái)構(gòu)造散列函數(shù)秒啦。

? ? ? ? 在構(gòu)造散列函數(shù)的時(shí)候熬粗，我們需要滿足下面三點(diǎn)基本要求：

? ? ? ? 1.散列函數(shù)計(jì)算得到的散列值是一個(gè)非負(fù)整數(shù)。

? ? ? ? 2.如果key1=key2余境，那么hash(key1)=hash(key2)驻呐。

? ? ? ? 3.如果key1!=key2，那么hash(key1)!=hash(key2)芳来。

? ? ? ? 前兩點(diǎn)比較容易滿足含末，第三點(diǎn)很難滿足，要想找到一個(gè)不同的key對(duì)應(yīng)的散列值都不一樣的散列函數(shù)即舌，幾乎是不可能的佣盒，即便是業(yè)界著名的MD5、SHA顽聂、CRC等哈希算法沼撕，也無(wú)法完全避免這種散列沖突宋雏。而且，因?yàn)閿?shù)組的存儲(chǔ)空間有限务豺，也會(huì)加大散列沖突的概率磨总。

????3散列沖突

? ? ? ? 解決散列沖突問(wèn)題有兩個(gè)方法：開(kāi)放尋址法和鏈表法。

? ? ? ? 1.開(kāi)放尋址法笼沥。

? ? ? ? 開(kāi)放尋址法的思想是蚪燕，如果出現(xiàn)了散列沖突，我們就重新探測(cè)一個(gè)空閑位置將其插入奔浅。這里講一個(gè)比較簡(jiǎn)單的探測(cè)方法：線性探測(cè)馆纳。

? ? ? ? 我們?cè)谕⒘斜碇胁迦霐?shù)據(jù)時(shí)，如果鍵值經(jīng)過(guò)散列函數(shù)處理得到的散列值已經(jīng)存在汹桦，也就是當(dāng)前下標(biāo)位置已經(jīng)存入數(shù)據(jù)了的時(shí)候鲁驶，我們就繼續(xù)往后探測(cè)，直到找到空閑位置舞骆，然后將它存入這個(gè)空閑位置钥弯。

? ? ? ? 舉個(gè)例子，如下圖所示督禽，橙色是已經(jīng)存儲(chǔ)數(shù)據(jù)的位置脆霎，黃色是空閑位置。x經(jīng)hash(key)處理后狈惫，得到的散列值是7睛蛛，但是下標(biāo)為7的位置已經(jīng)存儲(chǔ)了數(shù)據(jù)，所以就繼續(xù)向后探測(cè)空閑位置胧谈。但是直到數(shù)組尾部都沒(méi)有探測(cè)到呢忆肾，沒(méi)關(guān)系，我們繼續(xù)返回?cái)?shù)組頭部繼續(xù)探測(cè)空閑位置菱肖，找到了下標(biāo)為2的位置是空閑的难菌，將鍵值x存入。

? ? ? ? 查找與插入的方法很像蔑滓，也是通過(guò)hash(key)得到散列值郊酒，若當(dāng)前散列值下標(biāo)處存放的數(shù)據(jù)和我們要查找的數(shù)據(jù)相等，則就是我們要找的元素键袱，若不相等燎窘，則繼續(xù)向后探測(cè)。若探測(cè)到空閑位置的時(shí)候還沒(méi)有找到蹄咖，說(shuō)明要查找的元素并沒(méi)有在散列表中褐健。

? ? ? ? 下面是刪除操作，刪除操作和插入、查找的思想也基本一致蚜迅，但是要注意的是舵匾，我們不能簡(jiǎn)單的將元素直接刪除，這樣后面再查找的時(shí)候谁不，探測(cè)到這個(gè)位置還沒(méi)有找到元素坐梯，就會(huì)判定為元素不存在，有可能發(fā)生誤判刹帕，所以我們?cè)趧h除的時(shí)候吵血，需要將這個(gè)位置標(biāo)記為deleted，查找的時(shí)候探測(cè)到deleted的空間時(shí)就可以不用停下來(lái)偷溺，而是繼續(xù)向后探測(cè)蹋辅。

? ? ? ? 但是線性探測(cè)法存在的問(wèn)題是，當(dāng)散列表中插入的數(shù)據(jù)越來(lái)越多時(shí)挫掏，散列沖突發(fā)生的可能性就會(huì)越來(lái)越大侦另，空閑位置會(huì)越來(lái)越少，線性探測(cè)的時(shí)間就會(huì)越來(lái)越久尉共。極端情況下可能需要探測(cè)整個(gè)散列表褒傅，這個(gè)時(shí)候時(shí)間復(fù)雜度是O(n)。同理爸邢，刪除和查找也可能是這種情況。

? ? ? ? 所以除了線性探測(cè)方法之外拿愧，還有另外兩種比較經(jīng)典的探測(cè)方法：二次探測(cè)和雙重散列杠河。

? ? ? ? 二次探測(cè)跟線性探測(cè)很像，線性探測(cè)每次探測(cè)的步長(zhǎng)是1浇辜，而二次探測(cè)探測(cè)的步長(zhǎng)是原來(lái)的二次方券敌。

? ? ? ? 雙重散列意思就是不僅要用一個(gè)散列函數(shù)，如果通過(guò)第一個(gè)散列函數(shù)計(jì)算得到的位置已經(jīng)被占用柳洋，那么就再用第二個(gè)散列函數(shù)待诅，以此類推，直到找到空閑的存儲(chǔ)位置熊镣。

? ? ? ? 不管用哪種探測(cè)方法卑雁，當(dāng)散列表中空閑位置不多的時(shí)候，散列沖突發(fā)生的概率就會(huì)大大提高绪囱，所以為了盡可能保證散列表的操作效率测蹲，我們會(huì)盡可能去保證散列表中有一定比例的空閑槽位，我們用裝載因子來(lái)標(biāo)識(shí)空位的多少鬼吵。

? ? ? ? 裝載因子的計(jì)算公式：

? ? ? ? 裝載因子越大則散列表中空閑位置越少扣甲，發(fā)生散列沖突的概率越大，散列表的性能越低齿椅。

? ? ? ? 2.鏈表法

? ? ? ? 這種方法比線性探測(cè)法就簡(jiǎn)單多啦琉挖。

? ? ? ? 如上圖所示启泣，散列表中的每個(gè)“桶”或“槽”都對(duì)應(yīng)一條鏈表，所有散列值相同的元素我們都會(huì)放到相同槽位對(duì)應(yīng)的鏈表中去示辈。插入的時(shí)間復(fù)雜度是O(1)寥茫，查找和刪除的時(shí)間復(fù)雜度跟鏈表的長(zhǎng)度k成正比，也就是O(k)顽耳。對(duì)于散列表比較均勻地散列函數(shù)來(lái)說(shuō)坠敷，理論上講k=n/m，其中n表示散列表中數(shù)據(jù)的個(gè)數(shù)射富，m表示散列表中“槽”的個(gè)數(shù)膝迎。

? ? 4word中的單詞拼寫(xiě)檢查功能是如何實(shí)現(xiàn)的

? ? ? ? 實(shí)際上它就是通過(guò)散列表實(shí)現(xiàn)的。

? ? ? ? 我們將所有單詞都存在散列表中（常用的英文單詞有20萬(wàn)個(gè)左右胰耗，假設(shè)單詞的平均長(zhǎng)度是10個(gè)字母限次，平均一個(gè)單詞占用10個(gè)字節(jié)的內(nèi)存空間，20萬(wàn)英文單詞大約占2MB的存儲(chǔ)空間柴灯，這個(gè)大小放在內(nèi)存中完全不是問(wèn)題）卖漫。

? ? ? ? 當(dāng)用戶輸入某個(gè)英文單詞時(shí)，我們只需要在散列表中進(jìn)行查找赠群，如果沒(méi)有查到羊始，則說(shuō)明拼寫(xiě)可能有誤，就進(jìn)行拼寫(xiě)錯(cuò)誤提示查描。

? ? 5內(nèi)容小結(jié)

? ? ? ? 這節(jié)課的散列表知識(shí)都比較基礎(chǔ)突委、比較偏理論，包括散列表的由來(lái)冬三，散列函數(shù)匀油，散列沖突的解決方法。

? ? ? ? 散列表來(lái)源于數(shù)組勾笆，它借助散列函數(shù)對(duì)數(shù)組這種數(shù)據(jù)結(jié)構(gòu)進(jìn)行擴(kuò)展敌蚜，利用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問(wèn)元素的特性。散列表的兩個(gè)核心問(wèn)題是散列函數(shù)設(shè)計(jì)和散列沖突解決窝爪。散列沖突有兩種常用的解決方法：開(kāi)放尋址法和鏈表法弛车。散列函數(shù)設(shè)計(jì)的好壞決定了散列沖突的概率，也就決定散列表的性能蒲每。

? ? ? ? 后面的章節(jié)我們還會(huì)更貼近實(shí)戰(zhàn)更加深入的探討散列函數(shù)和散列沖突的問(wèn)題~? ? ??