--- tags: 資料結構, LeetCode disqus: HackMD --- # 雜湊表(Hash Table) :::spoiler 文章目錄 [toc] ::: ## 遇到問題 在一陣列中，我們放入成對`key`和`value`的數值，`key`為球員背號，`value`為球員名稱，假設要查找四號球員，用下列兩種方式查找會遇到一些問題 * 透過**線性搜尋**，查找速度較慢，為$O(n)$ * 將球員背號放入相對應`array`位置，直接使用它們的鍵值作為索引，稱作`Direct Address Table`，使用這種方式查找速度非常快，但如果數據總數與最大值之間有很大的差距，會導致記憶體空間浪費 ![](https://i.imgur.com/eVyPjU3.jpg) 為解決以上問題我們可以使用雜湊表 ## 介紹 雜湊表是資料結構的一種，主要用來進行有效率的數據搜尋。 雜湊表它將鍵映射到值。它使用雜湊函數`Hash Function`將鍵映射到數組中的桶`(Bucket)`，從而使查找，插入和刪除操作的時間複雜度達到$O(1)$，如下圖所示。它們被廣泛用於多種計算機軟件，特別是關聯數組`(associative arrays)`、數據庫索引`(database indexing)`、緩存`(caches)`和集合`(sets)`。 在實現雜湊表時，需要考慮具體的應用場景，選擇合適的雜湊函數和衝突解決方法，以達到最好的性能和空間效率。 ![](https://i.imgur.com/YUBcijC.png) ## 常見名詞 * **Collision(碰撞)**: 兩筆資料經過雜湊函數運算後雜湊值相同，都對應到同一個位置。 * **Bucket(桶)**: `Hash Table`儲存資料的位置，每一個位置對應一個`Bucket Address`。 <!-- * Slot(槽): 每一個桶中的資料欄位，假設發生`Collision`，將會檢查儲存桶，尋找還未佔用的槽 --> ## 常見的雜湊函數如下 雜湊的過程如下 ![](https://i.imgur.com/bX0Pt7g.png) (圖片來自於[Division Modulo Method - Hashing Technique](https://www.digitalbithub.com/learn/division-modulo-method-hashing-technique)) ### 除留餘數法`Division Method` > 相對其他雜湊函數簡單易用，計算速度較快 ![](https://i.imgur.com/WDAbNIH.jpg) (圖片來自於[Division Modulo Method - Hashing Technique](https://www.digitalbithub.com/learn/division-modulo-method-hashing-technique)) `Division`的方法就是將`Key`值去除以`Hash Table`長度得到的**餘數**，就是`Hash Table`的`Key`值。 ```javascript= // Division Method // mod = 除法 // m = Hashtable 的長度 // Index 等於 Key 除以 Hashtable 的長度 Index = Key mod m ``` 例如`key`值等於`99`除以`Hash Table`長度為`10`，餘數就等於`9` ```javascript= let index = 99 % 10 // 9 ``` 除留餘數法相對簡單，但是容易發生雜湊衝突。為了減少雜湊衝突的概率，可以使用其他雜湊函數，例如接下接下來要說的乘法雜湊法`（Multiplication Method）`。同時，為了解決雜湊衝突，還可以採用開放定址法、鏈結法等衝突解決方法。 #### 建構要點 * 選擇一個質數作為雜湊表的大小，可以減少雜湊衝突的概率。 * 如果雜湊表的大小為 $m$，則雜湊函數的值域必須是 0 到 $m - 1$ * $m$不能是`2`的平方，因為$10^p$會被$2^p$整除，較容易造成很多`collision` * 假設`key`值不是數字是英文名稱，我們須先把名稱轉成一些數字，若英文名稱相近，會造成很多`collision` * 如果發生雜湊衝突，可以採用衝突解決方法包括開放定址法、鏈結法等。 ### 乘法雜湊法Multiplication Method > 相對其他雜湊函數易於實現，並改善了雜湊衝突 ![](https://i.imgur.com/NH95tix.jpg) (圖片來自於[Lecture 11 oct 7 Goals](https://slideplayer.com/slide/5226941/)) 基本原理是通過將關鍵字與某個常數相乘再取小數部分來得到雜湊地址，具體來說，對於一個關鍵字`k`，假設雜湊表的大小為`m`，常數`A`為一個介於`0`和`1`之間的常數，則使用`Multiplication Method`計算雜湊地址`h(k)`的公式為： ``` h(k) = floor(m * (k * A mod 1)) ``` :::info 那要如何找到常數`A`呢? 根據[Knuth](https://en.wikipedia.org/wiki/Donald_Knuth)的說法，選擇黃金比例: $A=\cfrac{\sqrt{5}-1}{2}≈0.6180339887...$ 至於程式的實作上，利用**bit-shifting**會更有效率，請參考：[Geoff Kuenning：Hash Functions](https://www.cs.hmc.edu/~geoff/classes/hmc.cs070.200101/homework10/hashfuncs.html) ::: 其中，`floor`表示向下取整函數， $k * A \ mod \ 1$ 表示 `k` 與 `A` 的乘積除以 `1` 的餘數（即小數部分），`m` 為雜湊表的大小。由於 $k * A \ mod \ 1$ 的結果始終在$[0,1]$之間，因此乘以 `m` 後可以得到一個介於 `0` 和 `m-1` 之間的整數，作為雜湊地址。 `Multiplication Method`的優點是相對簡單且雜湊地址的分佈比較均勻，可以有效地降低雜湊衝突的概率。不過，選擇合適的常數`A`對於雜湊表的性能影響很大，需要根據實際情況進行調整。此外，如果雜湊表的大小不是 `2` 的次方，可能會影響雜湊地址的均勻性。 在實際應用中，`Multiplication Method`常用於解決靜態雜湊表的構建問題，即在雜湊表初始化之後，不再需要頻繁地進行插入和刪除操作的情況。而對於動態雜湊表，由於元素數量的不斷變化，需要採用更加複雜的雜湊函數來解決雜湊衝突的問題 #### 建構要點 * 確定乘數常數`A`：在使用`Multiplication Method`計算雜湊地址時，需要先確定乘數常數A，通常選擇一個介於0和1之間的無理數，盡量接近於$(n * (√5 - 1) / 2)$的值，通常常用的乘數常數`A`值为`0.6180339887`。 * 確定雜湊表的大小：雜湊表的大小是指雜湊表中可以存儲的元素數量，一般選擇質數或2的次方。 * 計算雜湊地址：使用Multiplication Method計算雜湊地址的公式為：$h(k) = floor(m * (k * A \ mod \ 1))$，其中m為雜湊表的大小，k為要插入或查找的鍵值，A為乘數常數。需要注意的是，計算過程中需要先將k與A相乘，然後取其小數部分，並將結果乘以m，最後向下取整得到雜湊地址。 * 處理雜湊衝突：由於雜湊函數不一定能夠將所有的鍵映射到唯一的雜湊地址，可能會出現雜湊衝突。常用的解決雜湊衝突的方法有鍊錶法和開放地址法。 ## 複雜度 ### 時間複雜度 | Action動作 | 平均 | 最壞 | | ---------- | ------ | ------ | | 訪問`(Access)` | N/A | N/A | | 搜尋`(Search)` | $O(1)$ | $O(n)$ | | 插入`(Insertion)`| $O(1)$ | $O(n)$| | 刪除`(Deletion)` | $O(1)$ | $O(n)$ | ### 空間複雜度 $O(n)$ ## 雜湊表實現 ### KEY 是數字 #### Division Method > 公式: $h(k) = K \ mod \ m$ 使用除法計算雜湊地址，並通過`insert()`方法將 `key value` 在雜湊表中，使用`search()`方法根據 `key` 查找對應的值。 由於`Division Method`的簡單性，即使雜湊表的大小不是`2`的次方，也能夠快速計算雜湊地址。然而，如果雜湊表的大小不是質數，可能會導致雜湊衝突增多，需要採取一些方法來解決這個問題。 ```javascript= class HashTable { constructor(size) { this.size = size; this.table = new Array(size); } hash(key) { return key % this.size; // 取餘數計算雜湊地址 } insert(key, value) { const index = this.hash(key); if (!this.table[index]) { this.table[index] = []; } for (let i = 0; i < this.table[index].length; i++) { if (this.table[index][i].key === key) { this.table[index][i].value = value; return; } } this.table[index].push({ key, value }); } search(key) { const index = this.hash(key); if (!this.table[index]) { return null; } for (let i = 0; i < this.table[index].length; i++) { if (this.table[index][i].key === key) { return this.table[index][i].value; } } return null; } printAll() { console.log(this.table); } } // 範例使用 const hashtable = new HashTable(10); hashtable.insert(1, 'value1'); hashtable.insert(2, 'value2'); hashtable.insert(11, 'value3'); hashtable.insert(21, 'value4'); console.log(hashtable.search(1)); // 輸出：value1 console.log(hashtable.search(2)); // 輸出：value2 console.log(hashtable.search(11)); // 輸出：value3 console.log(hashtable.search(3)); // 輸出：null hashtable.printAll(); ``` #### Multiplication Method > 公式: $h(k) = floor(m * (k * A \ mod \ 1))$ 使用`Multiplication Method`計算雜湊地址，並通過`insert()`方法將`key value`在雜湊表中，使用`search()`方法根據 `key` 查找對應的值。 由於雜湊地址的均勻性，即使鍵的值不連續，也能夠快速查找到對應的值。 ```javascript= class HashTable { constructor(size) { this.size = size; this.table = new Array(size); this.a = 0.6180339887; // 黃金比例乘数常数A } hash(key) { const x = key * this.a; const val = x - Math.floor(x); // 取小數部分 return Math.floor(val * this.size); // 雜湊地址 } insert(key, value) { const index = this.hash(key); if (!this.table[index]) { this.table[index] = []; } this.table[index].push({ key, value }); } search(key) { const index = this.hash(key); if (!this.table[index]) { return null; } for (let i = 0; i < this.table[index].length; i++) { if (this.table[index][i].key === key) { return this.table[index][i].value; } } return null; } printAll() { for (let i = 0; i < this.size; i++) { if (this.table[i]) { console.log(`index: ${i}, key: ${this.table[i][0].key},value: ${this.table[i][0].value}`); } } } } // 範例使用 const hashtable = new HashTable(10); hashtable.insert(1, 'value1'); hashtable.insert(2, 'value2'); hashtable.insert(11, 'value3'); hashtable.insert(21, 'value4'); console.log(hashtable.search(1)); // 輸出：value1 console.log(hashtable.search(2)); // 輸出：value2 console.log(hashtable.search(11)); // 輸出：value3 console.log(hashtable.search(3)); // 輸出：null hashtable.printAll(); // 輸出：index: 2, key: 2,value: value2.... ``` ### KEY 是字串 > 轉換的所產生的數字要夠隨機，不然容易產生衝突 :::warning 注意，這個實作僅供參考，實際應用中需要考慮更多的因素， 字串轉換有許多方式，範例使用轉換 `Unicode` 方式 ::: * `divideHash` 方法接受一個字串，使用 `division Method` 將其轉換為雜湊值 * `multiplicationHash` 方法接受一個字串，使用 `multiplication method` 將其轉換為雜湊值。常數 `A` 選用黃金比例為 `0.6180339887`，，可以較好地分散雜湊值。 * `set` 方法接受一個鍵和值，將其存儲在雜湊表中。 * `get` 方法接受一個鍵，返回與該鍵關聯的值，如果該鍵不存在，則返回 `null`。 * `printAll` 方法輸出 `Hash table` 值 ```javascript= class HashTable { constructor() { this.size = 16; this.table = new Array(this.size); } // Divide method divideHash(key) { let hash = 0; for (let i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } return hash % this.size; } // multiplication method multiplicationHash(key) { const A = 0.6180339887; // 黄金分割率 let hash = 0; for (let i = 0; i < key.length; i++) { hash = hash * 32 + key.charCodeAt(i); } return Math.floor(this.size * ((hash * A) % 1)); } set(key, value) { const index = this.DivideHash(key); if (!this.table[index]) { this.table[index] = []; } this.table[index].push([key, value]); } get(key) { const index = this.DivideHash(key); if (!this.table[index]) { return null; } for (let i = 0; i < this.table[index].length; i++) { if (this.table[index][i][0] === key) { return this.table[index][i][1]; } } return null; } printAll() { console.log(this.table); } } let hashTable = new HashTable(); hashTable.set('a', 1); hashTable.set('b', 2); hashTable.set('c', 3); hashTable.set('d', 4); hashTable.set('e', 5); hashTable.set('f', 6); hashTable.printAll(); ``` ## 處理碰撞衝突 Collision ### 鏈結法(separate chaining) ![](https://i.imgur.com/QNTIDvE.png) (圖片來自[Hash Tables, Hashing and Collision Handling](https://medium.com/codex/hash-tables-hashing-and-collision-handling-8e4629506572) 使用一個`Linked List`，來存儲相應數據，當`hash`遇到衝突的時候依次添加到`Linked List`的後面進行處理 #### 實作 :::warning 注意，這個實作僅供參考，實際應用中需要考慮更多的因素 ::: 我們同樣使用了`Division Method`計算雜湊地址，我們鏈結法解決雜湊衝突。在`insert()`方法中，我們判斷對應位置是否已經存在一個`Linked List`。如果不存在，直接將新節點存儲在該位置上。如果存在一個`Linked List`，就遍歷`Linked List`，如果找到對應的鍵值，就更新對應的值。否則，在`Linked List`的末尾插入一個新節點。在search()方法中，我們同樣需要遍歷對應位置的`Linked List`，找到對應的鍵值對。如果`Linked List`為空，說明對應的鍵值對不存在。如果`Linked List`不為空，則遍歷`Linked List`中的每個鍵值對，如果找到對應的鍵值，就返回對應的值，否則返回null。 ```javascript= class Node { constructor(key, value) { this.key = key; this.value = value; this.next = null; } } class HashTable { constructor(size) { this.size = size; this.table = new Array(size); } hash(key) { return key % this.size; // 取餘數計算雜湊地址 } insert(key, value) { const index = this.hash(key); if (!this.table[index]) { this.table[index] = new Node(key, value); } else { let current = this.table[index]; while (current.next) { if (current.key === key) { current.value = value; return; } current = current.next; } if (current.key === key) { current.value = value; } else { current.next = new Node(key, value); } } } search(key) { const index = this.hash(key); if (!this.table[index]) { return null; } let current = this.table[index]; while (current) { if (current.key === key) { return current.value; } current = current.next; } return null; } } // 範例使用 const hashtable = new HashTable(10); hashtable.insert(1, 'value1'); hashtable.insert(2, 'value2'); hashtable.insert(11, 'value3'); hashtable.insert(21, 'value4'); hashtable.insert(31, 'value5'); hashtable.insert(12, 'value6'); hashtable.insert(22, 'value7'); console.log(hashtable.search(1)); // 輸出：value1 console.log(hashtable.search(2)); // 輸出：value2 console.log(hashtable.search(11)); // 輸出：value3 console.log(hashtable.search(3)); // 輸出：null console.log(hashtable.search(21)); // 輸出：value4 console.log(hashtable.search(31)); // 輸出：value5 console.log(hashtable.search(12)); // 輸出：value6 console.log(hashtable.search(22)); // 輸出：value7 ``` ### 開放定址法(open addressing) ![](https://i.imgur.com/T0CVnOg.gif) (圖片來自於[Open Addressing](https://prepfortech.in/interview-topics/hash-table/open-addressing/)) 開放定址法比其他解決雜湊表衝突的方法更節省空間，例如上面提到的鏈結法，其中表中的每個索引都包含`key value`對的`Linked List`。使用開放定址，無需為`Linked List`分配內存，這在內存受限的環境中非常有利。 在開放定址中，當發生衝突時，算法會在表中探測可用的槽`(Slot)`，找出第二個候補位置，如果滿了再往下尋找，直到找到空的位址，有幾種方法可以探測下一個位址， 例如上述圖片的**線性探測法**`(Linear Probing)`算法通過按順序檢查索引來搜索下一個可用槽`(Slot)`。另一種方法是**二次探測**`(quadratic probing)`，此算法檢查由探測數量的二次函數偏移的索引。第三種方法是**雙重散列**`(double hashing)`，其中算法使用第二個散列函數來確定要探測的下一個索引。 但是，如果雜湊表變得太滿，開放定址也會導致性能下降。隨著表中佔用槽的數量增加，衝突次數也增加，算法必須探測更多索引以找到可用槽。這會導致更長的查找時間和性能下降。 為了解決這個問題，普遍做法是在**負載因數 (Load factor)**(表中佔用的槽數與槽總數的比率)，超過某個閾值時調整雜湊表的大小。調整大小以及創建一個更大的新表，將舊表中的所有key value對重新散列到新表中，然後使用新表進行後續操作。 #### 線性探測法實作 :::warning 注意，這個實作僅供參考，實際應用中需要考慮更多的因素 ::: `_hash()` 函數使用了一種簡單的雜湊函數，稱為「**多項式捲動雜湊（Polynomial rolling hash）**」，它將鍵中的每個字元轉換為一個整數，並將它們加總起來。線性探測法使用 while 迴圈在哈希表中尋找可用槽位。如果目標槽位已經被佔據，則在哈希表中移動到下一個槽位，直到找到一個可用槽位或搜尋完整個哈希表。這個實現還提供了 `keys()` 和 `values()` 方法來分別返回哈希表中所有鍵和所有值的陣列。 ```javascript= class HashTable { constructor(size = 53) { this.keyMap = new Array(size); } _hash(key) { const prime = 31; let hash = 0; for (let i = 0; i < key.length; i++) { const char = key.charCodeAt(i); hash = (hash * prime + char) % this.keyMap.length; } return hash; } set(key, value) { const index = this._hash(key); if (!this.keyMap[index]) { this.keyMap[index] = [[key, value]]; } else { let i = index; while (this.keyMap[i] !== undefined && this.keyMap[i][0][0] !== key) { i = (i + 1) % this.keyMap.length; } this.keyMap[i] = [[key, value]]; } } get(key) { const index = this._hash(key); if (!this.keyMap[index]) { return undefined; } else { let i = index; while (this.keyMap[i] !== undefined && this.keyMap[i][0][0] !== key) { i = (i + 1) % this.keyMap.length; } if (this.keyMap[i] === undefined) { return undefined; } else { return this.keyMap[i][0][1]; } } } keys() { const keysArray = []; for (let i = 0; i < this.keyMap.length; i++) { if (this.keyMap[i]) { keysArray.push(this.keyMap[i][0][0]); } } return keysArray; } values() { const valuesArray = []; for (let i = 0; i < this.keyMap.length; i++) { if (this.keyMap[i]) { valuesArray.push(this.keyMap[i][0][1]); } } return valuesArray; } } ```