資料結構一(哈希表)想進大廠的必備知識點

資料結構對于程式設計人員是非常重要的,想要提高自己的程式設計水準,或者是技術職稱,都要好好的學習資料結構.那麼今天講的哈希表就是一種非常重要的資料結構,大多數學習程式設計的人員都搞不懂資料結構或者是其中的哈希表結構.

下面,就通過一個實作的小例子來講解說明哈希表背後的優勢和特點.便于了解.

一. 認識哈希表

我們還像其他資料結構一樣, 先來簡單的認識一下哈希表.

哈希表介紹

• 哈希表是一種非常重要的資料結構, 幾乎所有的程式設計語言都有直接或者間接的應用這種資料結構.
• 哈希表通常是基于數組進行實作的, 但是相對于數組, 它也很多的優勢:
  • 它可以提供非常快速的插入-删除-查找操作
  • 無論多少資料, 插入和删除值需要接近常量的時間: 即O(1)的時間級. 實際上, 隻需要幾個機器指令即可
  • 哈希表的速度比樹還要快, 基本可以瞬間查找到想要的元素
  • 哈希表相對于樹來說編碼要容易很多.
• 哈希表相對于數組的一些不足:
  • 哈希表中的資料是沒有順序的, 是以不能以一種固定的方式(比如從小到大)來周遊其中的元素.
  • 通常情況下, 哈希表中的key是不允許重複的, 不能放置相同的key, 用于儲存不同的元素.
• 那麼, 哈希表到底是什麼呢?
  • 似乎還是沒有說它到底是什麼.
  • 這也是哈希表不好了解的地方, 不像數組和連結清單, 甚至是樹一樣直接畫出你就知道它的結構, 甚至是原理了.
  • 它的結構就是數組, 但是它神奇的地方在于對下标值的一種變換, 這種變換我們可以稱之為哈希函數, 通過哈希函數可以擷取到HashCode.
  • 不着急, 我們慢慢來認識它到底是什麼.

體會哈希表

• 案例一: 公司使用一種資料結構來儲存所有員工
  • 案例介紹:
    • 假如一家公司有1000個員工, 現在我們需要将這些員工的資訊使用某種資料結構來儲存起來
    • 你會采用什麼資料結構呢?
  • 方案一: 數組
    • 一種方案是按照順序将所有的員工依次存入一個長度為1000的數組中. 每個員工的資訊都儲存在數組的某個位置上.
    • 但是我們要檢視某個具體員工的資訊怎麼辦呢? 一個個找嗎? 不太好找.
    • 數組最大的優勢是什麼? 通過下标值去擷取資訊.
    • 是以為了可以通過數組快速定位到某個員工, 最好給員工資訊中添加一個員工編号, 而編号對應的就是員工的下标值.
    • 當查找某個員工的資訊時, 通過員工編号可以快速定位到員工的資訊位置.
  • 方案二: 連結清單
    • 連結清單對應插入和删除資料有一定的優勢.
    • 但是對于擷取員工的資訊, 每次都必須從頭周遊到尾, 這種方式顯然不是特别适合我們這裡.
  • 最終方案:
    • 這樣看最終方案似乎就是數組了. 但是數組還是有缺點, 什麼缺點呢?
    • 假如我想檢視一下張三這位員工的資訊, 但是我不知道張三的員工編号, 你怎麼辦呢?
    • 當然, 你說我可以問他. 但是你每查找一個員工都是問一下這個員工的編号嗎? 不合适.
    • 能不能有一種辦法, 讓張三的名字和它的員工編号産生直接的關系呢?
    • 也就是通過張三這個名字, 我就能擷取到它的索引值, 而再通過索引值我就能擷取到張三的資訊呢?
    • 這樣的方案已經存在了, 就是使用哈希函數, 讓某個key的資訊和索引值對應起來.
• 案例二: 設計一個資料結構, 儲存聯系人和電話.
  • 方案一: 數組?
    • 使用數組來存儲聯系人和電話不是非常合适.
    • 因為如果需要查詢某個聯系人, 就需要從數組中一個個取出資料和查詢的聯系人比較. 效率非常的低.
  • 方案二: 連結清單?
    • 連結清單和數組一樣, 效率非常低.
  • 方案三: 有沒有一種方案, 可以将聯系人和數組的下标值對應呢?
    • 那麼我們就可以讓聯系人的名字作為下标值, 來擷取這個聯系人對應的電話.
    • 但是聯系人的名字(字元串)可以作為下标值嗎? 當然不可以.
    • 是以你需要一種方案将字元串轉成下标值.
