如需轉(zhuǎn)載, 請咨詢作者, 并且注明出處.
有任何問題, 可以關(guān)注我的微博: coderwhy, 或者添加我的微信: 372623326

哈希表是一種非常重要的數(shù)據(jù)結(jié)構(gòu), 很多學(xué)習(xí)編程的人一直搞不懂哈希表到底是如何實現(xiàn)的.

在這一章節(jié)中, 我們就一點點來實現(xiàn)一個自己的哈希表. 通過實現(xiàn)來理解哈希表背后的原理和它的優(yōu)勢.

一. 認(rèn)識哈希表

我們還像其他數(shù)據(jù)結(jié)構(gòu)一樣, 先來簡單的認(rèn)識一下哈希表.

哈希表介紹

• 哈希表是一種非常重要的數(shù)據(jù)結(jié)構(gòu), 幾乎所有的編程語言都有直接或者間接的應(yīng)用這種數(shù)據(jù)結(jié)構(gòu).
• 哈希表通常是基于數(shù)組進(jìn)行實現(xiàn)的, 但是相對于數(shù)組, 它也很多的優(yōu)勢:
  • 它可以提供非承萃妫快速的插入-刪除-查找操作
  • 無論多少數(shù)據(jù), 插入和刪除值需要接近常量的時間: 即O(1)的時間級. 實際上, 只需要幾個機(jī)器指令即可
  • 哈希表的速度比樹還要快, 基本可以瞬間查找到想要的元素
  • 哈希表相對于樹來說編碼要容易很多.
• 哈希表相對于數(shù)組的一些不足:
  • 哈希表中的數(shù)據(jù)是沒有順序的, 所以不能以一種固定的方式(比如從小到大)來遍歷其中的元素.
  • 通常情況下, 哈希表中的key是不允許重復(fù)的, 不能放置相同的key, 用于保存不同的元素.
• 那么, 哈希表到底是什么呢?
  • 似乎還是沒有說它到底是什么.
  • 這也是哈希表不好理解的地方, 不像數(shù)組和鏈表, 甚至是樹一樣直接畫出你就知道它的結(jié)構(gòu), 甚至是原理了.
  • 它的結(jié)構(gòu)就是數(shù)組, 但是它神奇的地方在于對下標(biāo)值的一種變換, 這種變換我們可以稱之為哈希函數(shù), 通過哈希函數(shù)可以獲取到HashCode.
  • 不著急, 我們慢慢來認(rèn)識它到底是什么.

體會哈希表

• 案例一: 公司使用一種數(shù)據(jù)結(jié)構(gòu)來保存所有員工
  • 案例介紹:
    • 假如一家公司有1000個員工, 現(xiàn)在我們需要將這些員工的信息使用某種數(shù)據(jù)結(jié)構(gòu)來保存起來
    • 你會采用什么數(shù)據(jù)結(jié)構(gòu)呢?
  • 方案一: 數(shù)組
    • 一種方案是按照順序?qū)⑺械膯T工依次存入一個長度為1000的數(shù)組中. 每個員工的信息都保存在數(shù)組的某個位置上.
    • 但是我們要查看某個具體員工的信息怎么辦呢? 一個個找嗎? 不太好找.
    • 數(shù)組最大的優(yōu)勢是什么? 通過下標(biāo)值去獲取信息.
    • 所以為了可以通過數(shù)組快速定位到某個員工, 最好給員工信息中添加一個員工編號, 而編號對應(yīng)的就是員工的下標(biāo)值.
    • 當(dāng)查找某個員工的信息時, 通過員工編號可以快速定位到員工的信息位置.
  • 方案二: 鏈表
    • 鏈表對應(yīng)插入和刪除數(shù)據(jù)有一定的優(yōu)勢.
    • 但是對于獲取員工的信息, 每次都必須從頭遍歷到尾, 這種方式顯然不是特別適合我們這里.
  • 最終方案:
    • 這樣看最終方案似乎就是數(shù)組了. 但是數(shù)組還是有缺點, 什么缺點呢?
    • 假如我想查看一下張三這位員工的信息, 但是我不知道張三的員工編號, 你怎么辦呢?
    • 當(dāng)然, 你說我可以問他. 但是你每查找一個員工都是問一下這個員工的編號嗎? 不合適.
    • 能不能有一種辦法, 讓張三的名字和它的員工編號產(chǎn)生直接的關(guān)系呢?
    • 也就是通過張三這個名字, 我就能獲取到它的索引值, 而再通過索引值我就能獲取到張三的信息呢?
    • 這樣的方案已經(jīng)存在了, 就是使用哈希函數(shù), 讓某個key的信息和索引值對應(yīng)起來.
