2020年5月26日

[資料結構] Hash Table

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

觀念

  • 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

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;

參考

0 意見:

張貼留言