JavaScript資料結構與算法 - 哈希表詳解

哈希表通常是基于數組進行實作的,但是相對于數組,它也很多的優勢和不足.

優勢：

• 它可以提供非常快速的插入-删除-查找操作
• 無論多少資料,插入和删除值需要接近常量的時間:即O(1)的時間級.實際上，隻需要幾個機器指令即可完成
• 哈希表的速度比樹還要快，基本可以瞬間查找到想要的元素
• 哈希表相對于樹來說編碼要容易很多.

不足:

• 哈希表中的資料是沒有順序的,是以不能以一種固定的方式(比如從小到大)來周遊其中的元素
• 通常情況下。哈希表中的key是不允許重複的,不能放置相同的key.用于儲存不同的元素.

1. 哈希表的一些概念

1.1 哈希化

​ 将大數字轉化成數組範圍内下标的過程,我們就稱之為哈希化.

1.2 哈希函數

​ 通常我們會将字元串轉成大數字,大數字在進行哈希化的代碼實作放在一個i

1.3 哈希表

​ 最終将資料插入到的這個數組,對整個結構的封裝,我們就稱之為是一個哈希表

2. 解決沖突

元素通過哈希化了獲得的數組下标跟其他的已有的元素下标重複，就叫做沖突

常見的解決沖突的方法有兩種：

• 鍊位址法
• 開放位址法

3. 鍊位址法（拉鍊法）

每個下标處存儲一個連結清單或數組，當擷取到下标值後，在周遊連結清單/數組依次查找元素

• 圖檔解析:
  • 從圖檔中我們可以看出，鍊位址法解決沖突的辦法是每個數組單元中存儲的不再是單個資料,而是一個鍊條
  • 這個鍊條使用什麼資料結構呢?常見的是數組或者連結清單
  • 比如是繼表,也就是每個數組單元中存儲着一個連結清單.一旦發現重複,将重複的元素插入到連結清單的首端或者未端即可
  • 當查詢時,先根據哈希化後的下标值找到對應的位置再取對外連結表，依次查詢找尋找的資料
• 數組還是連結清單呢?
  • 數組或者連結清單在這裡其實都可以,

    效率上也差不多

    因為根據哈希化的index找出這個數組或者連結清單時,通常就會使用線性查找，這個時候數組和連結清單的效率是差不多的
  • 當然在某些實作中，會将新插入的資料放在數組或者連結清單的最前面,因為覺得新插入的資料用于取出的可能性更大

  • 這種情況最好采用連結清單

    ，因為數組在首位插入資料是需要所有其他項後移的,連結清單就沒有這樣的問題
  • 當然,我覺得出于這個也看業務需求,不見得新的資料就通路次數會更多:比如我們微信新添加的好友,可能是剛認識的,聯系的頻率不見得比我們的老朋友更多，甚至新加的隻是聊一兩句
  • 是以,這裡個人覺得選擇資料或者連結清單都是可以的.

4. 開放位址法

開放位址法主要工作方式是尋找空白的單元格來添加重複的資料

尋找空白位置有三種方法：

• 線性探測法
• 二次探測法
• 再哈希法

4.1 線性探測

線性探測即線性的查找空白的單元格

插入32

• 經過哈希化得到的index=2，但是在插入的時候發現該位置已經有了82.怎麼辦呢?
• 線性探測就是從index位置+1開始一點點查找合适的位置來放置32,什麼是合适的位置呢?
• 空的位置就是合适的位置，在我們上面的例子中就是index=3的位置,這個時候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.會發現連續的單元都不允許我們放置資料,并且在這個過程中我們需要探索多次
• 二次探測可以解決一部分這個問題

4.2 二次探測

• 二次探測線上性探測的基礎上進行了優化:
  • 二次探測主要優化的是

    探測時的步長

    ,什麼意思呢?

  • 線性探測

    ，我們可以看成是步長為1的探測,比如從下标值x開始,那麼線性測試就是x+1,x+2,x+3依次探測

  • 二次探測

    ,對步長做了優化，比如從下标值x開始,x+12,x+23,x+33.
  • 這樣就可以

    一次性探測比較長的距離

    ，比避免那些聚集帶來的影響.