• 案例二: 設(shè)計一個數(shù)據(jù)結(jié)構(gòu), 保存聯(lián)系人和電話.
  • 方案一: 數(shù)組?
    • 使用數(shù)組來存儲聯(lián)系人和電話不是非常合適.
    • 因為如果需要查詢某個聯(lián)系人, 就需要從數(shù)組中一個個取出數(shù)據(jù)和查詢的聯(lián)系人比較. 效率非常的低.
  • 方案二: 鏈表?
    • 鏈表和數(shù)組一樣, 效率非常低.
  • 方案三: 有沒有一種方案, 可以將聯(lián)系人和數(shù)組的下標(biāo)值對應(yīng)呢?
    • 那么我們就可以讓聯(lián)系人的名字作為下標(biāo)值, 來獲取這個聯(lián)系人對應(yīng)的電話.
    • 但是聯(lián)系人的名字(字符串)可以作為下標(biāo)值嗎? 當(dāng)然不可以.
    • 所以你需要一種方案將字符串轉(zhuǎn)成下標(biāo)值.
• 案例三: 使用一種數(shù)據(jù)結(jié)構(gòu)存儲單詞信息, 比如有50000個單詞. 找到單詞后每個單詞有自己的翻譯&讀音&應(yīng)用等等
  • 方案一: 數(shù)組?
    • 這個案例更加明顯能感受到數(shù)組的缺陷.
    • 我拿到一個單詞Python, 我想知道這個單詞的翻譯/讀音/應(yīng)用. 怎么可以從數(shù)組中查到這個單詞的位置呢?
    • 線性查找? 50000次比較?
    • 如果你使用數(shù)組來實現(xiàn)這個功能, 效率會非常非常低, 而且你一定沒有學(xué)習(xí)過數(shù)據(jù)結(jié)構(gòu).
  • 方案二: 鏈表?
    • 不需要考慮了吧?
  • 方案三: 有沒有一種方案, 可以將單詞轉(zhuǎn)成數(shù)組的下標(biāo)值呢?
    • 如果單詞轉(zhuǎn)成數(shù)組的下標(biāo), 那么以后我們要查找某個單詞的信息, 直接按照下標(biāo)值一步即可訪問到想要的元素.
• 案例三: 高級語言的編譯器
  • 事實上哈希表還有另外一個非常重要的應(yīng)用場景, 就是高級語言的編譯器.
  • 它通常用哈希表來保留符號表.
  • 符號表記錄了程序員聲明的所有變量和函數(shù)名, 以及它們在內(nèi)存中的地址.
  • 程序需要快速的訪問這些名字, 所以哈希表是理想的實現(xiàn)方式.

字母轉(zhuǎn)數(shù)字

• 但是, 怎樣才能將一個轉(zhuǎn)成數(shù)組的下標(biāo)值呢?

  • 單詞轉(zhuǎn)下標(biāo)值, 其實就是字母轉(zhuǎn)數(shù)字, 怎么轉(zhuǎn)?

• 現(xiàn)在我們需要設(shè)計一種方案, 可以將單詞轉(zhuǎn)成適當(dāng)?shù)南聵?biāo):

  • 其實計算機(jī)中有很多的編碼方案就是用數(shù)字代替單詞的字符.
  • 比如ASCII編碼: a是97, b是98, 依次類推122代表z
  • 我們也可以設(shè)計一個自己的編碼系統(tǒng), 比如a是1, b是2, c是3, 依次類推, z是26. 當(dāng)然我們可以加上空格用0代替, 就是27個字符(不考慮大寫問題)
  • 但是, 有了編碼系統(tǒng)后, 一個單詞如何轉(zhuǎn)成數(shù)字呢?

