Hash Table（四）實作一個 Hash Table

實作一個 Hash Table

· 3 min read
data structure

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

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

// 內部使用的 hash function
hash1
hash2

// 對外暴露的方法：設定、取得、印出
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 存在 table[index] 中。

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

五、get 取得值

先將傳入的 key 進行 hash 得到 index，搜尋 table[index]，得到該位置的陣列後，搜尋陣列中相同的 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 table
const 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 並不會都只是單純的數字，有各種形態，像是字串，如顏色表：

敘述hexrgb
white#FFFFFFrgb(255, 255, 255)
red#FF0000rgb(255, 0, 0)
magenta#FF00FFrgb(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 並相加

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