• 案例三: 使用一種資料結構存儲單詞資訊, 比如有50000個單詞. 找到單詞後每個單詞有自己的翻譯&讀音&應用等等
  • • 這個案例更加明顯能感受到數組的缺陷.
    • 我拿到一個單詞Python, 我想知道這個單詞的翻譯/讀音/應用. 怎麼可以從數組中查到這個單詞的位置呢?
    • 線性查找? 50000次比較?
    • 如果你使用數組來實作這個功能, 效率會非常非常低, 而且你一定沒有學習過資料結構.
  • • 不需要考慮了吧?
  • 方案三: 有沒有一種方案, 可以将單詞轉成數組的下标值呢?
    • 如果單詞轉成數組的下标, 那麼以後我們要查找某個單詞的資訊, 直接按照下标值一步即可通路到想要的元素.
• 案例三: 進階語言的編譯器
  • 事實上哈希表還有另外一個非常重要的應用場景, 就是進階語言的編譯器.
  • 它通常用哈希表來保留符号表.
  • 符号表記錄了程式員聲明的所有變量和函數名, 以及它們在記憶體中的位址.
  • 程式需要快速的通路這些名字, 是以哈希表是理想的實作方式.

字母轉數字

• 但是, 怎樣才能将一個轉成數組的下标值呢?
  • 單詞轉下标值, 其實就是字母轉數字, 怎麼轉?
• 現在我們需要設計一種方案, 可以将單詞轉成适當的下标:
  • 其實計算機中有很多的編碼方案就是用數字代替單詞的字元.
  • 比如ASCII編碼: a是97, b是98, 依次類推122代表z
  • 我們也可以設計一個自己的編碼系統, 比如a是1, b是2, c是3, 依次類推, z是26. 當然我們可以加上空格用0代替, 就是27個字元(不考慮大寫問題)
  • 但是, 有了編碼系統後, 一個單詞如何轉成數字呢?
• 方案一: 數字相加
  • 一個轉換單詞的簡單方案就是把單詞每個字元的編碼求和.
  • 例如單詞cats轉成數字: 3+1+20+19=43, 那麼43就作為cats單詞的下标存在數組中.
  • 問題: 按照這種方案有一個很明顯的問題就是很多單詞最終的下标可能都是43.
    • 比如was/tin/give/tend/moan/tick等等.
    • 我們知道數組中一個下标值位置隻能存儲一個資料, 如果存入後來的資料, 必然會造成資料的覆寫.
    • 一個下标存儲這麼多單詞顯然是不合理的.
• 方案二: 幂的連乘
  • 現在, 我們想通過一種算法, 讓cats轉成數字後不那麼普通. 數字相加的方案就有些過于普通了.
  • 有一種方案就是使用幂的連乘, 什麼是幂的連乘呢?
  • 其實我們平時使用的大于10的數字, 可以用一種幂的連乘來表示它的唯一性:比如: 7654 = 7*10³+6*10²+5*10+4
  • 我們的單詞也可以使用這種方案來表示: 比如cats = 3*27³+1*27²+20*27+17= 60337
  • 這樣得到的數字可以幾乎保證它的唯一性, 不會和别的單詞重複.
  • 問題: 如果一個單詞是zzzzzzzzzz(一般英文單詞不會超過10個字元). 那麼得到的數字超過7000000000000. 數組可以表示這麼大的下标值嗎?
  • 而且就算能建立這麼大的數組, 事實上有很多是無效的單詞. 建立這麼大的數組是沒有意義的.
  img
• 兩種方案總結:
  • 第一種方案(把數字相加求和)産生的數組下标太少.
  • 第二種方案(與27的幂相乘求和)産生的數組下标又太多.

認識哈希化

• 現在需要一種壓縮方法, 把幂的連乘方案系統中得到的巨大整數範圍壓縮到可接受的數組範圍中.
• 對于英文詞典, 多大的數組才合适呢?
  • 如果隻有50000個單詞, 可能會定義一個長度為50000的數組.
  • 但是實際情況中, 往往需要更大的空間來存儲這些單詞. 因為我們不能儲存單詞會映射到每一個位置. (比如兩倍的大小: 100000).
• 如何壓縮呢?
  • 現在, 就找一種方法, 把0到超過7000000000000的範圍, 壓縮為從0到100000.
  • 有一種簡單的方法就是使用取餘操作符, 它的作用是得到一個數被另外一個數整除後的餘數..