• 方案一: 數(shù)字相加

  • 一個轉(zhuǎn)換單詞的簡單方案就是把單詞每個字符的編碼求和.
  • 例如單詞cats轉(zhuǎn)成數(shù)字: 3+1+20+19=43, 那么43就作為cats單詞的下標(biāo)存在數(shù)組中.
  • 問題: 按照這種方案有一個很明顯的問題就是很多單詞最終的下標(biāo)可能都是43.
    • 比如was/tin/give/tend/moan/tick等等.
    • 我們知道數(shù)組中一個下標(biāo)值位置只能存儲一個數(shù)據(jù), 如果存入后來的數(shù)據(jù), 必然會造成數(shù)據(jù)的覆蓋.
    • 一個下標(biāo)存儲這么多單詞顯然是不合理的.

• 方案二: 冪的連乘

  • 現(xiàn)在, 我們想通過一種算法, 讓cats轉(zhuǎn)成數(shù)字后不那么普通. 數(shù)字相加的方案就有些過于普通了.
  • 有一種方案就是使用冪的連乘, 什么是冪的連乘呢?
  • 其實我們平時使用的大于10的數(shù)字, 可以用一種冪的連乘來表示它的唯一性:比如: 7654 = 7*103+6*102+5*10+4
  • 我們的單詞也可以使用這種方案來表示: 比如cats = 3*273+1*272+20*27+17= 60337
  • 這樣得到的數(shù)字可以幾乎保證它的唯一性, 不會和別的單詞重復(fù).
  • 問題: 如果一個單詞是zzzzzzzzzz(一般英文單詞不會超過10個字符). 那么得到的數(shù)字超過7000000000000. 數(shù)組可以表示這么大的下標(biāo)值嗎?
  • 而且就算能創(chuàng)建這么大的數(shù)組, 事實上有很多是無效的單詞. 創(chuàng)建這么大的數(shù)組是沒有意義的.
  img

• 兩種方案總結(jié):

  • 第一種方案(把數(shù)字相加求和)產(chǎn)生的數(shù)組下標(biāo)太少.
  • 第二種方案(與27的冪相乘求和)產(chǎn)生的數(shù)組下標(biāo)又太多.

認(rèn)識哈铣鹑茫化

• 現(xiàn)在需要一種壓縮方法, 把冪的連乘方案系統(tǒng)中得到的巨大整數(shù)范圍壓縮到可接受的數(shù)組范圍中.
• 對于英文詞典, 多大的數(shù)組才合適呢?
  • 如果只有50000個單詞, 可能會定義一個長度為50000的數(shù)組.
  • 但是實際情況中, 往往需要更大的空間來存儲這些單詞. 因為我們不能保存單詞會映射到每一個位置. (比如兩倍的大小: 100000).
• 如何壓縮呢?
  • 現(xiàn)在, 就找一種方法, 把0到超過7000000000000的范圍, 壓縮為從0到100000.
  • 有一種簡單的方法就是使用取余操作符, 它的作用是得到一個數(shù)被另外一個數(shù)整除后的余數(shù)..
• 取余操作的實現(xiàn):
  • 為了看到這個方法如何工作, 我們先來看一個小點的數(shù)字范圍壓縮到一個小點的空間中.
  • 假設(shè)把從0~199的數(shù)字, 比如使用largeNumber代表, 壓縮為從0到9的數(shù)字, 比如使用smallRange代表.
  • 下標(biāo)值的結(jié)果: index = largeNumber % smallRange;
  • 當(dāng)一個數(shù)被10整除時, 余數(shù)一定在0~9之間;
  • 比如13%10=3, 157%10=7.
  • 當(dāng)然, 這中間還是會有重復(fù), 不過重復(fù)的數(shù)量明顯變小了. 因為我們的數(shù)組是100000, 而只有50000個單詞.
  • 就好比, 你在0~199中間選取5個數(shù)字, 放在這個長度為10的數(shù)組中, 也會重復(fù), 但是重復(fù)的概率非常小. (后面我們會講到真的發(fā)生重復(fù)了應(yīng)該怎么解決)
