Skip to main content

[資料結構] Hash Table

在 JavaScript 中,可以用物件(object)來代表 Hash Table 的資料結構。

在 JavaScript 中還有 Map,Map 和 Object 有一個很大的差別在於,物件的 key 只能是 string(若是其他的型別也會被轉成 string),但 Map 的 key 則可以是其他的型別;另外 Map 會抱持資料輸入時的順序,但物件是沒有順序性的。

在 JavaScript 中還有 Set,它只會用來保存 key 而沒有 value。

觀念#

Imgur

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

參考#

Last updated on