• 取餘操作的實作:
  • 為了看到這個方法如何工作, 我們先來看一個小點的數字範圍壓縮到一個小點的空間中.
  • 假設把從0~199的數字, 比如使用largeNumber代表, 壓縮為從0到9的數字, 比如使用smallRange代表.
  • 下标值的結果: index = largeNumber % smallRange;
  • 當一個數被10整除時, 餘數一定在0~9之間;
  • 比如13%10=3, 157%10=7.
  • 當然, 這中間還是會有重複, 不過重複的數量明顯變小了. 因為我們的數組是100000, 而隻有50000個單詞.
  • 就好比, 你在0~199中間選取5個數字, 放在這個長度為10的數組中, 也會重複, 但是重複的機率非常小. (後面我們會講到真的發生重複了應該怎麼解決)
• 認識情況了上面的内容, 相信你應該懂了哈希标的原理了, 我們來看看幾個概念:
  • 哈希化: 将大數字轉化成數組範圍内下标的過程, 我們就稱之為哈希化.
  • 哈希函數: 通常我們會将單詞轉成大數字, 大數字在進行哈希化的代碼實作放在一個函數中, 這個函數我們成為哈希函數.
  • 哈希表: 最終将資料插入到的這個數組, 我們就稱之為是一個哈希表

二. 位址的沖突

盡管50000個單詞, 我們使用了100000個位置來存儲, 并且通過一種相對比較好的哈希函數來完成.

但是依然有可能會發生沖突, 比如melioration這個單詞, 通過哈希函數得到它數組的下标值後, 發現那個位置上已經存在一個單詞demystify, 因為它經過哈希化後和melioration得到的下标實作相同的.

這種情況我們成為沖突.

什麼是沖突?

• 前面前言部分我們已經簡單說明了, 什麼是沖突. 雖然我們不希望這種情況發生, 當然更希望每個下标對應一個資料項, 但是通常這是不可能的.
• 就像之前0~199的數字選取5個放在長度為10的單元格中
  • 如果我們随機選出來的是33, 82, 11, 45, 90, 那麼最終它們的位置會是3-2-1-5-0, 沒有發生沖突.
  • 但是如果其中有一個33, 還有一個73呢? 還是發生了沖突.
• 我們需要針對這種沖突提出一些解決方案, 即使沖突的可能性比較小, 你依然需要考慮到這種情況, 以便發生的時候進行對應的處理代碼.
• 如何解決這種沖突呢? 常見的情況有兩種方案.
  • 鍊位址法.
  • 開放位址法.

鍊位址法

• 鍊位址法是一種比較常見的解決沖突的方案.(也稱為拉鍊法)
  • 其實, 如果你了解了為什麼産生沖突, 看到圖後就可以立馬了解鍊位址法是什麼含義了.
• 鍊位址法圖檔
• 圖檔解析:
  • 從圖檔中我們可以看出, 鍊位址法解決沖突的辦法是每個數組單元中存儲的不再是單個資料, 而是一個鍊條.
  • 這個鍊條使用什麼資料結構呢? 常見的是數組或者連結清單.
  • 比如是連結清單, 也就是每個數組單元中存儲着一個連結清單. 一旦發現重複, 将重複的元素插入到連結清單的首端或者末端即可.
  • 當查詢時, 先根據哈希化後的下标值找到對應的位置, 再取對外連結表, 依次查詢找尋找的資料.
• 數組還是連結清單呢?
  • 數組或者連結清單在這裡其實都可以, 效率上也差不多.
  • 因為根據哈希化的index找出這個數組或者連結清單時, 通常就會使用線性查找, 這個時候數組和連結清單的效率是差不多的.
  • 當然在某些實作中, 會将新插入的資料放在數組或者連結清單的最前面, 因為覺得心插入的資料用于取出的可能性更大.
  • 這種情況最好采用連結清單, 因為數組在首位插入資料是需要所有其他項後移的, 連結清單就沒有這樣的問題.
  • 當然, 我覺得出于這個也看業務需求, 不見得新的資料就通路次數會更多: 比如我們微信新添加的好友, 可能是剛認識的, 聯系的頻率不見得比我們的老朋友更多, 甚至新加的隻是聊一兩句.
  • 是以, 這裡個人覺得選擇資料或者連結清單都是可以的.

開放位址法

• 開放位址法的主要工作方式是尋找空白的單元格來添加重複的資料.
• 我們還是通過圖檔來了解開放位址法的工作方式.
• • 從圖檔的文字中我們可以了解到, 開放位址法其實就是要尋找空白的位置來放置沖突的資料項.
  • 但是探索這個位置的方式不同, 有三種方法:
    • 線性探測
    • 二次探測
    • 再哈希法