• 認(rèn)識情況了上面的內(nèi)容, 相信你應(yīng)該懂了哈希標(biāo)的原理了, 我們來看看幾個概念:
  • 哈细盟荩化: 將大數(shù)字轉(zhuǎn)化成數(shù)組范圍內(nèi)下標(biāo)的過程, 我們就稱之為哈希化.
  • 哈希函數(shù): 通常我們會將單詞轉(zhuǎn)成大數(shù)字, 大數(shù)字在進(jìn)行哈希化的代碼實現(xiàn)放在一個函數(shù)中, 這個函數(shù)我們成為哈希函數(shù).
  • 哈希表: 最終將數(shù)據(jù)插入到的這個數(shù)組, 我們就稱之為是一個哈希表

二. 地址的沖突

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

但是依然有可能會發(fā)生沖突, 比如melioration這個單詞, 通過哈希函數(shù)得到它數(shù)組的下標(biāo)值后, 發(fā)現(xiàn)那個位置上已經(jīng)存在一個單詞demystify, 因為它經(jīng)過哈弦路停化后和melioration得到的下標(biāo)實現(xiàn)相同的.

這種情況我們成為沖突.

什么是沖突?

• 前面前言部分我們已經(jīng)簡單說明了, 什么是沖突. 雖然我們不希望這種情況發(fā)生, 當(dāng)然更希望每個下標(biāo)對應(yīng)一個數(shù)據(jù)項, 但是通常這是不可能的.

  img

• 就像之前0~199的數(shù)字選取5個放在長度為10的單元格中

  • 如果我們隨機(jī)選出來的是33, 82, 11, 45, 90, 那么最終它們的位置會是3-2-1-5-0, 沒有發(fā)生沖突.
  • 但是如果其中有一個33, 還有一個73呢? 還是發(fā)生了沖突.

• 我們需要針對這種沖突提出一些解決方案, 即使沖突的可能性比較小, 你依然需要考慮到這種情況, 以便發(fā)生的時候進(jìn)行對應(yīng)的處理代碼.

• 如何解決這種沖突呢? 常見的情況有兩種方案.

  • 鏈地址法.
  • 開放地址法.

鏈地址法

• 鏈地址法是一種比較常見的解決沖突的方案.(也稱為拉鏈法)

  • 其實, 如果你理解了為什么產(chǎn)生沖突, 看到圖后就可以立馬理解鏈地址法是什么含義了.

• 鏈地址法圖片

  img

• 圖片解析:

  • 從圖片中我們可以看出, 鏈地址法解決沖突的辦法是每個數(shù)組單元中存儲的不再是單個數(shù)據(jù), 而是一個鏈條.
  • 這個鏈條使用什么數(shù)據(jù)結(jié)構(gòu)呢? 常見的是數(shù)組或者鏈表.
  • 比如是鏈表, 也就是每個數(shù)組單元中存儲著一個鏈表. 一旦發(fā)現(xiàn)重復(fù), 將重復(fù)的元素插入到鏈表的首端或者末端即可.
  • 當(dāng)查詢時, 先根據(jù)哈希化后的下標(biāo)值找到對應(yīng)的位置, 再取出鏈表, 依次查詢找尋找的數(shù)據(jù).

• 數(shù)組還是鏈表呢?

  • 數(shù)組或者鏈表在這里其實都可以, 效率上也差不多.
  • 因為根據(jù)哈希化的index找出這個數(shù)組或者鏈表時, 通常就會使用線性查找, 這個時候數(shù)組和鏈表的效率是差不多的.
  • 當(dāng)然在某些實現(xiàn)中, 會將新插入的數(shù)據(jù)放在數(shù)組或者鏈表的最前面, 因為覺得心插入的數(shù)據(jù)用于取出的可能性更大.
  • 這種情況最好采用鏈表, 因為數(shù)組在首位插入數(shù)據(jù)是需要所有其他項后移的, 鏈表就沒有這樣的問題.
  • 當(dāng)然, 我覺得出于這個也看業(yè)務(wù)需求, 不見得新的數(shù)據(jù)就訪問次數(shù)會更多: 比如我們微信新添加的好友, 可能是剛認(rèn)識的, 聯(lián)系的頻率不見得比我們的老朋友更多, 甚至新加的只是聊一兩句.
  • 所以, 這里個人覺得選擇數(shù)據(jù)或者鏈表都是可以的.

開放地址法

• 開放地址法的主要工作方式是尋找空白的單元格來添加重復(fù)的數(shù)據(jù).

• 我們還是通過圖片來了解開放地址法的工作方式.

  img

