Bảng băm

Bài Cây nhị phân tìm kiếm cho ta tra cứu O(log n) mà vẫn giữ thứ tự. Nhưng nhiều lúc mèo con chẳng cần thứ tự - chỉ muốn hỏi “khoá này có chưa?” hoặc “lấy giá trị của khoá này” thật nhanh. Có cách nhanh hơn cả O(log n) không?

Có: bảng băm (hash table), trung bình O(1). Hình dung một dãy ngăn tủ đánh số. Thay vì dò từng ngăn, ta có một hàm băm nhận khoá và nói ngay “khoá này thuộc ngăn số mấy” - đi thẳng tới đó, không cần tìm.

• ▸Bảng băm tra cứu theo khoá gần như tức thì - trung bình O(1).
• ▸Bí quyết: hàm băm tính thẳng ra vị trí cần tới, không phải dò.
• ▸Đánh đổi: bảng băm KHÔNG giữ thứ tự (khác cây nhị phân tìm kiếm).

Một hàm băm (hash function) biến khoá (chuỗi, số…) thành một con số. Lấy số đó chia lấy dư cho số xô (bucket) là ra chỉ số xô để đặt khoá. Tra cứu cũng tính y vậy rồi tới thẳng xô đó. Hàm băm đồ chơi của ta: cộng mã ký tự.

• ▸hash(khoá) → số; số mod (số xô) → chỉ số xô.
• ▸Đặt và tra đều dùng cùng công thức, nên luôn tới đúng xô.
• ▸Một hàm băm tốt phải rải khoá ĐỀU ra các xô, và tính nhanh.

Vì nhiều khoá hơn số xô, kiểu gì cũng có hai khoá rơi cùng một xô - gọi là va chạm (collision). Với hàm cộng mã, mọi từ đảo chữ đều va chạm: cat và act cùng tổng 312, cùng xô. Cách hoá giải phổ biến là chaining: mỗi xô giữ một danh sách các khoá (đúng danh sách liên kết ở bài 2), va chạm thì nối thêm vào chuỗi:

function hashCode(key: string): number {
  let sum = 0;
  for (let i = 0; i < key.length; i++) sum += key.charCodeAt(i);
  return sum;
}

const xo: string[][] = Array.from({ length: 8 }, () => []); // 8 xo, moi xo mot danh sach
const them = (key: string) => xo[hashCode(key) % 8].push(key);

them('cat'); them('dog'); them('act'); // 'cat' & 'act' dao chu -> cung tong

console.log(hashCode('cat') % 8); // xo cua 'cat'
console.log(hashCode('act') % 8); // xo cua 'act' -> trung! (va cham)
console.log(xo[0]);               // hai khoa noi thanh chuoi trong xo 0
console.log(hashCode('fox') % 8); // 'fox' di xo khac

0
0
[ 'cat', 'act' ]
5

Khi tra một khoá, ta tới đúng xô rồi đi trong chuỗi của xô đó để so. Xô ngắn thì gần như tức thì; xô dài thì chậm dần.

• ▸Va chạm: hai khoá khác nhau cùng chỉ số xô - không tránh hết được.
• ▸Chaining: mỗi xô là một danh sách; va chạm thì nối thêm.
• ▸Tra cứu = tới xô + đi trong chuỗi của xô đó.

Gõ một khoá rồi bấm Thêm để xem hàm băm chọn xô nào; thử thêm cat rồi act để thấy va chạm nối chuỗi. Bấm Tìm để xem phải so mấy lần trong xô:

• ▸Cùng giá trị băm → cùng xô → nối vào chuỗi (chaining).
• ▸Tìm trong xô ngắn tốn ít phép so; xô dài tốn nhiều.
• ▸Hệ số tải càng cao thì các xô càng dài.

Nếu hàm băm rải khoá đều và số xô đủ nhiều, mỗi xô chỉ có một hai khoá, nên tra cứu gần như O(1). Để giữ điều đó khi thêm nhiều khoá, bảng băm theo dõi hệ số tải (load factor) = số khoá / số xô; vượt ngưỡng thì tăng số xô và rải lại (rehash).

• ▸Hàm băm tốt + đủ xô → mỗi xô ngắn → O(1) trung bình.
• ▸Hệ số tải cao → xô dài → cần tăng số xô (rehash).
• ▸Hàm băm dở dồn hết vào một xô → O(n), như danh sách liên kết.

Mèo con giờ có hai cách tra cứu nhanh, cho hai nhu cầu khác nhau: bảng băm (O(1), không thứ tự - hợp khi chỉ cần “có/không” hay lấy theo khoá) và cây nhị phân tìm kiếm (O(log n), giữ thứ tự). Đây cũng là lý do Map/Set (JS) và dict (Python) nhanh đến vậy: chúng là bảng băm.