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;
0 意見:
張貼留言