數(shù)據(jù)結(jié)構(gòu)與算法之美筆記——散列表（上）

摘要:

「散列表」（Hash Table）或「Hash 表」是基于數(shù)組擴(kuò)展的數(shù)據(jù)結(jié)構(gòu)屉佳，能夠?qū)?fù)雜信息通過「Hash 算法」生成「Hash 值」武花，以對應(yīng)數(shù)組下標(biāo)，完成快速隨機訪問數(shù)據(jù)的功能专钉。

"我"從哪里來

我們已經(jīng)知道隨機訪問數(shù)組元素時間復(fù)雜度只有 $O(1)$ ，效率極高炮沐，當(dāng)我們想利用數(shù)組的這個特性時就需要將元素下標(biāo)與存儲信息對應(yīng)大年。例如翔试，一個商店只有四件商品复旬，依次編號 0 至 3驹碍，這樣就可以將四件商品信息按照編號對應(yīng)下標(biāo)的方式存儲到數(shù)組中，依據(jù)編號就可以快速從數(shù)組中找到相應(yīng)商品信息怔球。

如果一段時間之后，商店盈利并且重新進(jìn)貨 100 件商品钧舌，商家想對大量商品在編號上區(qū)分類別，這時候需要使用類別編號加順序編號的方式標(biāo)識每件商品洼冻，這種編號變得復(fù)雜撞牢，并不能直接對應(yīng)數(shù)組下標(biāo)，此時的商品編號又該如何對應(yīng)數(shù)組下標(biāo)以實現(xiàn)快速查找商品的功能播掷？這時候我們可以將類別編號去除之后按照順序編號對應(yīng)數(shù)組下標(biāo)，同樣也能享受數(shù)組高效率隨機訪問的福利砰嘁。這個例子中，商品編號稱為「鍵」或「關(guān)鍵字」斟冕，將鍵轉(zhuǎn)化為數(shù)組對應(yīng)下標(biāo)的方法就是「散列函數(shù)」或「Hash 函數(shù)」磕蛇，由散列函數(shù)生成的值叫做「散列值」或「Hash 值」秀撇，而這樣的數(shù)組就是散列表向族。

散列表的關(guān)鍵

從散列表的原理來看再扭，數(shù)據(jù)通過散列函數(shù)計算得到散列值是關(guān)鍵泛范，這個步驟中散列函數(shù)又是其中的核心紊撕，一個散列函數(shù)需要遵守以下三個原則柠傍。

生成的散列值是非負(fù)整數(shù)
如果 $k_1=k_2$ 惧笛，那么 $hash(k_1)=hash(k_2)$
如果 $k_1\neq{k_2}$ 逞泄，那么 $hash(k_1)\neq{hash(k_2)}$

因為散列函數(shù)生成的散列值對應(yīng)數(shù)組下標(biāo)喷众，而數(shù)組下標(biāo)就是非負(fù)整數(shù)到千，所以需要滿足第一個原則憔四；兩個相等的數(shù)據(jù)經(jīng)過散列算法得到的散列值肯定相等般眉，否則利用散列值在散列表中查找數(shù)據(jù)就無從談起甸赃；至于第三個原則雖然在情理之中埠对，卻不那么容易做到鸠窗，即使是被廣泛運用的散列算法也會出現(xiàn)散列值沖突的情況稍计，導(dǎo)致無法滿足第三個原則臣嚣。

散列函數(shù)作為散列表的核心部分硅则，必然不能拖散列表的執(zhí)行效率后腿怎虫，畢竟散列表的查詢大审、插入和刪除操作都需要經(jīng)過散列函數(shù)，所以散列函數(shù)不能太復(fù)雜根穷，執(zhí)行效率不能太低屿良。由于散列函數(shù)不可避免地都會出現(xiàn)散列沖突情況尘惧，散列函數(shù)要盡量降低散列沖突，使散列值能夠均勻地分布在散列表中。

如何解決散列沖突

解決散列沖突主要有「開放尋址」（open addressing）和「鏈表法」（chaining）兩類方法谅将。

開放尋址

開放尋址法是指插入操作時漾狼，當(dāng)生成的散列值對應(yīng)槽位已經(jīng)被其他數(shù)據(jù)占用重慢，就探測空閑位置供插入使用饥臂，其中探測方法又分為「線性探測」（Linear Probing）、「二次探測」（Quadratic Probing）和「雙重散列」（Double hashing）三種似踱。

三種探測方法

