Hash Table（二）Hash Function 雜湊法？

在講 hash table 之前，還必須先瞭解 hash function。
簡單來說，hash funtion 就是把一個值換成另外一個值。

在 hash table 中，會把原始資料的 KEY（例如球員編號）經過 hash 過後，得到 index，把資料存在 hash table 相對應的 index 欄位中。

如：20 => !@!2∂∑œ–¡™¡

特性

• hash 的值是不可逆的，無法用 hash 值來推導出 hash 前的值。
• 不同的值經過 hash function 之後也可能會得到相同的 hash 值。

舉例
假設有一個 hash function hashMethod，hash 過的值為 原始值 ÷ 6 的餘數：

const hashMethod = (key) => {
  return key % 6
}

將五個數字 [6, 12, 15, 18, 21]，經過 hash 之後會得到各自的 index [0, 0, 3, 0, 3]。

就可以形成 Hash Table：

[
  [6, 12, 18],
  [],
  [],
  [15, 21],
]

可以看到原始值都不一樣，但 hash 過後，卻出現重複的 0 跟 3，發生了很多衝突（collision），而且無法從 0 跟 3 來推出 hash 前的值是什麼。

衝突（Collision）：當 hashtable 內經過 hash 後的值，有至少兩個以上的值相同，就稱作衝突。

如何處理衝突：同一個 index 需要存放很多的 value，這時就需要以 array 的方式記錄，使 hash table 變成二維陣列，上面的例子即為二維陣列。

Hash Function 的應用

世界上有成千上萬種 Hash Function，應用在不同的情境。

如資料庫存放的密碼，密碼存放到資料庫前，會先經過 Hash Function 處理，將你的密碼改成一串亂碼，如：123456 經過 hash function 處理變成 @dsop™£åß∂¡，這樣做的原因是：

• 對於資料庫管理員來說沒有辦法一眼就記下正確的密碼。
• 且發生資料外洩事件的時候，只要不知道 hash 的方式，駭客也無法存取你真正的密碼。

Hash Funtion 可以對搜尋球員資料的方法有什麼幫助呢？

以上一篇文章中舉的例子來說，Array 中最大的球員編號為 666，代表需要使用 666 個空間，但實際球員只有 13 個。

這時候我們就可以透過 hash function 把球員編號都改成另一個值，一個縮小的值。例如：把最大的編號 666 改成 89，把編號 666 的 Peter 的年薪是 92 萬美元 的資料，存在陣列中索引 89 的地方，這樣陣列的長度就從 666 減少到 89，可以有效地減少使用空間，且同時擁有陣列快速搜尋的便利。

---

舉例幾個 Hash Function

這邊介紹兩個基本的 hash function，但大部分的時候我們不需要深入研究 hash function 的實作方式，我們只需要在意：容不容易發生衝突、時間複雜度是多少這樣的特性，基本上只要看到前面就夠了，所以有興趣再看下去吧！

補充：Load Factor

Load Factor 是一個衡量 hash function 的一項指標。

m: 存放的元素數量
n: hash table 的長度
Load Factor = m / n

• Load Factor 的值越小，衝突的機率越低，越多未使用的空間。
• Load Factor 的值越大，衝突的機率越大，越少未使用的空間。
• 0 < Load Factor < 1

一、Division Method 除法方法

index = Key % hashtable size

這個方法就跟前面提到的例子一樣，把 Key ÷ 雜湊表的長度，取餘數當作 index 存入 Array 中，這邊把 id 當作 Key。hash 後的值 會小於 hash table 的長度，並且大於 0。

0 < hash 後的值 < hash table 的長度

Division Method 除法方法範例

假設有一個 hashtable 的長度為 6，使用 Division Method hash 後，把資料放進 hash table，這樣 hash table 會長怎樣？

原始資料

名字	ID
Mike	11424
Drake	4174
James	6253
Kevin	554

hash 後的值

名字	ID	÷ 6 的餘數
Mike	11424	0
Drake	4171	1
James	6253	1
Kevin	554	2

Hash Table

[
  [{ name: 'Mike', ID: 11424 }],
  [{ name: 'Drake', ID: 4171 }, { name: 'James', ID: 6253 }],
  [[{ name: 'Kevin', ID: 554 }],
  [],
  [],
  [],
]

Division Method 的優缺點

優點

• 速度快，時間複雜度為 O(1)

缺點

• hash table 的大小需盡量遠離 2 的次方值，若選擇 2 的次方值，較容易發生衝突，以下為例，若選擇 8 為 hash table 的大小，就發生了很多的衝突：

[10123, 123125, 5325, 6435, 1235, 12224, 42145].map(node => node % 8)
[3, 5, 5, 3, 3, 0, 1]

二、Multiplication Method (乘法方法)

A = (√5 - 1) / 2
m = hash table 的長度

公式

index = [m(keyA % 1)]

過程

- 先把 key * (√5 - 1) / 2
- 再求 ÷ 1 的餘數，將會得到 0 ~ 1 的值
- 再乘以 m 將會得到介於 0 ~ (m - 1)的值
- Math.floor 去掉小數點
- 得到 0 ~ (m - 1)的值

可以看到這個方法相對除法方法更複雜一些，雖然還是會有衝突，但衝突的機率較 division method 小。

Multiplication Method 除法方法範例

假設有一個 hashtable 的長度為 6，使用 Multiplication Method hash 後，把資料放進 hash table，這樣 hash table 會長怎樣？

原始資料

名字	ID
Mike	11424
Drake	4174
James	6254
Kevin	554

Hash 後的值

名字	ID	hash function（乘法方法） 後的 index
Mike	11424	2
Drake	4171	4
James	6254	1
Kevin	554	2

原始碼

const arr2 = [11424, 4171, 6254, 554]

const A = (Math.sqrt(5) - 1) / 2


arr2.map(node => {
 return Math.floor((node * A) % 1 *  6)
})

// [2, 4, 1, 2]

Hash Table

[
  [],
  [{ name: 'James', ID: 6253 }],
  [{ name: 'Drake', ID: 4171 }, { name: 'Kevin', ID: 554 }]
  [],
  [[{ name: 'Mike', ID: 11424 }],
  [],
]