[資料結構] Hash Table
在 JavaScript 中，可以用物件（object）來代表 Hash Table 的資料結構。
在 JavaScript 中還有 Map，Map 和 Object 有一個很大的差別在於，物件的 key 只能是 string（若是其他的型別也會被轉成 string），但 Map 的 key 則可以是其他的型別；另外 Map 會抱持資料輸入時的順序，但物件是沒有順序性的。
在 JavaScript 中還有 Set，它只會用來保存 key 而沒有 value。
觀念
- Hash Table 本身是一個陣列，裡面的每一個元素都是帶有 key-value 的物件，稱作 Buckets。
- 透過自訂的
hash函式，可以決定新增的資料要放在 Hash Table 中的哪個位置。 - 當有不同的內容放到相同編號的 Buckets 時，會發生所謂的 collision，這時候相同 Bucket 內的資料，會透過 Linked List 的方式串接在一起。
- 當 insert 了相同 key 的資料時，會有更新的效果。
- 其中會包含的方法有：
hashinsertget,retrieveAll
Hash Function
Hash function 指的是
- 將 input 轉成固定長度的函式
- idempotent：相同的 input 會得到相同的 output
- 它是單向的，透過 output 無法反推 input。
Hash Collision 是指 hash function 在「不同的 input」下，得到了相同的「output」，導致儲存到同一個記憶體位置上。
由於 Hash Table 的 size 並不是無限擴展的，在有限的記憶體空間下，一定會有 hash collision 發生的可能。若有 hash collision 發生的話，lookup 的時間複雜度就可能會變成 O(n)。
Time Complexity
- Insert：O(1)
- Lookup: O(1)，但若 有 hash collision 發生，lookup 的時間複雜度就可能會變成 O(n)
- Delete: O(1)
- Search: O(1)：能夠透過 hash function 直接找出該 key 對應的 address
- Hash Table 常用在儲存使用者的 Email、使用者資料。
- 缺點：除非在同一個 bucket 內，否則資料（Node）之間不會彼此參照。
Sample Code
實作 Hash Table
- 從實作中可以看到
keys()是很耗時的操作 - 同理，
for ... in這類的迴圈也是相對耗時的
// https://www.udemy.com/course/master-the-coding-interview-data-structures-algorithms/
class HashTable {
data: any[];
constructor(size: number) {
this.data = new Array(size);
}
private hash(key: string) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = (hash + key.charCodeAt(i) * i) % this.data.length;
}
return hash;
}
set(key: string, value: any) {
const address = this.hash(key); // 算出要儲存的位址
const bucket = this.data[address]; // 取出要保存的 bucket
// 如果 bucket 不存在，則建立空陣列
if (bucket === undefined) {
this.data[address] = [];
}
this.data[address].push([key, value]);
return this.data;
}
get(key: string): any {
const address = this.hash(key); // 算出要資料保存的位址
const bucket = this.data[address]; // 取出 bucket
// 如果沒有 hash collision 則是 O(1)，否則會是 O(n)
if (bucket) {
for (let i = 0; i < bucket.length; i++) {
const [_key, value] = bucket[i];
if (_key === key) {
return value;
}
}
}
return undefined;
}
// 取得所有 key，O(n^2)
keys() {
let keys = [];
for (let i = 0; i < this.data.length; i++) {
const bucket = this.data[i];
if (bucket) {
for (let j = 0; j < bucket.length; j++) {
const [key] = bucket[j];
keys.push(key);
}
}
}
return keys;
}
}
const myHashTable = new HashTable(2);
myHashTable.set('grapes', 10000);
myHashTable.set('apples', 54);
myHashTable.set('oranges', 2);
const a = myHashTable.get('apples');
console.log(a);
const keys = myHashTable.keys();
console.log(keys);
Started Template
data-structures-in-javascript @ PJCHENder Github
// https://www.udemy.com/course/learning-data-structures-in-javascript-from-scratch/
// 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;
Questions
找出陣列中第一個重複的元素
firstRecurringCharacterWithObject([2, 5, 1, 2, 3, 5, 1, 2, 4]); // 2
firstRecurringCharacterWithObject([2, 1, 1, 2, 3, 5, 1, 2, 4]); // 1
firstRecurringCharacterWithObject([0, 1, 0, 2, 3, 5, 1, 2, 4]); // 0
firstRecurringCharacterWithObject([...Array(1000).keys()]); // undefined
想法一：使用 Object
- 使用 hashTable 來看該元素是否已經出現過
- 有一個 edge case 要考慮是 value 為 0 時，
if (0)會變成false
interface Dictionary<T> {
[key: string]: T;
}
const firstRecurringCharacterWithObject = (
arr: number[]
): number | undefined => {
const hashTable: Dictionary<number> = {};
for (let i = 0; i < arr.length; i++) {
const value = hashTable[arr[i]];
if (value !== undefined) {
return value;
} else {
hashTable[arr[i]] = arr[i];
}
}
return undefined;
};
firstRecurringCharacterWithObject([2, 5, 1, 2, 3, 5, 1, 2, 4]); // 2
firstRecurringCharacterWithObject([2, 1, 1, 2, 3, 5, 1, 2, 4]); // 1
firstRecurringCharacterWithObject([...Array(1000).keys()]); // undefined
想法二：使用 Map
const firstRecurringCharacterWithMap = (arr: number[]): number | undefined => {
const hashTable = new Map();
for (let i = 0; i < arr.length; i++) {
const value = hashTable.get(arr[i]);
if (value !== undefined) {
return value;
} else {
hashTable.set(arr[i], arr[i]);
}
}
return undefined;
};
firstRecurringCharacterWithMap([2, 5, 1, 2, 3, 5, 1, 2, 4]); // 2
firstRecurringCharacterWithMap([2, 1, 1, 2, 3, 5, 1, 2, 4]); // 1
firstRecurringCharacterWithMap([...Array(1000).keys()]); // undefined