線性探測是其中較為簡單的一種隅熙，這種探測方式是當(dāng)遇到散列沖突的情況就順序查找（查找到數(shù)組尾部時轉(zhuǎn)向數(shù)組頭部繼續(xù)查找），直到查找到空槽將數(shù)據(jù)插入核芽。當(dāng)進(jìn)行查找操作時囚戚，也是同樣的操作，利用散列值從散列表中取出對應(yīng)元素轧简，與目標(biāo)數(shù)據(jù)比對，如果不相等就繼續(xù)順序查找，直到查找到對應(yīng)元素或遇到空槽為止，最壞情況下查找操作的時間復(fù)雜度可能會下降為 $O(n)$ 睹限。

散列表除了支持插入和查找操作外顺囊，當(dāng)然也支持刪除操作晕换，不過并不能將需刪除的元素置為空。如果刪除操作是將元素置為空的話敏释，查找操作遇到空槽就會結(jié)束蜂大，存儲在被刪除元素之后的數(shù)據(jù)就可能無法正確查找到澳叉，這時的刪除操作應(yīng)該使用標(biāo)記的方式所踊，而不是使用將元素置空，當(dāng)查找到被標(biāo)識已刪除的元素將繼續(xù)查找，而不是就此停止慈鸠。

線性探測是一次一個元素的探測督笆，二次探測就是使用都是線性探測的二次方步長探測。例如線性探測是 $hash(key)+0, hash(key)+1, hash(key)+2,...$ 嫂伞，那二次探測對應(yīng)的就是 $hash(key)+0^2, hash(key)+1^2, hash(key)+2^2,...$ 。

雙重探測是當(dāng)?shù)谝粋€散列函數(shù)沖突時使用第二個散列函數(shù)運算散列值刊驴，利用這種方式探測躲惰。例如诡宗，當(dāng) $hash_1(key)$ 沖突時蛀柴，就使用 $hash_2(key)$ 計算散列值，如果再沖突就使用 $hash_3(key)$ 計算散列值超燃，依此類推圣猎。

動態(tài)擴(kuò)容的困境

關(guān)于散列表的空位多少使用「裝載因子」（load factor）表示欠啤，裝載因子滿足數(shù)學(xué)關(guān)系 $裝載因子=\frac{散列表已存儲數(shù)據(jù)量}{散列表可存儲數(shù)據(jù)總量}$ 疾呻，也就是說裝載因子越大蟆肆，散列表的空閑空間越小，散列沖突的可能性也就越大赁温，一般我們會保持散列表有一定比例的空閑空間股囊。

為了保持散列表一定比例的空閑空間居灯，在裝載因子到達(dá)一定閾值時需要對散列表數(shù)據(jù)進(jìn)行搬移岩灭，但散列表搬移比較耗時。你可以試想下這樣的步驟珍德，在申請一個新的更大的散列表空間后蛔垢，需要將舊散列表的數(shù)據(jù)重新通過散列函數(shù)生成散列值巩梢，再存儲到新散列表中创泄，想想都覺得麻煩。

散列表搬移的操作肯定會降低散列表的操作效率括蝠，那能不能對這一過程進(jìn)行改進(jìn)验烧？其實可以將低效的擴(kuò)容操作分?jǐn)傊敛迦氩僮鳎?dāng)裝載因子達(dá)到閾值時不一次性進(jìn)行散列表搬移又跛，而是在每次插入操作時將一個舊散列表數(shù)據(jù)搬移至新散列表碍拆，這樣搬移操作的執(zhí)行效率得到了提高，插入操作的時間復(fù)雜度也依然能保持 $O(1)$ 的高效慨蓝。當(dāng)新舊兩個散列表同時存在時查詢操作就要略作修改感混，需先在新散列表中查詢，如果沒有查找到目標(biāo)數(shù)據(jù)再到舊散列表中查找礼烈。

當(dāng)然弧满，如果你對內(nèi)存有更高效的利用要求，可以在裝載因子降低至某一閾值時對散列表進(jìn)行縮容處理此熬。

鏈表法

除了開放尋址之外庭呜，還可以使用鏈表法解決散列沖突的問題。散列值對應(yīng)的槽位并不直接存儲數(shù)據(jù)犀忱，而是將數(shù)據(jù)存儲在槽位對應(yīng)的鏈表上募谎，當(dāng)進(jìn)行查找操作時，根據(jù)散列函數(shù)計算的散列值找到對應(yīng)槽位阴汇，再在槽位對應(yīng)的鏈表上查找對應(yīng)數(shù)據(jù)数冬。