• 二次探測的問題:
  • 但是二次探測依然存在問題,比如我們連續插入的是32-112-82-2-192,那麼它們依次累加的時候步長的相同的.
  • 也就是這種情況下會造成步長不一的一種聚集.還是會影響效率(當然這種可能性相對于連續的數字會小一些)
  • 怎麼根本解決這個問題呢?讓每個人的步長不一樣，一起來看看再哈希法吧.

4.3 再哈希化

為了消除線性探測和二次探測中無論步長+1還是步長+平法中存在的問題，我們可以使用再哈希法

再哈希法:

• 二次探測的算法産生的探測序列步長是固定的:1,4,9，16,依次類推
• 現在需要一種方法:産生一種依賴關鍵字的探測序列,而不是每個關鍵字都一樣
• 那麼不同的關鍵字即使映射到相同的數組下标,也可以使用不同的探測序列
• 再哈希法的做法就是:把關鍵字用另外一個哈希函數,再做一次哈希化,用這次哈希化的結果作為步長
• 對于指定的關鍵字，步長在整個探測中是不變的,不過不同的關鍵字使用不同的步長

第二次哈希化需要具備如下特點:

• 和第一個哈希函數不同.(不要再使用上一次的哈希函數了,不然結果還是原來的位置)
• 不能輸出為0(否則,将沒有步長.每次探測都是原地踏步，算法就進入了死循環)
• 其我們不用費腦細胞來設計了,計算機專家已經設計出一種工作很好的哈希函數:

  • stepSize = constant - (key - constant)

  • 其中constant是質數,且小于數組的容量
  • 例如:

    stepSize = 5 -(key % 5)

    ，滿足需求,并且結果不可能為0.

5. 哈希化的效率

• 哈希表中執行插入和搜尋操作效率是非常高的
• 如果

  沒有産生沖突

  ,那麼效率就會更高。如果

  發生沖突

  ，存取時間就依賴後來的

  探測長度

  。
• 平均探測長度以及平均存取時間，取決于

  填裝因子

  ，随着填裝因子變大，探測長度也越來越長。
• 随着填裝因子變大，效率下降的情況，在不同開放位址法方案中比鍊位址法更嚴重,是以我們來對比一下他們的效率，再決定我們選取的方案.
• 在分析效率之前,我們先了解一個概念:

  裝填因子

  .
  • 裝填因子表示目前哈希表中已經

    包含的資料項

    和

    整個哈希表長度

    的

    比值

  • 裝填因子=總資料項/哈希表長度

  • 開放位址法的裝填因子最大是1

    ,因為它必須尋找到空白的單元才能将元素放入，總資料項最多等于哈希表長度

  • 鍊位址法的裝填因子可以大于1

    ,因為拉鍊法可以無限的延伸下去，隻要你願意.(當然後面效率就變低了)

6. 線性探測效率

下面的等式顯示了線性探測時，探測序列§和填裝因子(L)的關系

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

  

  圖檔解析.:
• 當填裝因子是1/2時，成功的搜尋需要1.5次比較，不成功的搜尋需要2.5次
• 當填裝因子為2/3時，分别需要2.0次和5.0次比較
• 如果填裝因子更大，比較次數會非常大。
• 應該使填裝因子保持在2/3以下，最好在1/2以下，另一方面，填裝因子越低，對于給定數量的資料項，就需要越多的空間。
• 實際情況中，最好的填裝因子取決于存儲效率和速度之間的平衡，随着填裝因子變小，存儲效率下降，而速度上升。

7. 二次探測和再哈希化

二次探測和再哈希法的性能相當。它們的性能比線性探測略好。

• 對成功的搜尋，公式是:

  -log2(1 - loadFactor) / loadFactor

• 對于不成功的搜搜,公式是:

  1/(1-loadFactor)

  

  圖檔解析:
• 當填裝因子是0.5時，成功和不成的查找平均需要2次比較
• 當填裝因子為2/3時，分别需要2.37和3.0次比較
• 當填裝因子為0.8時，分别需要2.9和5.0次
• 是以對于較高的填裝因子，對比線性探測，二次探測和再哈希法還是可以忍受的。

8. 鍊位址法

