「雜湊表(hash table)」,又可稱為「哈希表」,是透過鍵(key)值找到資料在記憶體位置的儲存方式。將數據透過雜湊函式(hash function)映射(map)到其在表中的對應位置後,可同步降低操作時的「空間複雜度」與「時間複雜度」。


雜湊函式(hash function)

可將我們熟悉的「明文(plaintext)」轉為長度與格式固定的「密文(ciphertext / cyphertext)。只要明文改變,密文就要跟著改變,且無法從密文反推明文。這個密文即為「雜湊值(hash value)」。

雜湊函式被廣泛應用於密碼學中,如區塊鏈即利用「加密雜湊函式(cryptographic hash function)」將資料加密。

雜湊函式示意圖(取 SHA-256 前六碼為例)


雜湊函式運算方法

常見的雜湊函式以「除法」或「乘法」實現,兩者都可以透過資料的「key」值找到對應的記憶體存放位置。下列範例中,雜湊表為陣列,每筆資料的儲存位置都有對應的索引值。

「載荷因子(load factor)」代表資料個數(設為 n)與雜湊表大小(設為 m)的比例,其值越大,越容易產生多筆資料放在同一個空間的「雜湊衝突(hash collision)」現象。如果載荷因子大於 1,根據「鴿巢原理(pigeonhole principal)」,雜湊衝突將不可避免。

除法(division method)

取雜湊表大小為 m,每筆資料在雜湊表中的索引值(index)為「key % m」,其中 0≤index<m。

現假設有 A(key=11424)、B(key=6254)、C(key=4171)、D(key=554) 四筆資料,雜湊表共有 6 個儲存空間,載荷因子為 4/6=66.7%。四筆資料經雜湊函式以除法運算後,可得各自對應的位置如下:

在上圖中,B、D 經過雜湊函式的模除運算後皆為 2,即會產生雜湊衝突。

使用除法進行雜湊函式運算時,「m」的值應遠離 2ᵖ,否則不管「key」值多大,當中十位數以上的數字都能夠被「m」整除,經模除運算的結果非常有限,將會產生非常多衝突。

乘法(multiplication method)

取雜湊表大小為 m,每筆資料在雜湊表中的索引值(index)為「[m·(( key · A)% 1)]」,其中 0≤index≤(m–1)。

這樣的算法看似複雜,我們可以拆為下列幾個步驟一一理解:

  1. 將「key」值乘上一個小於 1 的無理數 A(常用 (√5–1)/2),得一個更大的無理數。
  2. 將步驟 1. 求得的大無理數模除 1,去掉整數部分,剩下小數。
  3. 將 m 乘以步驟 2. 求出的小數,將小數點右移,得界於 0~(m–1) 之間的無理數。
  4. 將步驟 3. 求出的無理數取高斯符號,得界於 0~(m–1) 之間的整數,這個整數就是「key」值的索引值。

各步驟與原理圖示如下,為了方便觀察,當中的「key」與「A」都轉為二進制(binary),因此第 2 步驟(黃色部分)的模除項目由 1 改為 2ʷ:

跟除法相比,乘法在進行上述步驟運算時,同步將「key」中更多不同的部分都納入考量,可以提高隨機性(參考上圖中央半透明橘框部分),且 m 不再有要遠離 2ᵖ 這個限制。

現假設一樣有 A(key=11424)、B(key=6254)、C(key=4171)、D(key=554) 四筆資料,雜湊表共有 6 個儲存空間,載荷因子為 4/6=66.7%。四筆資料經雜湊函式以乘法運算後,可得各自對應的位置如下:

即便經過複雜的乘法運算,雜湊衝突依然不可避免。


處理雜湊衝突

常見的雜湊衝突處理方式可分為「封閉尋址法(closed addressing / chaining)」及「開放定址法(open addressing)」兩大類。


封閉尋址法(closed addressing / chaining)

在每個儲存空間中再生成新的子鏈狀儲存空間,可用「鏈結串列(linked list)」或「陣列(array)」實現。

使用「鏈結串列(linked list)」實現封閉尋址

