Hash Table
Bảng băm — vũ khí O(1)

5.1 Tại sao cần Hash Table?

Hãy giải bài toán: "Cho mảng nums và target, tìm 2 phần tử có tổng = target." Đây là LeetCode 1, nổi tiếng nhất.

// Cách 1: Brute force — O(n²)
function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
}

// Cách 2: Hash Map — O(n)
function twoSum(nums, target) {
  const map = new Map();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (map.has(need)) return [map.get(need), i];
    map.set(nums[i], i);
  }
}

Cách 2 chạy nhanh gấp ~50,000 lần với n = 100,000. Sự khác biệt ấy đến từ Hash Map: map.has() và map.get() đều O(1) trung bình.

Hash Table là gì?

Hash Table (bảng băm) là cấu trúc lưu cặp (key, value) sao cho thao tác get/set/has/delete có độ phức tạp O(1) trung bình.

Ý tưởng: dùng một hàm băm (hash function) biến key bất kỳ thành chỉ số mảng:

key "apple" ──hash()──→ 73   ──mod 10──→ 3
key "banana" ──hash()──→ 124  ──mod 10──→ 4

bucket[]: [_, _, _, "apple→1", "banana→3", _, _, _, _, _]

5.2 Hash function — trái tim của hash table

Một hash function tốt có 4 tính chất:

1. Deterministic: cùng key → luôn cho cùng hash
2. Uniform distribution: các key khác nhau phân bố đều khắp các bucket
3. Fast to compute: tính nhanh, ưu tiên O(1) hoặc O(độ dài key)
4. Avalanche effect: thay đổi 1 bit của key làm thay đổi mạnh hash

Ví dụ hash function đơn giản cho string

// Hash đơn giản — chỉ để minh hoạ, không nên dùng production
function badHash(str) {
  let sum = 0;
  for (const ch of str) sum += ch.charCodeAt(0);
  return sum;
}
// Vấn đề: "abc" và "cba" cho cùng hash → quá nhiều collision

// Polynomial hash — tốt hơn nhiều
function polyHash(str, mod = 1e9 + 7) {
  let h = 0;
  const p = 31;  // prime
  for (let i = 0; i < str.length; i++) {
    h = (h * p + str.charCodeAt(i)) % mod;
  }
  return h;
}
// "abc" và "cba" cho hash khác nhau

// FNV-1a — production-grade, dùng trong nhiều thư viện
function fnv1a(str) {
  let hash = 2166136261;
  for (let i = 0; i < str.length; i++) {
    hash ^= str.charCodeAt(i);
    hash = (hash * 16777619) >>> 0;  // unsigned 32-bit
  }
  return hash;
}

Hash cho object

Trong các ngôn ngữ như Java, Python, mỗi object có method hashCode(). Trong JS, Map dùng cơ chế nội bộ của V8 (chi tiết bên trong là engine implementation).

const obj = {};
const key1 = {a: 1};
const key2 = {b: 2};
obj[key1] = "hello";
obj[key2] = "world";
console.log(obj[key1]);  // "world" (!) — vì key1.toString() = "[object Object]" = key2.toString()

5.3 Collision và 2 chiến lược xử lý

Vì số lượng key tiềm năng là vô hạn nhưng số bucket là hữu hạn, theo nguyên lý ngăn kéo (pigeonhole), sẽ có 2 key khác nhau cho cùng hash → collision.

5.3.1 Separate Chaining — mỗi bucket là 1 linked list

bucket 0: → null
bucket 1: → ("apple", 1) → ("apricot", 8) → null  (cùng hash)
bucket 2: → ("banana", 3) → null
bucket 3: → null
bucket 4: → ("cherry", 5) → null

• Insert: tìm bucket, append vào list — O(1) trung bình
• Search: tìm bucket, duyệt list, so sánh key — O(load factor) trung bình
• Delete: tương tự search

Java HashMap, C++ unordered_map, JS Map đều dùng (biến thể) chaining.

5.3.2 Open Addressing — không dùng linked list

Khi collision, tìm bucket trống khác theo một quy tắc (probing).

• Linear probing: thử bucket (h+1, h+2, h+3, ...) mod N
• Quadratic probing: thử (h+1, h+4, h+9, ...) — giảm "clustering"
• Double hashing: dùng hash function thứ hai để xác định bước nhảy

Insert "apple" → hash=3 → bucket[3]
Insert "apricot" → hash=3 → bucket[3] đầy → bucket[4] (linear probe)
Insert "almond" → hash=3 → bucket[3,4] đầy → bucket[5]

Python's dict dùng open addressing (vì cache-friendly). Java's HashMap dùng chaining + chuyển sang Red-Black Tree khi list dài > 8 (Java 8+). Rust's HashMap dùng SwissTable (open addressing với SIMD probing).