鍊位址法的效率分析有些不同,一般來說比開放位址法簡單，效率也比開放位址法好。我們來分析一下這個公式應該是怎麼樣的

• 假如哈希表包含

  arraySize

  個資料項,每個資料項有一個連結清單,在表中一共包含N個資料項
• 那麼,平均起來每個連結清單有

  N / arraySize

  個資料項
• 上面那個公式就是裝填因子.

怎麼求出查找成功和不成功的次數：

• 成功可能隻需要查找連結清單的一半即可: 1 + loadFactor/2
• 不成功呢?可能需要将整個連結清單查詢完才知道不成功: 1 + loadFactor.

是以在真實開發中，使用鍊位址法的情況較多

• 因為它不會因為添加了某元素後性能急劇下降
• 比如在Java的HashMap中使用的就是鍊位址法.

9. 哈希函數

9.1 哈希函數的優點

• 快速的計算
  • 哈希表的優勢就在于效率,是以快速擷取到對應的

    hashCode

    非常重要.
  • 我們需要通過快速的計算來擷取到元素對應的

    hashCode

• 均勻的分布
  • 哈希表中，無論是鍊位址法還是開放位址法。當多個元素映射到同一個位置的時候,都會影響效率
  • 是以優秀的哈希函數應該盡可能将元素映射到不同的位置，讓元素在哈希表中均勻的分布.

9.2 提高哈希函數計算效率

• 讓哈希函數中盡量

  減少乘法和除法

  ，因為它們的性能是比較低的。
• 使用

  霍納法則

  優化多項式，減少乘法和除法

  • - 未優化前：
    	a(n)x^n+a(n-1)x^(n-1)+...a(1)x+a(0);
    	+ 乘法次數：n+(n-1)+...+1=n(n+1)/2
    	+ 加法次數：n次
    	+ 時間複雜度：O(n^2)
    	
    - 優化後
    	Pn(x)=anx^n+a(n-1)x^(n-1)+...+a1x+a0=
    	((...(((anx+an-1)x+an-2)x+an-3)...)x+a1)x+a0
    	+ 乘法次數：n次
    	+ 加法次數：n次
    	+ 時間複雜度：O(n)
               

9.3 均勻分布

• 在設計哈希表時,我們已經有辦法處

  理映射到相同下标值

  的情況:鍊位址法或者開放位址法
• 但是無論哪種方案,為了提供效率,最好的情況還是讓資料在哈希表中

  均勻分布

• 是以,我們需要在

  使用常量的地方

  ,盡量使用

  質數

  .

質數的使用: (質數是指在大于1的自然數中，除了1和它本身以外不再有其他因數的自然數。)

• 哈希表的長度
• N次幂的底數(我們之前使用的是27)

**思考：**為什麼他們使用質數.會讓哈希表分布更加均勻呢?

• 假設表的容量不是質數,例如:表長為15(下标值0~14)
• 有一個特定關鍵字映射到D,步長為5.探測序列是多少呢?
• 0-5-10-0-5-10,依次類推,循環下去.
• 算法隻嘗試着三個單元,如果這三個單元已經有了資料。那麼會一直循環下去,直到程式崩潰
• 如果容量是一個質數。比如13.探測序列是多少呢?
• 0-5-10-2-7-12-4-9-1-6-11-3,一直這樣下去
• 不僅不會産生循環，而且可以讓資料在哈希表中更加均勻的分布.

9.4 實作哈希函數

// 實作哈希函數
// 1. 将字元串轉換為較大的數字：hashCode
// 2. 将數字hashCode壓縮到數組範圍之内
function hashfun(str,size){
    var hashCode = 0;

    // 霍納法則公式
    for (let i = 0; i < str.length; i++) {
        // string.charCodeAt(index): 傳回字元串index位字元的Unicode 編碼
        // 相當于霍納法則裡的：anx+an-1
        // ((...(((anx+an-1)x+an-2)x+an-3)...)x+a1)x+a0
        // 37是一個質數，也可以寫其他質數，質數比較常用37
        hashCode = 37 * hashCode + str.charCodeAt(i);
        console.log(str.charCodeAt(i));
    }

    // 取餘
    var index = hashCode % size;
    return index;
}
           