使用「陣列(array)」實現封閉尋址


開放定址法(open addressing)

透過「探測(probing)」尋找仍未儲存資料的儲存空間,主要可分為「線性探測法(linear probing)」與「平方探測法(quadratic probing)」兩種。

使用「線性探測法(linear probing)」實現開放尋址


使用「平方探測法(quadratic probing)」實現開放尋址

若不使用探測,也可在衝突發生時,再跑另一個雜湊函式,也就是「雙雜湊(double hashing)」,若依然衝突,則持續進行雜湊運算,直到沒有衝突為止。現假設第一個雜湊函式為 F₁(x)、第二個雜湊函式為 F₂(x),而要計算的「key」值為 k:

  1. 第一次雜湊函式運算,得 index₁=F₁(k)。
  2. 若有衝突,進行第二次雜湊運算,得 index₂=F₁(k)+1*F₂(k)。
  3. 若仍有衝突,進行第三次雜湊運算,得 index₃=F₁(k)+2*F₂(k)。
  4. 若仍有衝突,進行第三次雜湊運算,得 index₄=F₁(k)+3*F₂(k)。

若仍有衝突則按「indexₙ=F₁(k)+(n–1)*F₂(k)」的規則持續運算,直到找到的「indexₙ」不再與舊的儲存資料有衝突為止。


程式碼範例(JavaScript)

下列程式碼以「陣列」實現封閉循址處理雜湊衝突。

class HashTable {
    constructor(size){
        this.size = size;
        this.table = [];

        //要在table這個陣列中每個索引值對應的位置都再放入小陣列
        for(let i=0; i<this.size; i++){
            this.table.push([]);
        }
    }

    //以除法實現雜湊函式
    hash1(key){
        return key%(this.size);
    }

    //以乘法實現雜湊函式
    hash2(key){
        let A = (Math.sqrt(5)-1)/2;
        return Math.floor((this.size)*((key*A)%1));
    }

    //將一筆key-value pair放進雜湊表
    set(key, value){ 
        let index = this.hash2(key); //用雜湊函式處理key值,設定該筆資料索引值
        this.table[index].push({key,value}); //以物件形式將key-value pair放進對應索引位置
    }

    //輸入key值,從雜湊表取得對應的value
    get(key){
        let index = this.hash2(key); //用雜湊函式處理key值,找到該筆資料索引值

        //因可能有雜湊衝突,即同一個索引位置有不只一筆資料,因此用for迴圈在該索引位置內跑,找到與輸入key值相符者才是正確資料
        for(let i = 0; i < this.table[index].length; i++){
            if(this.table[index][i].key === key){
                console.log(this.table[index][i]);
                return;
            } 
        }
        console.log("not in this table") //如果雜湊表中找不到對應資料,則顯示"not in this table"
    }

    //顯示雜湊表
    printAll(){
        console.log(this.table);
    }
}

時間複雜度

  1. 平均&最佳情況:O(1),在多數情況下,可透過雜湊函式求「key」值,直接找到對應位置並進行操作。
  2. 最差情況:O(n),若產生雜湊衝突且使用「封閉循址法」處理,則在同一個「key」值的儲存空間中要再做一次搜尋。

空間複雜度

視處理雜湊衝突時使用「封閉尋址法」或「開放定址法」而定:

  1. 封閉循址法:O(m+n) = O(n),原本雜湊表的大小為 m,但另外需要 n 個儲存空間處理對應到同一索引值的資料。
  2. 開放定址法:O(n),資料透過不斷探測,在原雜湊表中找到空的位置儲存,所有資料佔據的總空間大小不變。

參考資料

  1. Hash Table:Intro(簡介)
  2. Time and Space Complexity of Hash Table operations
#資料結構 #雜湊表







你可能感興趣的文章

Python Table Manners - 測試 (一)

Python Table Manners - 測試 (一)

[BE101]  留言板(上-基礎實作篇)

[BE101] 留言板(上-基礎實作篇)

JS30 Day 20 筆記

JS30 Day 20 筆記






留言討論