Data Structure - Hash Table

Hash Table 雜湊表

Hash Table，也可稱作 Hash Map，是 Dictionary 類別中雜湊表的一種實作。實作的思路是：當要把資料放到雜湊表時，先給定一個 key 和存放的 value，並將 key 的每個字元轉換成 ASCII Code 或 Unicode Code 並相加，這個相加的值即是 hash 鍵值，在 table 陣列上對應到存放的 value。

優點：

insert、lookup、delete： 使用 key 鍵值可以直接透過 hash function 找到 value 所在，如果不考慮 collisions，以上的操作時間複雜度為 O(n)

缺點：

• 儲存不按照順序，有些按照順序的操作被限制，例如想要處理有時間順序的 data，或是希望儲存的 data 可以被排序。

  • Python 中例外，Python 默認將字典排序了，因此，在該語言中，Array（Python中的List）和Hash Table（Python中的Dict）之間的區別較小：https://softwaremaniacs.org/blog/2020/02/05/dicts-ordered/en/

• 因為有 collisions 問題，必須分配大量內存才能有效工作。

使用時機 :

• 在搜尋引擎可以用來縮小搜尋範圍，例如在搜尋的時候輸入關鍵字，我們可以把這個關鍵字傳進 hash function，然後 hash function 就可以指出這個關鍵字對應到的桶子，這時候再到這個桶子裡搜尋網頁就可以了。

Javascript Hash Table：

建立 class

class HashTable {
  constructor(size){
    this.data = new Array(size);
  }
  //簡易的雜湊
  _hash(key) {
    let hash = 0;
    for (let i =0; i < key.length; i++){
        hash = (hash + key.charCodeAt(i) * i) % this.data.length
    }
    return hash;
  }
}

set

class HashTable {
  //...以上省略
  set(key, value) {
    let address = this._hash(key);
    if (!this.data[address]) {
      this.data[address] = [];
    }
    this.data[address].push([key, value]);
    return this.data;
  }
}

get

class HashTable {
  //...以上省略
  get(key){
    const address = this._hash(key);
    const currentBucket = this.data[address]
    if (currentBucket) {
      for(let i = 0; i < currentBucket.length; i++){
        if(currentBucket[i][0] === key) {
          return currentBucket[i][1]
        }
      }
    }
    return undefined;
  }
}