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

摘要:

「散列表」（Hash Table）或「Hash 表」是基于數(shù)組擴展的數(shù)據(jù)結構，能夠將復雜信息通過「Hash 算法」生成「Hash 值」，以對應數(shù)組下標，完成快速隨機訪問數(shù)據(jù)的功能。

"我"從哪里來

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

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

散列表的關鍵

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

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

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

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

如何解決散列沖突

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

開放尋址

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

三種探測方法

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

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

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

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

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

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

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

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

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

鏈表法

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

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

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

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

開放尋址 VS 鏈表法

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

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

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

總結

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

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

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

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

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