• 圖片解析:

  • 從圖片的文字中我們可以了解到, 開放地址法其實就是要尋找空白的位置來放置沖突的數(shù)據(jù)項.
  • 但是探索這個位置的方式不同, 有三種方法:
    • 線性探測
    • 二次探測
    • 再哈希法

線性探測

• 線性探測非常好理解: 線性的查找空白的單元.
• 插入的32:
  • 經(jīng)過哈辖模化得到的index=2, 但是在插入的時候, 發(fā)現(xiàn)該位置已經(jīng)有了82. 怎么辦呢?
  • 線性探測就是從index位置+1開始一點點查找合適的位置來放置32, 什么是合適的位置呢?
  • 空的位置就是合適的位置, 在我們上面的例子中就是index=3的位置, 這個時候32就會放在該位置.
• 查詢32呢?
  • 查詢32和插入32比較相似.
  • 首先經(jīng)過哈希化得到index=2, 比如2的位置結(jié)果和查詢的數(shù)值是否相同, 相同那么就直接返回.
  • 不相同呢? 線性查找, 從index位置+1開始查找和32一樣的.
  • 這里有一個特別需要注意的地方: 如果32的位置我們之前沒有插入, 是否將整個哈希表查詢一遍來確定32存不存在嗎?
  • 當(dāng)然不是, 查詢過程有一個約定, 就是查詢到空位置, 就停止. (因為查詢到這里有空位置, 32之前不可能跳過空位置去其他的位置.)
• 刪除32呢?
  • 刪除操作和插入查詢比較類似, 但是也有一個特別注意點.
  • 注意: 刪除操作一個數(shù)據(jù)項時, 不可以將這個位置下標(biāo)的內(nèi)容設(shè)置為null, 為什么呢?
  • 因為將它設(shè)置為null可能會影響我們之后查詢其他操作, 所以通常刪除一個位置的數(shù)據(jù)項時, 我們可以將它進(jìn)行特殊處理(比如設(shè)置為-1).
  • 當(dāng)我們之后看到-1位置的數(shù)據(jù)項時, 就知道查詢時要繼續(xù)查詢, 但是插入時這個位置可以放置數(shù)據(jù).
• 線性探測的問題:
  • 線性探測有一個比較嚴(yán)重的問題, 就是聚集. 什么是聚集呢?
  • 比如我在沒有任何數(shù)據(jù)的時候, 插入的是22-23-24-25-26, 那么意味著下標(biāo)值:2-3-4-5-6的位置都有元素. 這種一連串填充單元就叫做聚集.
  • 聚集會影響哈希表的性能, 無論是插入/查詢/刪除都會影響.
  • 比如我們插入一個32, 會發(fā)現(xiàn)連續(xù)的單元都不允許我們放置數(shù)據(jù), 并且在這個過程中我們需要探索多次.
  • 二次探測可以解決一部分這個問題, 我們一起來看一看.

二次探測

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

再哈希法

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

三. 哈馅怂化的效率

哈希表中執(zhí)行插入和搜索操作可以達(dá)到O(1)的時間級热康，如果沒有發(fā)生沖突，只需要使用一次哈希函數(shù)和數(shù)組的引用劣领，就可以插入一個新數(shù)據(jù)項或找到一個已經(jīng)存在的數(shù)據(jù)項姐军。

如果發(fā)生沖突，存取時間就依賴后來的探測長度尖淘。一個單獨的查找或插入時間與探測的長度成正比奕锌，這里還要加上哈希函數(shù)的常量時間。

平均探測長度以及平均存取時間村生，取決于填裝因子歇攻，隨著填裝因子變大，探測長度也越來越長梆造。

隨著填裝因子變大缴守，效率下降的情況，在不同開放地址法方案中比鏈地址法更嚴(yán)重, 所以我們來對比一下他們的效率, 再決定我們選取的方案.

裝填因子

• 在分析效率之前, 我們先了解一個概念: 裝填因子.
• 裝填因子表示當(dāng)前哈希表中已經(jīng)包含的數(shù)據(jù)項和整個哈希表長度的比值.
  • 裝填因子 = 總數(shù)據(jù)項 / 哈希表長度.