10. 建立哈希表

10.1 建立

我們這裡采用

鍊位址法

來實作哈希表:

• 實作的哈希表(基于storage的數組)每個index對應的是一個數組(bucket).(當然基于連結清單也可以.)
• bucket中存放什麼呢?我們最好将key和value都放進去,我們繼續使用一個數組.(其實其他語言使用元組更好)
• 最終我們的哈希表的資料格式是這樣:[[ [k,v],[k,v],[k,v] ],[[k,v],[k,v] ],[ [k,v]]]

代碼解析

我們定義了三個屬性:

• storage

  作為我們的數組,數組中存放相關的元素

• count

  表示目前已經存在了多少資料

• limit

  用于标記數組中一共可以存放多少個元素.

function Hash(){
    var storage = [];   
    var count = 0;      
    var limit = 7;
}
           

實作哈希函數

// 實作哈希函數
// 1. 将字元串轉換為較大的數字：hashCode
// 2. 将數字hashCode壓縮到數組範圍之内
function hashfun(str,size){
    var hashCode = 0;

    // 霍納法則公式
    for (let i = 0; i < str.length; i++) {
        // string.charCodeAt(index): 傳回字元串index位字元的Unicode 編碼
        // 相當于霍納法則裡的：anx+an-1
        // ((...(((anx+an-1)x+an-2)x+an-3)...)x+a1)x+a0
        // 37是一個質數，也可以寫其他質數，質數比較常用37
        hashCode = 37 * hashCode + str.charCodeAt(i);
        console.log(str.charCodeAt(i));
    }

    // 取餘
    var index = hashCode % size;
    return index;
}
           

10.2 插入&修改資料

哈希表的插入和修改操作是同一個函數：

• 因為,當使用者傳入一個<Key,Value>時
• 如果原來不存在該key,那麼就是插入操作
• 如果已經存在該key,那麼就是修改操作

代碼解析

• 步驟1:根據傳入的key擷取對應的

  hashCode

  ,也就是數組的

  index

• 步驟2:從哈希表的

  index

  位置中取出桶（另外一個數組）
• 步驟3:檢視上一步的

  bucket

  是否為

  null

  • 為

    nul

    , 表示之前在該位置沒有放置過任何的内容,那麼就建立一個數組
• 步驟4.檢視是否之前已經放置過

  key

  對應的

  value

  • 如果放置過,那麼就是依次替換操作,而不是插入新的資料
  • 我們使用一個變量

    override

    來記錄是否是修改操作
• 步驟5:如果不是修改操作,那麼插入新的資料
  • 在

    bucket

    中

    push

    新的

    [key value]

    即可
  • 注意:這裡需要将

    count+1

    ,因為資料增加了一項

// 插入&修改操作
HashTable.prototype.put = function(key, value){
    // 1. 根據key擷取對應的hashcode，也就是數組的下标
    var index = this.hashfun(key, this.limit);

    // 2. 根據index取出對應的bucket
    var bucket = this.storage[index];

    // 3. 檢視`bucket`是否為`null`
    if (bucket == null) {
        // 如果為空，就建立一個數組，存放到index位置
        bucket = [];
        this.storage[index] = bucket;
    }

    // 4. 判斷是否是修改資料
    for (let i = 0; i < bucket.length; i++) {
        // if (bucket[i][0] == key) {
        //     bucket[i][1] = value;
        // }else if (bucket[i] == null) {
        //     bucket[i][0] = key;
        //     bucket[i][1] = value;
        //     bucket.push([key,value]);
        // }
        // return 

        // 定義一個數組存放bucket裡的元素
        var tuple = bucket[i];
        if (tuple[0] == key) {
            tuple[1] = value;
            return;
        }
    }

    // 添加
    bucket.push([key,value]);
    this.count += 1;
}
           

10.3 擷取操作

// 擷取操作
HashTable.prototype.get = function(key){
    // 1. 通過傳來的key擷取hashCode，查找到對應的元素
    this.index = this.hashfun(key,this.limit);

    // 2. 根據index取出對應的bucket
    var bucket = this.storage[index];

    // 3. 判斷bucket是否為空
    if (bucket == null) return null;

    // 4. 查找元素
    for (let i = 0; i < bucket.length; i++) {
        var tuple = bucket[i];
        if (tuple[0] == key) {
            return tuple[1];
        }
        return null;
    }
}
           