• 線性探測非常好了解: 線性的查找空白的單元.
• 插入的32:
  • 經過哈希化得到的index=2, 但是在插入的時候, 發現該位置已經有了82. 怎麼辦呢?
  • 線性探測就是從index位置+1開始一點點查找合适的位置來放置32, 什麼是合适的位置呢?
  • 空的位置就是合适的位置, 在我們上面的例子中就是index=3的位置, 這個時候32就會放在該位置.
• 查詢32呢?
  • 查詢32和插入32比較相似.
  • 首先經過哈希化得到index=2, 比如2的位置結果和查詢的數值是否相同, 相同那麼就直接傳回.
  • 不相同呢? 線性查找, 從index位置+1開始查找和32一樣的.
  • 這裡有一個特别需要注意的地方: 如果32的位置我們之前沒有插入, 是否将整個哈希表查詢一遍來确定32存不存在嗎?
  • 當然不是, 查詢過程有一個約定, 就是查詢到空位置, 就停止. (因為查詢到這裡有空位置, 32之前不可能跳過空位置去其他的位置.)
• 删除32呢?
  • 删除操作和插入查詢比較類似, 但是也有一個特别注意點.
  • 注意: 删除操作一個資料項時, 不可以将這個位置下标的内容設定為null, 為什麼呢?
  • 因為将它設定為null可能會影響我們之後查詢其他操作, 是以通常删除一個位置的資料項時, 我們可以将它進行特殊處理(比如設定為-1).
  • 當我們之後看到-1位置的資料項時, 就知道查詢時要繼續查詢, 但是插入時這個位置可以放置資料.
• 線性探測的問題:
  • 線性探測有一個比較嚴重的問題, 就是聚集. 什麼是聚集呢?
  • 比如我在沒有任何資料的時候, 插入的是22-23-24-25-26, 那麼意味着下标值:2-3-4-5-6的位置都有元素. 這種一連串填充單元就叫做聚集.
  • 聚集會影響哈希表的性能, 無論是插入/查詢/删除都會影響.
  • 比如我們插入一個32, 會發現連續的單元都不允許我們放置資料, 并且在這個過程中我們需要探索多次.
  • 二次探測可以解決一部分這個問題, 我們一起來看一看.

• 我們剛才談到, 線性探測存在的問題: 就是如果之前的資料時連續插入的, 那麼新插入的一個資料可能需要探測很長的距離.
• 二次探測線上性探測的基礎上進行了優化:
  • 二次探測主要優化的是探測時的步長, 什麼意思呢?
  • 線性探測, 我們可以看成是步長為1的探測, 比如從下标值x開始, 那麼線性測試就是x+1, x+2, x+3依次探測.
  • 二次探測, 對步長做了優化, 比如從下标值x開始, x+1², x+2², x+3².
  • 這樣就可以一次性探測比較常的距離, 比避免那些聚集帶來的影響.
• 二次探測的問題:
  • 但是二次探測依然存在問題, 比如我們連續插入的是32-112-82-2-192, 那麼它們依次累加的時候步長的相同的.
  • 也就是這種情況下會造成步長不一的一種聚集. 還是會影響效率.
  • 怎麼根本解決這個問題呢? 讓每個人的步長不一樣, 一起來看看再哈希法吧.

• 為了消除線性探測和二次探測中無論步長+1還是步長+平法中存在的問題, 還有一種最常用的解決方案: 再哈希法.
• 再哈希法:
  • 二次探測的算法産生的探測序列步長是固定的: 1, 4, 9, 16, 依次類推.
  • 現在需要一種方法: 産生一種依賴關鍵字的探測序列, 而不是每個關鍵字都一樣.
  • 那麼, 不同的關鍵字即使映射到相同的數組下标, 也可以使用不同的探測序列.
  • 再哈希法的做法就是: 把關鍵字用另外一個哈希函數, 再做一次哈希化, 用這次哈希化的結果作為步長.
  • 對于指定的關鍵字, 步長在整個探測中是不變的, 不過不同的關鍵字使用不同的步長.
• 第二次哈希化需要具備如下特點:
  • 和第一個哈希函數不同. (不要再使用上一次的哈希函數了, 不然結果還是原來的位置)
  • 不能輸出為0(否則, 将沒有步長. 每次探測都是原地踏步, 算法就進入了死循環)
• 其實, 我們不用費腦細胞來設計了, 計算機專家已經設計出一種工作很好的哈希函數:
  • stepSize = constant - (key - constant)
  • 其中constant是質數, 且小于數組的容量.
  • 例如: stepSize = 5 - (key % 5), 滿足需求, 并且結果不可能為0.

三. 哈希化的效率

