[資料結構] Hash Table

keywords: data structure

此系列筆記主要依照 [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub 的課程脈絡加以整理，但部分程式碼是消化後以自己較易理解的方式重新撰寫，因此和原課程內容有些出入。

觀念

• Hash Table 本身是一個陣列，裡面的每一個元素都是帶有 key-value 的物件，稱作 Buckets。
• 透過自訂的 hash 函式，可以決定新增的資料要放在 Hash Table 中的哪個位置。
• 當有不同的內容放到相同編號的 Buckets 時，會發生所謂的 collision，這時候相同 Bucket 內的資料，會透過 Linked List 的方式串接在一起。
• 當 insert 了相同 key 的資料時，會有更新的效果。
• 其中會包含的方法有：
  • hash
  • insert
  • get, retrieveAll

Big O Notation

• Hash Table 常用在儲存使用者的 Email、使用者資料。
• 缺點：除非在同一個 bucket 內，否則資料（Node）之間不會彼此參照。

Constant Time - O(1)

• 插入資料
• 搜尋資料

Sample Code

data-structures-in-javascript @ PJCHENder Github

Started Template

// size 會決定在 hashTable 中有多少 buckets
function HashTable(size) {
  this.buckets = Array(size);
  this.numberBuckets = this.buckets.length;
}

// 每一個 key-value pair 稱作 Node
function HashNode({ key, value, next = null }) {
  this.key = key;
  this.value = value;
  this.next = next;
}

// 用來產生一個數值，此數值不能超過 buckets 的 size
HashTable.prototype.hash = function hash(key) {/* ... */};

// 用來新增 Node 到 HashTable 中
// 若該 bucket 已經有資料，則透過 Linked List 的概念，放到 next 中
// 若該 key 已經存在，則進行更新
HashTable.prototype.insert = function insert({ key, value }) {/* ... */};

// 根據 key 取得 value
HashTable.prototype.get = function get(key) {/* ... */};

// 取得所有 Buckets 中的 Node
HashTable.prototype.retrieveAll = function retrieveAll() {/* ... */};

module.exports = HashTable;

參考

• [Udemy] Learning Data Structures in JavaScript from Scratch by Eric Traub