Giới thiệu

Hash table được sử dụng để lưu cặp key-value, giống như array nhưng key không được sắp xếp. Cho phép truy xuất giá trị nhanh O(1)

Hash table sẽ dùng 1 hàm băm để chuyển đổi key thành một chỉ số trong mảng

Cấu trúc của hash table:

• Hash function: chuyển key thành một số nguyên index .
• Array (bucket array): Lưu trữ giá trị tại bị trí được hash.
• Collision handling: Xử lý trường hợp nhiều key trả về một index :
  • Chaining: nếu hash bị trùng index thì ghi đè lên vị trí index đó, tại vị trí index đó lưu nhiều cặp [key, value]
  • Linear probing: nếu index bị trùng sẽ ghi ở vị trí trống kế tiếp.

Khởi tạo

class HashTable { buckets; size: number; constructor(size = 4) { this.buckets = new Array(size); this.size = size; } _hash(key) { let total = 0; const PRIME = 31; for (let i = 0; i < Math.min(key.length, 100); i++) { const char = key[i]; const value = char.charCodeAt(0) - 96; total = (total * PRIME + value) % this.size; } return total; }
}

Khởi tạo các method

set

 set(key, value) { const index = this._hash(key); if (!this.buckets[index]) { this.buckets[index] = []; } this.buckets[index].push([key, value]); }

get

get(key) { const index = this._hash(key); const bucket = this.buckets[index]; if (bucket) { for (let pair of bucket) { if (pair[0] === key) { return pair[1]; } } } return undefined; }

keys

 keys() { const keys = []; for (let bucket of this.buckets) { if (bucket) { for (let pair of bucket) { keys.push(pair[0]); } } } return keys; }

values

 values() { const values = []; for (let bucket of this.buckets) { if (bucket) { for (let pair of bucket) { values.push(pair[1]); } } } return values; }

Độ phức tạp