Hash Table（四）實作一個 Hash Table
實作一個 Hash Table
-6 min read完整程式碼 - GitHub，可以先 clone 下來，或是跟著下面一步一步建立函式。
接下來我們會在 Hash Table 中建立幾個方法，讓我們可以 set and get。
// 內部使用的 hash functionhash1hash2// 對外暴露的方法：設定、取得、印出set,get,printAll,一、初始化 hash table
function hashTable(size) { // 建立一個 hash table 可以存資料 const table = [] // 先根據 hash table 的長度來將建立二維陣列，方便處理衝突的情況。 for (let i = 0; i < size; i++) table.push([])}二、實作第一個 hash 方法：division method
const hash1 = key => key % size三、實作第二個 hash 方法：multiplication method
function hash2(key) { A = (Math.sqrt(5) - 1) / 2 return Math.floor(size * ((key * A) % 1))}四、set 將資料存進 hash table
需傳入 key 與 value，KEY 經過 hash 之後生成 index，把 value 存在 tableindex 中。
function set(key, value) { const index = hash2(key) table[index].push({ key, value })}五、get 取得值
先將傳入的 key 進行 hash 得到 index，搜尋 tableindex，得到該位置的陣列後，搜尋陣列中相同的 key 值，即可得到該 value。
function get(key) { const index = hash2(key) for (let i = 0; i < table[index].length; i++) { if (table[index][i].key === key) return table[index][i] }}六、印出 hash table
function printAll() { console.log(table) }執行程式碼
// 建立一個長度為六的 hash tableconst myHashTable = hashTable(6)// 設定四筆資料myHashTable.set(11424, 'Mike')myHashTable.set(6254, 'James')myHashTable.set(554, 'Kevin')myHashTable.set(4174, 'Drake')// 取得並印出 id 為 4174 的資料console.log(myHashTable.get(4174))// 印出 hash tablemyHashTable.printAll()output
{ key: 4174, value: 'Drake' }[ [], [ { key: 6254, value: 'James' } ], [ { key: 11424, value: 'Mike' }, { key: 554, value: 'Kevin' } ], [], [ { key: 4174, value: 'Drake' } ], []]當 hash function 中的 Key 不是數字
前面實作了簡單的 hash table，但實際中我們的 key 並不會都只是單純的數字，有各種形態，像是字串，如顏色表：
| 敘述 | hex | rgb |
|---|---|---|
| white | #FFFFFF | rgb(255, 255, 255) |
| red | #FF0000 | rgb(255, 0, 0) |
| magenta | #FF00FF | rgb(255, 0, 255) |
不知道大家在撰寫樣式的時候有沒有用過這種寫法：color: white，用敘述的方式讓顏色指定為白色，非常的方便，讓我們不需要去記 hex 的色票。
但瀏覽器是如何知道 color: white，是要將顏色指向 #FFFFFF的呢？
想像一下瀏覽器在資料庫內存了一個 table 記錄對應的： 敘述、hex、rgb。
當我們使用 color: white 的語法，瀏覽器就會去撈資料庫的資料，找到相對應的 hex 是 #FFFFFF。
但是會遇到一個問題，之前都是使用 number 的型態當作 key 來進行 hash，如：id: 571 => id: 5，但在上面的情況中，沒有數字可以直接使用，那我們要用什麼當作 key 來進行 hash 呢？
把字串轉換成數字
我們可以把字串先轉成數字再進行 set，可以採用各種不同的方法
1. 把字串的長度當成 key：
是最簡單的方法，但不是很好的做法因為很容易發生衝突。
2. 將字串轉為 ASCII
把字串個別轉成 ASCII 並且相加。
3. 任何你想得到的組合算法
調換字串的位置，ASCII、相乘、相加、相除 ...等等。
實作第二個方法: 將字串轉為 ASCII
延續上一個 hash table 的程式碼，新增一個 parse 方法。
一、parse 把字串型態的 key 轉換成 ASCII 並相加
function parse(str) { let sum = 0 for (char of str) sum += char.charCodeAt() return sum % size}二、hash function 多判斷型別
若非數字型別則使用 parse 解析為數字，再進行 hash。
function hash2(key) { let parseKey if (typeof key !== 'number') parseKey = parse(key) else parseKey = key A = (Math.sqrt(5) - 1) / 2 return Math.floor(size * ((parseKey * A) % 1))}