鏈表法操作的時間復(fù)雜度與散列表槽位和數(shù)據(jù)在槽位上的分布情況有關(guān)，假設(shè)有 n 個數(shù)據(jù)均勻分布在 m 個槽位的散列表上搀庶，那鏈表法的時間復(fù)雜度為 $O(\frac{n}{m})$ 拐纱。鏈表法可以不用像開放尋址一樣關(guān)心裝載因子，但需要注意散列函數(shù)對散列值的計算哥倔，使鏈表結(jié)點能夠盡可能均勻地分布在散列表槽位上秸架，避免散列表退化為鏈表。有時黑客甚至?xí)闹圃鞌?shù)據(jù)咆蒿，利用散列函數(shù)制造散列沖突东抹，使數(shù)據(jù)集中某些槽位上，造成散列表性能的極度退化蜡秽。

面對這樣的惡意行為散列表只能坐以待斃嗎府阀？其實不然，當(dāng)槽位上的鏈表過長時芽突，可以將其改造成之前學(xué)習(xí)過的跳表等试浙，鏈表改造為跳表后查詢的時間復(fù)雜度也只是退化為 $O(\log{n})$ ，依然是可以接受的范圍寞蚌。

鏈表法在存儲利用上比開放尋址更加高效田巴，不用提前申請存儲空間钠糊，當(dāng)有新數(shù)據(jù)時申請一個新的結(jié)點就行。而且鏈表法對裝載因子也不那么敏感壹哺，裝載因子的增高也只是意味著槽位對應(yīng)的鏈表更長而已抄伍，鏈表增長也有將鏈表改造為跳表等結(jié)構(gòu)的應(yīng)對策略，所以鏈表法在裝載因子超過 1 的情況下都可保持高效管宵。

開放尋址 VS 鏈表法

開放尋址不存在像鏈表法一樣有鏈表過長而導(dǎo)致效率降低的煩惱截珍，不過裝載因子是開放尋址的晴雨表，裝載因子過高會造成散列沖突機率的上升箩朴，開放尋址就需要不斷探測空閑位置岗喉，算法的執(zhí)行成本會不斷被提高。而且在刪除操作時只能將數(shù)據(jù)先標(biāo)記為刪除炸庞，對于頻繁增刪的數(shù)據(jù)效率會受到影響钱床。

當(dāng)然也可以在這種風(fēng)險出現(xiàn)前進(jìn)行散列表的動態(tài)擴(kuò)容，不過這樣就會出現(xiàn)大量空閑的存儲空間埠居，導(dǎo)致存儲的利用效率過低查牌，這種現(xiàn)象在數(shù)據(jù)量越大的情況下越明顯。所以開放尋址比較適用于數(shù)據(jù)量較小的情況滥壕。

鏈表法對于散列沖突的處理更加靈活纸颜，同時對存儲空間的利用效率也更高，但鏈表結(jié)點除了存儲數(shù)據(jù)外還需要存儲指針捏浊，如果存儲數(shù)據(jù)較小指針占用的存儲甚至?xí)?dǎo)致整體存儲翻倍的情況懂衩，但存儲數(shù)據(jù)較大時指針占用的存儲也就可以忽略不計，所以鏈表法較適合存儲數(shù)據(jù)對象較大金踪，但頻繁的增刪操作不會對鏈表法造成明顯的影響。因為這樣的特點牵敷，鏈表法更加適合大數(shù)據(jù)量胡岔，或者數(shù)據(jù)對象較大的時候，如果數(shù)據(jù)操作頻繁枷餐，那鏈表法更是不二之選靶瘸。

總結(jié)

散列表由數(shù)組擴(kuò)展而來，使用散列函數(shù)將鍵計算為散列值毛肋，散列值對應(yīng)數(shù)據(jù)存儲的數(shù)組下標(biāo)怨咪。雖然散列表的執(zhí)行效率較高，但會有散列沖突的問題润匙，可以通過開放尋址法和鏈表法解決此問題诗眨。

開放尋址存儲利用效率較低，適用數(shù)據(jù)量較小并且增刪不頻繁的情況孕讳，如果數(shù)據(jù)量較大匠楚，增刪頻繁的情況更加適用鏈表法巍膘，相對之下鏈表法更加普適。

文章中如有問題歡迎留言指正
數(shù)據(jù)結(jié)構(gòu)與算法之美筆記系列將會做為我對王爭老師此專欄的學(xué)習(xí)筆記芋簿，如想了解更多王爭老師專欄的詳情請到極客時間自行搜索峡懈。