5.4 Load Factor & Rehashing

Load factor = số phần tử / số bucket. Nó đo độ "chật" của hash table.

• Load factor thấp (e.g. 0.3): nhiều bucket trống → tốn memory nhưng ít collision
• Load factor cao (e.g. 0.9): tiết kiệm memory nhưng nhiều collision → chậm

Khi load factor vượt ngưỡng (thường 0.75 cho chaining, 0.5 cho open addressing), hash table phải rehash:

1. Cấp phát mảng mới gấp đôi kích thước
2. Tính lại hash cho mỗi key (vì chỉ số bucket thay đổi)
3. Insert lại vào mảng mới

Rehash tốn O(n), nhưng nhờ amortized analysis, insert vẫn là O(1) trung bình.

// Pseudo-code rehashing
function rehash() {
  const oldBuckets = this.buckets;
  this.capacity *= 2;
  this.buckets = new Array(this.capacity).fill(null).map(() => []);
  this.size = 0;
  for (const bucket of oldBuckets) {
    for (const [k, v] of bucket) {
      this.set(k, v);  // tính hash mới với capacity mới
    }
  }
}

5.5 Big-O của Hash Table

5.6 Object vs Map vs Set trong JavaScript

Trong JS có 3 cấu trúc lookup. Biết chọn đúng là quan trọng.

5.6.1 Object thường — {}

const obj = {};
obj.name = "Alice";
obj["age"] = 25;
obj[42] = true;        // key tự động convert sang "42"
console.log(Object.keys(obj));  // ["42", "name", "age"]

Đặc điểm:

• Key tự động convert sang string hoặc Symbol
• Có prototype chain (kế thừa methods như toString) → có thể nhầm lẫn
• Khi nói "hash table" trong JS, đây thường là Object (trước ES6)
• Performance: V8 tối ưu nhiều cho object có shape cố định (hidden classes)

5.6.2 Map — ES6 hash map "đúng nghĩa"

const map = new Map();
map.set("name", "Alice");
map.set(42, true);
map.set({a: 1}, "object key!");  // object cũng làm key được
map.set(NaN, "even NaN!");        // NaN cũng làm key được

console.log(map.get("name"));   // "Alice"
console.log(map.size);           // 4
console.log([...map.keys()]);    // ["name", 42, {a:1}, NaN]

Đặc điểm:

• Key có thể là kiểu bất kỳ (object, NaN, function...)
• Giữ thứ tự insertion khi iterate
• Có method tiện lợi: size, has, delete, clear
• Iterable trực tiếp với for...of

5.6.3 Set — chỉ chứa value, không có key

const set = new Set([1, 2, 3, 2, 1]);
console.log(set);          // Set(3) {1, 2, 3} — auto dedupe
set.add(4);
set.has(2);                // true
set.delete(1);
console.log(set.size);     // 3

// Convert array → set → array để loại trùng
const unique = [...new Set([1, 2, 2, 3, 3, 3])];  // [1, 2, 3]

So sánh khi nào dùng

WeakMap & WeakSet

WeakMap/WeakSet: chỉ chấp nhận object làm key, và không giữ reference → khi không còn ai khác giữ key, GC có thể thu hồi. Dùng cho metadata, caching gắn với object.

5.7 Tự cài đặt Hash Map (Separate Chaining)

class HashMap {
  constructor(capacity = 16, loadFactor = 0.75) {
    this.capacity = capacity;
    this.loadFactor = loadFactor;
    this.size = 0;
    this.buckets = Array.from({length: capacity}, () => []);
  }

  // Hash function đơn giản cho string
  _hash(key) {
    const str = String(key);
    let h = 0;
    for (let i = 0; i < str.length; i++) {
      h = (h * 31 + str.charCodeAt(i)) >>> 0;  // unsigned 32-bit
    }
    return h % this.capacity;
  }

  set(key, value) {
    const idx = this._hash(key);
    const bucket = this.buckets[idx];
    for (const pair of bucket) {
      if (pair[0] === key) {
        pair[1] = value;  // update existing
        return;
      }
    }
    bucket.push([key, value]);
    this.size++;
    if (this.size / this.capacity > this.loadFactor) this._rehash();
  }

  get(key) {
    const idx = this._hash(key);
    const bucket = this.buckets[idx];
    for (const [k, v] of bucket) {
      if (k === key) return v;
    }
    return undefined;
  }

  has(key) {
    return this.get(key) !== undefined;
  }