10.4 删除操作

// 删除操作
HashTable.prototype.delete = function(key){
    // 1. 通過傳來的key擷取hashCode，查找到對應的元素
    this.index = this.hashfun(key,this.limit);

    // 2. 根據index取出對應的bucket
    var bucket = this.storage[index];

    // 3. 判斷bucket是否為空
    if (bucket == null) return null;

    // 4. 查找元素
    for (let i = 0; i < bucket.length; i++) {
        var tuple = bucket[i];
        if (tuple[0] == key) {
            bucket.splice(i,1);
            this.count--;
            return tuple[1];
        }
        return null;
    }
}
           

10.5 測試

var hash = new HashTable();
hash.set('abc', 123);
hash.set('cds', 234);

hash.get('abc');
           

11. 哈希表擴容思想

• 為什麼需要擴容?
  • 目前,我們是将所有的資料項放在長度為7的數組中的.
  • 因為我們使用的是鍊位址法,

    loadFactor

    可以大于1,是以這個哈希表可以無限制的插入新資料

    • loadFactor

      就是前面第五點哈希化的效率中提到過的：裝填因子
  • 但是随着資料量的增多,每一個index對應的bucket會越來越長，,也就造成效率的降低
  • 是以在合适的情況對數組進行擴容.比如擴容兩倍
• 如何進行擴容?
  • 擴容可以簡單的将容量增大兩倍(不是質數嗎?質數的問題後面再讨論)
  • 但是這種情況下.所有的資料項一定要同時進行修改(重新調用哈希函數.來擷取到不同的位置)
  • 比如

    hashCode=12

    的資料項,在

    length=8

    的時候,

    index=4

    .在長度為16的時候呢?

    index=12

  • 這是一個耗時的過程,但是如果數組需要擴容,那麼這個過程是必要的.
• 什麼情況下擴容呢?
  • 比較常見的情況是

    loadFactor>0.75

    的時候進行擴容.
  • 比如Java的哈希表就是在裝填因子大于0.75的時候,對哈希表進行擴容.

12. 高效的質數判斷

• 對于每個數n，其實并不需要從2判斷到n-1
• 一個數若可以進行因數分解，那麼分解時得到的兩個數一定是一個小于等于sqrt(n)，一個大于等于sqrt(n)
• 比如16可以被分解為

  2*8

  ,2小于sqrt(16),也就是4, 8大于4。而

  4*4

  都是等于sqrt(n)。
  • 就是說在小于sqrt(n)的數裡，如果n不是質數，那麼總有一個數能被他整除
• 是以其實我們周遊到等于sqrt(n)即可

function prime(num){
	var temp = parseInt(Math.sqrt(num));
    for (let i = 0; i <= temp; i++) {
        if (num % i == 0) {
            return false;
        }
    }

    // for (let i = 2; i < num; i++) {
    //     if (num % i == 0) {
    //         return false;
    //     }
    // }
    return true;
    }   
}
           

13. 實作容量恒為質數

• 新增方法

  // 判斷某個數字是否是質數
  HashTable.prototype.isPrime = function (num){
      var temp = parseInt(Math.sqrt(num));
      for (let i = 0; i <= temp; i++) {
          if (num % i == 0) {
              return false;
          }
      }
      return true;
  }
  
  // 擷取質數
  HashTable.prototype.getPrime = function(num){
      while(this.getPrime(num)){
          num++;
      }
      return num;
  }
             

• 修改set方法

  // 6. 判斷是否需要擴容
  if (this.count > this.limit * 0.75) {
      var newSize = this.limit * 2;
      var newPrime = this.getPrime(newSize);
      this.resize(newPrime);
  }
             

• 修改delete方法

  // 判斷是否需要減小容量
  if (this.limit > 7 && this.count < this.limit * 0.25) {
      var newSize = Math.floor(this.limit / 2);
      var newPrime = this.getPrime(newSize);
      this.resize(newPrime);
  }
             

14. 完整代碼

完整代碼