[資料結構]Hash Table — 雜湊表

發表於 更新於 分類於
在理解hash table之前，先來理解hash(雜湊)吧!

在理解 hash table 之前，先來理解 hash(雜湊)吧!

雜湊的特色有以下幾點:

  1. 無論原本的內容長短，經過雜湊演算法處理過的值都會是固定長度

  2. 經由雜湊處理過的資料無法反推出原本的輸入為何

  3. 兩個輸入的內容即使只差一個字， 算出來的結果會會相差非常多

  4. 常用的雜湊演算法有 MD5 和 SHA ，後者的安全性更高

生活中的例子

1.保存用戶密碼

假如小明在 A 網站的登入密碼是 12345 ，存在後端資料庫的密碼通常會經過雜湊處理，不會大喇喇地把明碼 12345 存進去，因此就算駭客侵入資料庫， 也無法推測出原本的密碼是多少，確保資料安全性，所以如果有天你在某個網站點了忘記密碼，就會把原密碼原封不動寄到信箱裡的話 ，那就要特別小心了，那個網站可能會有資安疑慮。

2.檔案驗證

假如我們打開終端機輸入 md5 檔名 ，就會發現生成一組雜湊值，可以用來驗證兩個檔案是否一樣

什麼?雜湊不等於加密嗎?

  • 加密需要有一把鑰匙， 透過鑰匙才能解密回推取得原本的內容
  • 雜湊不需要鑰匙 ，無且無法回推原本的內容是甚麼

Hash Table

Hash table 中文叫作雜湊表，又被稱為關聯式陣列，是根據 key 來查詢資料存在哪個記憶體位置的資料結構，而這個 key 是透過 hash function(雜湊函數)計算出來的，搜尋速度為 O(1)。

buckets 是儲存資料的格子

HashMap Collision

經過 hash function 算出一個索引值，但可能會發生兩組資料算出來的索引值為重複的情形，這就是 HashMap Collision(碰撞)，假如真的發生碰撞的話，就把碰撞的值放到同一個陣列裡或者是用 linked list 解決碰撞的問題，以下圖為例， Danny 和 Ella 的 id 經過 hash funciton 計算後的索引值都是 4，就會發生碰撞，所以這個時候我們可以設計成每個儲存格都是一個陣列，這樣的話遇到碰撞的值還是可以存放在同一個索引值底下。

用 js 實作 hash table

  • hash1 的 function 為 Division Method，公式為 index = key mod size， 簡單來說就是 key(id)取 size(6)的餘數
  • hash2 的 function 為 Multiplication Method，公式為 A =(√5–1)/2 , index = [m(keyA%1)]，相信這邊應該已經蠻多人眼神死了，想要瞭解完整的公式解釋可以 google Multiplication Method

在無法預先得知「Key的範圍」以及「在該範圍內Key的分佈情形」之下，使 Multiplication Method 會比較好，所以採取 hash2 來做雜湊處理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class HashTable {
  constructor(size) {
    this.size = size;
    this.table = [];
    for (let i = 0; i < this.size; i++) {
      this.table.push([]);
    }
  }
  hash1(key) {
    return key % this.size;
  }

  hash2(key) {
    let num = (Math.sqrt(5) - 1) / 2;
    return Math.floor(this.size * ((key * num) % 1));
  }

  set(key, value) {
    let index = this.hash2(key);
    this.table[index].push({ key, value });
  }

  get(key) {
    let index = this.hash2(key);
    //可能有碰撞的情形發生
    for (let i = 0; i < this.table[index].length; i++) {
      if (this.table[index][i] === key) {
        return this.table[index][i];
      }
    }
  }
  printAll() {
    console.log(this.table);
  }
}

let myHashTable = new HashTable(6);
myHashTable.set("89893", "Hank");
myHashTable.set("12343", "Sally");
myHashTable.set("72324", "Danny");
myHashTable.set("28990", "Ella");
myHashTable.set("324323", "Wason");

myHashTable.printAll();

呼叫 printAll 可以發現印出來的 hash table 雖然有發生碰撞的情況，但還是可以看到碰撞的兩個物件安然無恙的放在同一個索引值底下 🎉

參考資料:Hashing 基礎介紹