  delete(key) {
    const idx = this._hash(key);
    const bucket = this.buckets[idx];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        this.size--;
        return true;
      }
    }
    return false;
  }

  _rehash() {
    const oldBuckets = this.buckets;
    this.capacity *= 2;
    this.buckets = Array.from({length: this.capacity}, () => []);
    this.size = 0;
    for (const bucket of oldBuckets) {
      for (const [k, v] of bucket) this.set(k, v);
    }
  }

  *entries() {
    for (const bucket of this.buckets) {
      for (const pair of bucket) yield pair;
    }
  }
}

// Test
const m = new HashMap();
m.set("apple", 1);
m.set("banana", 2);
m.set("apple", 3);  // update
console.log(m.get("apple"));   // 3
console.log(m.size);            // 2

5.8 Hash Table Patterns kinh điển

5.8.1 Counting / Frequency Map

// Đếm tần suất từng phần tử
function countFreq(arr) {
  const freq = new Map();
  for (const x of arr) freq.set(x, (freq.get(x) || 0) + 1);
  return freq;
}

// Bài: Most Frequent Element
function mostFrequent(arr) {
  const freq = countFreq(arr);
  let best = null, max = 0;
  for (const [k, v] of freq) {
    if (v > max) { max = v; best = k; }
  }
  return best;
}

5.8.2 Two Sum & biến thể

// Đã thấy ở 5.1, đây là biến thể:
// Subarray Sum Equals K — đếm số subarray có tổng = k
function subarraySum(nums, k) {
  const map = new Map([[0, 1]]);
  let sum = 0, count = 0;
  for (const x of nums) {
    sum += x;
    if (map.has(sum - k)) count += map.get(sum - k);
    map.set(sum, (map.get(sum) || 0) + 1);
  }
  return count;
}

5.8.3 Group Anagrams

// Cho mảng strings, group các từ là anagram của nhau
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = s.split('').sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

// Input:  ["eat","tea","tan","ate","nat","bat"]
// Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]

5.8.4 Longest Consecutive Sequence — KINH ĐIỂN

// Tìm độ dài chuỗi liên tiếp dài nhất trong mảng (không cần sort)
// O(n) bằng Hash Set
function longestConsecutive(nums) {
  const set = new Set(nums);
  let longest = 0;
  for (const n of set) {
    // Chỉ bắt đầu đếm từ phần tử đầu chuỗi (n-1 không có trong set)
    if (!set.has(n - 1)) {
      let len = 1;
      while (set.has(n + len)) len++;
      longest = Math.max(longest, len);
    }
  }
  return longest;
}

// Input: [100, 4, 200, 1, 3, 2]
// Chuỗi 1-2-3-4 dài nhất = 4
// Output: 4

Tại sao O(n)? Mỗi phần tử được duyệt trong inner while chỉ 1 lần (vì ta chỉ bắt đầu từ "đầu chuỗi"). Tổng: O(n).

5.8.5 LRU Cache — Hash Map + Doubly Linked List

// LRU Cache với get/put O(1) — bài LeetCode 146 cực kinh điển
class LRUCache {
  constructor(capacity) {
    this.cap = capacity;
    this.map = new Map();  // key → node
    // Doubly linked list với head/tail dummy
    this.head = {};
    this.tail = {};
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  _remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  _addToFront(node) {
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next.prev = node;
    this.head.next = node;
  }

  get(key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this._remove(node);
    this._addToFront(node);
    return node.val;
  }

  put(key, val) {
    if (this.map.has(key)) {
      const node = this.map.get(key);
      node.val = val;
      this._remove(node);
      this._addToFront(node);
    } else {
      const node = {key, val};
      this.map.set(key, node);
      this._addToFront(node);
      if (this.map.size > this.cap) {
        const lru = this.tail.prev;
        this._remove(lru);
        this.map.delete(lru.key);
      }
    }
  }
}

Lưu ý: JS Map giữ thứ tự insert, nên LRU Cache có thể cài đơn giản hơn bằng cách delete + set lại để "đẩy" key lên cuối Map. Nhưng cách dùng doubly linked list là cách "cổ điển" hỏi trong phỏng vấn.

Bài tập

Tổng kết chương 5

• ✅ Hash Table: O(1) trung bình cho get/set/has/delete
• ✅ Hash function biến key thành chỉ số bucket; cần fast + uniform + deterministic
• ✅ 2 cách xử lý collision: Separate Chaining (linked list) vs Open Addressing (probing)
• ✅ Load factor > ngưỡng → rehash O(n) nhưng amortized O(1)
• ✅ JS có 3 lựa chọn: Object (key string), Map (key bất kỳ + giữ thứ tự), Set (chỉ value)
• ✅ Patterns vàng: Frequency Map, Two Sum, Group Anagrams, Longest Consecutive, LRU Cache
• ✅ LRU Cache = Hash Map + Doubly Linked List → bài phỏng vấn cực hay