Hash Table（四）實作一個 Hash Table

完整程式碼 - GitHub，可以先 clone 下來，或是跟著下面一步一步建立函式。

接下來我們會在 Hash Table 中建立幾個方法，讓我們可以 set and get。

// 內部使用的 hash function
hash1
hash2

// 對外暴露的方法：設定、取得、印出
set,
get,
printAll,

一、初始化 hash table

const hashTable = (size) => {
  // 建立一個 hash table 可以存資料
  let table = [];
  // 先根據 hash table 的長度來將建立二維陣列，方便處理衝突的情況。
  for (let i = 0; i < size; i++) table.push([]);
}

二、實作第一個 hash 方法：division method

const hash1 = key => key % size

三、實作第二個 hash 方法：multiplication method

const hash2 = key => {
  A = (Math.sqrt(5) - 1) / 2
  return Math.floor(size * ((key * A) % 1))
}

四、set 將資料存進 hash table

需傳入 key 與 value，KEY 經過 hash 之後生成 index，把 value 存在 table[index] 中。

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

五、get 取得值

先將傳入的 key 進行 hash 得到 index，搜尋 table[index]，得到該位置的陣列後，搜尋陣列中相同的 key 值，即可得到該 value。

const get = (key) => {
  let index = hash2(key);
  for (let i = 0; i < table[index].length; i++) {
    if (table[index][i].key === key) return table[index][i]
  }
}

六、印出 hash table

const printAll = () => { console.log(table) }

執行程式碼

// 建立一個長度為六的 hash table
let 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 table
myHashTable.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

完整程式碼 - GitHub

延續上一個 hash table 的程式碼，新增一個 parse 方法。

一、parse 把字串型態的 key 轉換成 ASCII 並相加

const parse = (str) => {
  let sum = 0;
  for (char of str) sum += char.charCodeAt();
  return sum % size;
};

二、hash function 多判斷型別

若非數字型別則使用 parse 解析為數字，再進行 hash。

const 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));
};