---
tags: DSA in JavaScript
---
# Ch. 25 Hash Tables

hash table 又稱雜湊表，大致有以下特性：

- 儲存著鍵值對 (key-value pair) 的資料
- 有點像陣列，但不像陣列那樣依序排列
- 在尋找、新增、刪除資料都很快

其實在不少語言內就有實作出這個資料結構，以下列出幾樣常見例子

- Python 的 dictionary
- JavaScript 的 Object
- Java 的 Map

雖然已經有了現成的東西，但雜湊表的概念仍然重要，了解內部運作機制也是學習的重要環節。

## hash (雜湊)

基本的雜湊表，就是使用一個陣列來儲存值 (value)，再用一種雜湊函式，將鍵 (key) 轉換為陣列的索引 (index)，而值就儲存在那個特定的索引內。

但這不只是單純的函式，它必須要符合以下條件：

- 要快 (constant time)
- 不能因為輸入值太長而減緩處理速度
- 所有輸出要平均分布
- 儘量避免重複出現同一種輸出值
- 相同輸入要有相同輸出
- 保持鍵與值的一致性

那接下來就來實作一個 hash function 吧

// 簡單的功能，將字串轉換為某陣列的其中一個位置
function hash (key, arrayLen) {
  let total = 0
  for (const char of key) {
    // map 'a' to 1, 'b' to 2, 'z' to 26, etc.
    // 使用 ASCII code 將其轉換為數字後，取 arrayLen 的餘數
    // 轉換為數字的同時，保持輸出結果在陣列翻圍內
    const value = char.charCodeAt(0) - 96
    total = (total + value) % arrayLen
  }
  return total
}

嗯 ... 這個方式雖然可行，但是時間複雜度為 $O (n)$，因此還有優化的空間。

當然，優化的方法要多少有多少，這邊就先用兩個優化的方法 (可能不如大家預期)。

function hash (key, arrayLen) {
  let total = 0
  // 加入這個奇怪的質數做運算
  const WEIRD_PRIME = 31
  // 然後限縮範圍在 key 的前 100 個字母內
  for (let i = 0; i < Math.min(key.length, 100); i++) {
    const char = key[i]
    const value = char.charCodeAt(0) - 96
    total = (total * WEIRD_PRIME + value) % arrayLen
  }
  return total
}

這邊用了兩個方法，一個是限縮迴圈的範圍，只要輸入值超過一定的長度後，時間複雜度就會固定，另外一種則是非常邪門的作法 --- 參入質數，只要在運算過程，或是雜湊表的陣列長度是質數的話，就可以讓不同輸入值的雜湊結果分散的平均一點。

## Collision
就算是設計縝密的雜湊函式，依然有機率出現重複的雜湊值，這種情況就是 collision (碰撞)。
以下介紹兩種處理碰撞的基本方法：

### separate chaining

> 誰說雜湊表裡面只能放值？

以這種方式處理碰撞的雜湊表，索引內儲存的不是數值，而是一個陣列，或是其他資料結構。當該索引已經有其他數值時，新數值可以直接加進該索引的資料結構裡面。


### linear probing

> 此處不留爺，自有留爺處

以這種方式處理碰撞時，新數值會不斷移動至下一個索引，直到加進空白索引為止。


## 實作

雖然 JavaScript 已經有一個 object 型別，但我們也可以試著做一個自己的雜湊表看看，當然就是做個基本款，也不會去實作錯誤處理之類詳細的部份，key 限定使用字串格式。

### 骨幹

除了基礎的空陣列外，也把剛才實作的雜湊函式也一起加進來，底線是表明這個方法/屬性是私有的，原則上無法被外界存取，這邊是使用 separate chaining 處理碰撞。

class HashTable {
  // 這邊為 size 加上一個神奇質數作為預設值
  constructor(size = 17) {
    // 產生一個 size * 0 的二維陣列
    this.keyMap = Array.from({ length: size }, () => [])
  }

  _hash (key) {
    let total = 0
    const WEIRD_PRIME = 31
    for (let i = 0; i < Math.min(key.length, 100); i++) {
      const char = key[i]
      // map 'a' to 1, 'b' to 2, 'z' to 26, etc.
      const value = char.charCodeAt(0) - 96
      total = (total * WEIRD_PRIME + value) % this.keyMap.length
    }
    return total
  }
}

### `set(key,value)`

新增一個鍵值對放進雜湊表內。
這邊暫時不處理相同 key 的情況，以常規來說，這樣會覆蓋上一個 value。

set (key, value) {
  const hash = this._hash(key)
  this.keyMap[hash].push([key, value])
}

### `get(key)`

搜尋雜湊表內鍵值為 key 的鍵值對，找不到鍵值對則回傳 undefined。

get (key) {
  const index = this._hash(key)
  if (this.keyMap[index]) {
    for (let i = 0; i < this.keyMap[index].length; i++) {
      if (this.keyMap[index][i][0] === key) {
        return this.keyMap[index][i]
      }
    }
  }
}

### `values()`

列出雜湊表內所有不重複的數值 (values)，以陣列表示。

values () {
  const valuesArr = []
  // 遍歷整個二維陣列
  for (let i = 0; i < this.keyMap.length; i++) {
    if (this.keyMap[i].length) {
      for (let j = 0; j < this.keyMap[i].length; j++) {
        // 檢查是否有重複元素，不重複就加進來，第三個中括號的 [1] 代表 value 的部份
        // [0] 代表 key 的部份，會在下方看到
        if (!valuesArr.includes(this.keyMap[i][j][1])) {
          valuesArr.push(this.keyMap[i][j][1])
        }
      }
    }
  }
  return valuesArr
}

### `keys()`

列出雜湊表內所有鍵值 (keys)，並以陣列表示。

keys () {
  const keysArr = []
  for (let i = 0; i < this.keyMap.length; i++) {
    if (this.keyMap[i].length) {
      for (let j = 0; j < this.keyMap[i].length; j++) {
        if (!keysArr.includes(this.keyMap[i][j][0])) {
          keysArr.push(this.keyMap[i][j][0])
        }
      }
    }
  }
  return keysArr
}

## 時間複雜度

雜湊表的時間複雜度在新增、刪除、存取時平均都是 $O(1)$，若資料沒有排序的需求，雜湊表是個不錯的選擇，~~但能不做就不用自己做，大概知道原理就行叻~~。