哈希表中執行插入和搜尋操作可以達到O(1)的時間級，如果沒有發生沖突，隻需要使用一次哈希函數和數組的引用，就可以插入一個新資料項或找到一個已經存在的資料項。

如果發生沖突，存取時間就依賴後來的探測長度。一個單獨的查找或插入時間與探測的長度成正比，這裡還要加上哈希函數的常量時間。

平均探測長度以及平均存取時間，取決于填裝因子，随着填裝因子變大，探測長度也越來越長。

随着填裝因子變大，效率下降的情況，在不同開放位址法方案中比鍊位址法更嚴重, 是以我們來對比一下他們的效率, 再決定我們選取的方案.

裝填因子

• 在分析效率之前, 我們先了解一個概念: 裝填因子.
• 裝填因子表示目前哈希表中已經包含的資料項和整個哈希表長度的比值.
  • 裝填因子 = 總資料項 / 哈希表長度.
• 開放位址法的裝填因子最大是多少呢? 1, 因為它必須尋找到空白的單元才能将元素放入.
• 鍊位址法的裝填因子呢? 可以大于1, 因為拉鍊法可以無限的延伸下去, 隻要你願意. (當然後面效率就變低了)

• 我們來一個個認識一下開放位址法中每種方案的效率.

• 下面的等式顯示了線性探測時，探測序列(P)和填裝因子(L)的關系
  • 對成功的查找: P = (1+1/(1-L))/2
  • 對不成功的查找: P=(1+1/(1-L)^2)/2
• 公式來自于Knuth(算法分析領域的專家, 現代計算機的先驅人物), 這些公式的推導自己去看了一下, 确實有些繁瑣, 這裡不再給出推導過程, 僅僅說明它的效率.
• 圖解算法的效率:
• • 當填裝因子是1/2時，成功的搜尋需要1.5次比較，不成功的搜尋需要2.5次
  • 當填裝因子為2/3時，分别需要2.0次和5.0次比較
  • 如果填裝因子更大，比較次數會非常大。
  • 應該使填裝因子保持在2/3以下，最好在1/2以下，另一方面，填裝因子越低，對于給定數量的資料項，就需要越多的空間。
  • 實際情況中，最好的填裝因子取決于存儲效率和速度之間的平衡，随着填裝因子變小，存儲效率下降，而速度上升。

二次探測和再哈希

• 二次探測和再哈希法的性能相當。它們的性能比線性探測略好。
  • 對成功的搜尋，公式是: -log2(1 - loadFactor) / loadFactor
  • 對于不成功的搜搜, 公式是: 1 / (1-loadFactor)
• 對應的圖:
• • 當填裝因子是0.5時，成功和不成的查找平均需要2次比較
  • 當填裝因子為2/3時，分别需要2.37和3.0次比較
  • 當填裝因子為0.8時，分别需要2.9和5.0次
  • 是以對于較高的填裝因子，對比線性探測，二次探測和再哈希法還是可以忍受的。

• 鍊位址法的效率分析有些不同, 一般來說比開放位址法簡單. 我們來分析一下這個公式應該是怎麼樣的.
  • 假如哈希表包含arraySize個資料項, 每個資料項有一個連結清單, 在表中一共包含N個資料項.
  • 那麼, 平均起來每個連結清單有多少個資料項呢? 非常簡單, N / arraySize.
  • 有沒有發現這個公式有點眼熟? 其實就是裝填因子.
• OK, 那麼我們現在就可以求出查找成功和不成功的次數了
  • 成功可能隻需要查找連結清單的一半即可: 1 + loadFactor/2
  • 不成功呢? 可能需要将整個連結清單查詢完才知道不成功: 1 + loadFactor.
• 對應的圖

效率的結論

• 經過上面的比較我們可以發現, 鍊位址法相對來說效率是好于開放位址法的.
• 是以在真實開發中, 使用鍊位址法的情況較多, 因為它不會因為添加了某元素後性能急劇下降.
  • 比如在Java的HashMap中使用的就是鍊位址法.
• 代碼實作:
  • 到目前為止, 我們講了很久的哈希表原理, 依然沒有寫任何代碼.
  • 因為我覺得了解了原理, 再去寫代碼相對思路會清晰一些.
  • 後面, 我會使用鍊位址法來實作我們的哈希表(你也可以試着使用開放位址法來實作, 原理已經非常清晰了)
  • 但是, 我們還有N多的細節, 可以深入探讨.
  • 欲知後事如何, 且聽下回分解!!!
  • 感謝小夥伴的閱讀,後面還會繼續更新,與大家分享.歡迎大家加入哦 1023554403 群,可以免費領取學習資料,不斷更新資料,一起學習,進步.