• 開放地址法的裝填因子最大是多少呢? 1, 因為它必須尋找到空白的單元才能將元素放入.
• 鏈地址法的裝填因子呢? 可以大于1, 因為拉鏈法可以無限的延伸下去, 只要你愿意. (當(dāng)然后面效率就變低了)

開放地址法

• 我們來一個個認(rèn)識一下開放地址法中每種方案的效率.

線性探測

• 下面的等式顯示了線性探測時镇辉，探測序列(P)和填裝因子(L)的關(guān)系

  • 對成功的查找: P = (1+1/(1-L))/2
  • 對不成功的查找: P=(1+1/(1-L)^2)/2

• 公式來自于Knuth(算法分析領(lǐng)域的專家, 現(xiàn)代計算機(jī)的先驅(qū)人物), 這些公式的推導(dǎo)自己去看了一下, 確實有些繁瑣, 這里不再給出推導(dǎo)過程, 僅僅說明它的效率.

• 圖解算法的效率:

  img

• 圖片解析:

  • 當(dāng)填裝因子是1/2時屡穗，成功的搜索需要1.5次比較，不成功的搜索需要2.5次
  • 當(dāng)填裝因子為2/3時忽肛，分別需要2.0次和5.0次比較
  • 如果填裝因子更大村砂，比較次數(shù)會非常大。
  • 應(yīng)該使填裝因子保持在2/3以下屹逛，最好在1/2以下础废，另一方面汛骂，填裝因子越低，對于給定數(shù)量的數(shù)據(jù)項评腺，就需要越多的空間帘瞭。
  • 實際情況中，最好的填裝因子取決于存儲效率和速度之間的平衡蒿讥，隨著填裝因子變小蝶念，存儲效率下降，而速度上升芋绸。

二次探測和再哈希

• 二次探測和再哈希法的性能相當(dāng)媒殉。它們的性能比線性探測略好。

  • 對成功的搜索摔敛，公式是: -log2(1 - loadFactor) / loadFactor
  • 對于不成功的搜搜, 公式是: 1 / (1-loadFactor)

• 對應(yīng)的圖:

  img

• 圖片解析:

  • 當(dāng)填裝因子是0.5時廷蓉，成功和不成的查找平均需要2次比較
  • 當(dāng)填裝因子為2/3時，分別需要2.37和3.0次比較
  • 當(dāng)填裝因子為0.8時马昙，分別需要2.9和5.0次
  • 因此對于較高的填裝因子桃犬，對比線性探測，二次探測和再哈希法還是可以忍受的给猾。

鏈地址法

• 鏈地址法的效率分析有些不同, 一般來說比開放地址法簡單. 我們來分析一下這個公式應(yīng)該是怎么樣的.

  • 假如哈希表包含arraySize個數(shù)據(jù)項, 每個數(shù)據(jù)項有一個鏈表, 在表中一共包含N個數(shù)據(jù)項.
  • 那么, 平均起來每個鏈表有多少個數(shù)據(jù)項呢? 非常簡單, N / arraySize.
  • 有沒有發(fā)現(xiàn)這個公式有點眼熟? 其實就是裝填因子.

• OK, 那么我們現(xiàn)在就可以求出查找成功和不成功的次數(shù)了

  • 成功可能只需要查找鏈表的一半即可: 1 + loadFactor/2
  • 不成功呢? 可能需要將整個鏈表查詢完才知道不成功: 1 + loadFactor.

• 對應(yīng)的圖

  img

效率的結(jié)論

• 經(jīng)過上面的比較我們可以發(fā)現(xiàn), 鏈地址法相對來說效率是好于開放地址法的.
• 所以在真實開發(fā)中, 使用鏈地址法的情況較多, 因為它不會因為添加了某元素后性能急劇下降.
  • 比如在Java的HashMap中使用的就是鏈地址法.
• 代碼實現(xiàn):
  • 到目前為止, 我們講了很久的哈希表原理, 依然沒有寫任何代碼.
  • 因為我覺得理解了原理, 再去寫代碼相對思路會清晰一些.
  • 后面, 我會使用鏈地址法來實現(xiàn)我們的哈希表(你也可以試著使用開放地址法來實現(xiàn), 原理已經(jīng)非常清晰了)
  • 但是, 我們還有N多的細(xì)節(jié), 可以深入探討.
  • 欲知后事如何, 且聽下回分解!!!