Bài 10: Hash Table & Va Chạm — Linear/Quadratic Probing, Chaining

Ở Bài 9 chúng ta thấy bộ cấp phát bộ nhớ phải dò tuyến tính qua free list để tìm một khối trống — O(n) trong trường hợp xấu. Bài này giới thiệu một cấu trúc dữ liệu giải quyết một bài toán khác nhưng cùng họ: tra cứu một giá trị theo khoá trong thời gian trung bình O(1), bất kể tập dữ liệu lớn tới đâu. Đó chính là Hash Table — nền tảng của Object/Map trong JavaScript, dict trong Python, HashMap trong Java hay std::unordered_map trong C++.

1. Vì sao cần Hash Table? Từ O(n) đến O(1) trung bình

Nếu lưu các cặp khoá-giá trị trong một mảng hoặc danh sách liên kết thô, việc tìm một khoá cụ thể buộc phải duyệt qua từng phần tử — O(n). Cây tìm kiếm cân bằng như AVL/Red-Black (xem Bài 1) cải thiện xuống O(log n) nhờ so sánh có thứ tự. Hash Table đi theo hướng hoàn toàn khác: thay vì so sánh khoá với nhau, nó tính toán trực tiếp vị trí của khoá trong một mảng — biến bài toán tìm kiếm thành bài toán truy cập chỉ số mảng, vốn dĩ đã là O(1).

2. Hàm băm (Hash Function): Biến khoá bất kỳ thành chỉ số mảng

Một hàm băm h(key) nhận một khoá (số, chuỗi, object…) và trả về một số nguyên trong khoảng [0, m) — với m là kích thước mảng lưu trữ (gọi là bucket array). Với khoá là số nguyên, cách đơn giản nhất là phép chia lấy dư:

// Hàm băm đơn giản nhất cho khoá số nguyên
function hashInt(key, tableSize) {
  return key % tableSize; // luôn nằm trong [0, tableSize)
}

// Với khoá chuỗi, phải "gộp" từng ký tự thành 1 số trước khi mod.
// Polynomial rolling hash — nhân dồn theo một số nguyên tố p:
//   h(s) = (s[0]*p^0 + s[1]*p^1 + ... + s[n-1]*p^(n-1)) mod m
function hashString(str, tableSize) {
  const p = 31; // số nguyên tố lẻ, giảm va chạm cho chuỗi tiếng Anh
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    hash = (hash * p + str.charCodeAt(i)) % tableSize;
  }
  return hash;
}

Một hàm băm tốt cần 3 tính chất: xác định (cùng khoá luôn ra cùng kết quả), tính nhanh (O(1) hoặc O(độ dài khoá)), và quan trọng nhất — phân phối đều các khoá khắp [0, m), tránh dồn cụm vào một vài chỉ số.

3. Va Chạm (Collision) Là Điều Không Thể Tránh Khỏi

Vì miền giá trị khoá gần như vô hạn còn m bucket là hữu hạn, theo nguyên lý chuồng bồ câu (pigeonhole principle), chắc chắn tồn tại 2 khoá khác nhau cùng băm ra một chỉ số — gọi là va chạm (collision). Tệ hơn, va chạm xảy ra sớm hơn nhiều so với trực giác, tương tự nghịch lý ngày sinh nhật: với m{' '} bucket và chèn ngẫu nhiên n khoá, xác suất không có va chạm nào xấp xỉ:

$$P(\text{no collision}) \approx e^{-n^2 / 2m}$$

4. Giải pháp 1: Separate Chaining (Nối Danh Sách Liên Kết)

Cách trực quan nhất: mỗi bucket không lưu trực tiếp 1 khoá, mà lưu một danh sách liên kết chứa tất cả khoá cùng băm về chỉ số đó. Khi va chạm xảy ra, chỉ cần nối thêm phần tử mới vào danh sách của bucket tương ứng — không ảnh hưởng tới bucket khác:

class ChainingHashTable {
  constructor(size) {
    this.size = size;
    this.buckets = Array.from({ length: size }, () => []); // mỗi bucket = 1 mảng (chain)
  }
  insert(key, value) {
    const i = key % this.size;
    const chain = this.buckets[i];
    const existing = chain.find((entry) => entry.key === key);
    if (existing) existing.value = value; // cập nhật nếu khoá đã tồn tại
    else chain.push({ key, value });       // O(1) amortized — nối cuối chain
  }
  search(key) {
    const chain = this.buckets[key % this.size];
    const entry = chain.find((e) => e.key === key);
    return entry ? entry.value : undefined; // O(1) trung bình, O(chain.length) xấu nhất
  }
}

Ưu điểm: cài đặt đơn giản, không bao giờ "đầy bảng" (chain có thể phình dài vô hạn), xoá phần tử dễ dàng. Nhược điểm: mỗi bucket cần thêm bộ nhớ cho con trỏ/mảng, và hiệu năng bộ nhớ đệm (cache locality) kém hơn vì các phần tử trong chain thường nằm rải rác trên heap.

