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

摘要:

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

"我"從哪里來

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

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

散列表的關(guān)鍵

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

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

因?yàn)樯⒘泻瘮?shù)生成的散列值對(duì)應(yīng)數(shù)組下標(biāo)，而數(shù)組下標(biāo)就是非負(fù)整數(shù)，所以需要滿足第一個(gè)原則；兩個(gè)相等的數(shù)據(jù)經(jīng)過散列算法得到的散列值肯定相等，否則利用散列值在散列表中查找數(shù)據(jù)就無從談起；至于第三個(gè)原則雖然在情理之中，卻不那么容易做到，即使是被廣泛運(yùn)用的散列算法也會(huì)出現(xiàn)散列值沖突的情況，導(dǎo)致無法滿足第三個(gè)原則。

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

如何解決散列沖突

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

開放尋址

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

三種探測方法

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

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

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

雙重探測是當(dāng)?shù)谝粋€(gè)散列函數(shù)沖突時(shí)使用第二個(gè)散列函數(shù)運(yùn)算散列值，利用這種方式探測。例如，當(dāng) hash_1(key) 沖突時(shí)，就使用 hash_2(key) 計(jì)算散列值，如果再?zèng)_突就使用 hash_3(key) 計(jì)算散列值，依此類推。

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

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

為了保持散列表一定比例的空閑空間，在裝載因子到達(dá)一定閾值時(shí)需要對(duì)散列表數(shù)據(jù)進(jìn)行搬移，但散列表搬移比較耗時(shí)。你可以試想下這樣的步驟，在申請(qǐng)一個(gè)新的更大的散列表空間后，需要將舊散列表的數(shù)據(jù)重新通過散列函數(shù)生成散列值，再存儲(chǔ)到新散列表中，想想都覺得麻煩。

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

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

鏈表法

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

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

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

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

開放尋址 VS 鏈表法

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

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

鏈表法對(duì)于散列沖突的處理更加靈活，同時(shí)對(duì)存儲(chǔ)空間的利用效率也更高，但鏈表結(jié)點(diǎn)除了存儲(chǔ)數(shù)據(jù)外還需要存儲(chǔ)指針，如果存儲(chǔ)數(shù)據(jù)較小指針占用的存儲(chǔ)甚至?xí)?dǎo)致整體存儲(chǔ)翻倍的情況，但存儲(chǔ)數(shù)據(jù)較大時(shí)指針占用的存儲(chǔ)也就可以忽略不計(jì)，所以鏈表法較適合存儲(chǔ)數(shù)據(jù)對(duì)象較大，但頻繁的增刪操作不會(huì)對(duì)鏈表法造成明顯的影響。因?yàn)檫@樣的特點(diǎn)，鏈表法更加適合大數(shù)據(jù)量，或者數(shù)據(jù)對(duì)象較大的時(shí)候，如果數(shù)據(jù)操作頻繁，那鏈表法更是不二之選。

總結(jié)

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

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

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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容