5. Giải pháp 2: Open Addressing — Linear Probing

Ngược với chaining, Open Addressing không dùng bộ nhớ phụ — toàn bộ dữ liệu nằm ngay trong mảng bucket. Khi vị trí h(key) đã bị chiếm, ta dò (probe) sang các vị trí khác theo một quy tắc cố định cho tới khi tìm được chỗ trống. Linear Probing là quy tắc đơn giản nhất: thử lần lượt từng ô kế tiếp, với i = 0, 1, 2, … tăng dần cho tới khi tìm được chỗ trống:

$$\text{slot}_i = (h(key) + i) \bmod m$$

function insertLinear(slots, key) {
  const m = slots.length;
  const start = key % m;
  for (let i = 0; i < m; i++) {
    const idx = (start + i) % m; // dò tuần tự, quay vòng khi hết mảng
    if (slots[idx] === null || slots[idx] === TOMBSTONE) {
      slots[idx] = key;
      return idx;
    }
    if (slots[idx] === key) return idx; // khoá đã tồn tại
  }
  return -1; // bảng đầy — không tìm được chỗ trống
}

6. Quadratic Probing & Double Hashing

Để giảm clustering, Quadratic Probing nhảy theo bước bình phương thay vì bước tuyến tính:

$$\text{slot}_i = \bigl(h(key) + i^2\bigr) \bmod m$$

Bước nhảy càng xa càng lớn dần, phá vỡ các cụm dài. Một hướng tinh vi hơn nữa là Double Hashing — dùng một hàm băm thứ hai h₂(key) để quyết định bước nhảy, khiến mỗi khoá có một "quỹ đạo dò" gần như riêng biệt:

$$\text{slot}_i = \bigl(h_1(key) + i \cdot h_2(key)\bigr) \bmod m$$

function insertQuadratic(slots, key) {
  const m = slots.length;
  const start = key % m;
  for (let i = 0; i < m; i++) {
    const idx = (start + i * i) % m; // bước nhảy tăng theo i^2: 0, 1, 4, 9, 16...
    if (slots[idx] === null || slots[idx] === TOMBSTONE) {
      slots[idx] = key;
      return idx;
    }
    if (slots[idx] === key) return idx;
  }
  return -1; // có thể "đầy giả" — xem cạm bẫy bên dưới
}

7. Xoá Phần Tử Trong Open Addressing: Kỹ Thuật Tombstone

Xoá một khoá trong Open Addressing phức tạp hơn tưởng tượng. Nếu chỉ đơn giản đặt ô đó về null, mọi thao tác tìm kiếm dò qua ô này sau đó sẽ dừng lại nhầm — tưởng rằng khoá không tồn tại dù nó thực ra nằm ở phía sau (đã được chèn nhờ dò tiếp qua ô vừa xoá). Giải pháp: đánh dấu ô vừa xoá bằng một tombstone (bia mộ) — một giá trị đặc biệt khác null, báo cho thao tác tìm kiếm "cứ dò tiếp", còn thao tác chèn thì coi tombstone là chỗ trống có thể tái sử dụng.

8. Load Factor & Rehashing

Hệ số tải (load factor) đo mức độ "chật" của bảng băm, với n là số phần tử đã chèn và m là số bucket của bảng:

$$\alpha = \frac{n}{m}$$

Load factor càng cao, số va chạm trung bình càng nhiều — với chaining, độ dài chain trung bình chính là α; với open addressing, khi α tiến gần 1, số bước dò trung bình tăng vọt phi tuyến. Vì vậy mọi cài đặt thực tế đều đặt một ngưỡng (thường 0.7 với open addressing, có thể cao hơn với chaining) — vượt ngưỡng thì rehash: tạo bảng mới lớn hơn (thường gấp đôi) rồi băm lại & chèn lại toàn bộ phần tử cũ:

function rehash(oldSlots) {
  const newSize = oldSlots.length * 2 + 1; // gấp đôi + lẻ, gần số nguyên tố hơn
  const newSlots = new Array(newSize).fill(null);
  for (const key of oldSlots) {
    if (key === null || key === TOMBSTONE) continue;
    insertLinear(newSlots, key); // băm lại theo kích thước MỚI — chỉ số thay đổi hết
  }
  return newSlots;
}
// Chi phí rehash là O(n), nhưng vì tần suất giảm dần theo cấp số nhân
// (giống dynamic array), chi phí trung bình mỗi lần insert vẫn là O(1)
// khấu hao (amortized) — cùng lập luận với việc mảng động tăng gấp đôi.

9. So Sánh Separate Chaining vs Open Addressing

Sân chơi tương tác: Hash Table Visualizer

Chèn khoá số (0–999) vào bảng 7 bucket, chọn chiến lược xử lý va chạm, và quan sát hàm băm cùng bước dò từng lần chèn trong nhật ký. Click vào một khoá đã chèn để xoá (Open Addressing sẽ đánh dấu tombstone thay vì xoá trắng). Bấm "Rehash" khi hệ số tải cao để xem bảng mở rộng và băm lại toàn bộ.