🗂️ Bảng băm (Hash Table)

Mảng cho bạn truy cập O(1) - nhưng chỉ khi biết trước chỉ số (index). Nếu muốn tra cứu bằng một thứ khác - tên người, mã sinh viên, một chuỗi bất kỳ - bạn buộc phải duyệt qua từng phần tử để so sánh, tốn O(n). Hash table giải quyết đúng vấn đề này: nó cho phép tra cứu theo một “khóa” (key) tuỳ ý mà vẫn giữ được tốc độ gần O(1), bằng một mẹo đơn giản - biến key thành một con số, rồi dùng con số đó làm chỉ số mảng.

Ghi chú

Hash table còn được gọi là hash map, dictionary (Python), hoặc associative array. Trong hầu hết ngôn ngữ, nó là cấu trúc dữ liệu bạn dùng “mặc định” mỗi khi cần tra cứu nhanh theo key: dict trong Python, Map/HashMap trong Kotlin/Java, Dictionary trong Swift.

Hàm băm biến key thành chỉ số

Mọi hash table đều dựa trên một hàm băm (hash function): nhận vào một key (chuỗi, số, hay bất kỳ kiểu dữ liệu nào), trả về một con số nguyên. Từ con số đó, lấy phần dư cho dung lượng mảng (capacity) để ra chỉ số cần lưu:

index = hash(key) % capacity

person = {}
person["name"] = "John"   # Python tự tính hash("name"), tìm ô tương ứng để lưu
print(person["name"])     # tính lại hash("name"), nhảy thẳng đến đúng ô -> O(1)

Vì bước “nhảy thẳng đến đúng ô” không phụ thuộc số lượng phần tử đang có trong bảng, việc thêm, tìm, xóa đều đạt độ phức tạp trung bình O(1) - khác hẳn với việc phải dò tuần tự trong mảng hay linked list.

Va chạm: khi hai key trỏ về cùng một ô

Không gian các key có thể có (mọi chuỗi, mọi số) gần như vô hạn, trong khi số ô của mảng luôn hữu hạn. Theo nguyên lý chuồng bồ câu (pigeonhole), sớm muộn sẽ có hai key khác nhau cho ra cùng một index - gọi là va chạm (hash collision). Đây không phải lỗi thiết kế mà là điều không thể tránh khỏi; vấn đề chỉ là xử lý nó thế nào.

Hai cách xử lý phổ biến:

Separate chaining (nối chuỗi): mỗi ô không chứa trực tiếp một cặp key-value, mà chứa một danh sách nhỏ các cặp bị rơi vào cùng ô đó. Khi tra cứu, tính index xong thì duyệt qua danh sách ngắn ấy để tìm đúng key.

class HashMapChaining:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]  # mỗi ô là 1 danh sách

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for pair in bucket:
            if pair[0] == key:      # key đã tồn tại -> cập nhật
                pair[1] = value
                return
        bucket.append([key, value])  # key mới -> thêm vào cuối danh sách

    def get(self, key):
        bucket = self.buckets[self._index(key)]
        for k, v in bucket:
            if k == key:
                return v
        return None

Open addressing (địa chỉ mở): không dùng danh sách phụ, mà khi một ô đã có người ở, thử ô kế tiếp theo một quy luật nào đó cho đến khi tìm được ô trống - cách đơn giản nhất là linear probing: thử lần lượt index + 1, index + 2, …

Chú ý

Càng nhiều va chạm, chuỗi trong mỗi ô càng dài (hoặc phải dò càng nhiều ô), khiến độ phức tạp trung bình O(1) trượt dần về O(n) ở trường hợp xấu nhất. Vì vậy hash table luôn tự mở rộng dung lượng (resize) khi tỷ lệ số phần tử/capacity - gọi là load factor - vượt một ngưỡng nhất định (thường quanh 0.75), rồi băm lại toàn bộ key sang bảng lớn hơn để giữ số lượng va chạm ở mức thấp.

Một hàm băm tốt cần gì?

• Phân bố đều: các key khác nhau nên rải đều khắp các ô, tránh dồn cục gây va chạm nhiều.
• Tính nhanh: hash table tồn tại để nhanh, nên bản thân phép băm không được trở thành nút thắt cổ chai.
• Ổn định: cùng một key luôn cho cùng một giá trị băm, ở mọi lần gọi.

Hàm băm dùng cho hash table thông thường (nhân, XOR, dịch bit…) khác hẳn mục tiêu với các thuật toán băm mật mã như MD5, SHA-256 - loại sau được thiết kế để khó bị đảo ngược và khó cố ý tạo va chạm, nên chậm hơn nhiều và không phù hợp làm hàm băm cho hash table.

Vì sao key phải là kiểu bất biến?

Một hệ quả quan trọng của cách hash table hoạt động: key phải là kiểu dữ liệu bất biến (immutable), hoặc ít nhất là kiểu mà giá trị hash của nó không đổi trong suốt vòng đời làm key.

Lý do: vị trí lưu một key trong bảng được quyết định bởi hash(key) tại thời điểm thêm vào. Nếu sau đó bạn sửa đổi nội dung của key khiến giá trị hash thay đổi, hash table sẽ tìm sai ô khi tra cứu lại - vì nó tính hash mới, trong khi dữ liệu vẫn nằm ở ô ứng với hash cũ.

# list là kiểu mutable -> không dùng được làm key
cache = {}
key = [1, 2]
# cache[key] = "value"  # TypeError: unhashable type: 'list'

# tuple là bất biến -> dùng được làm key
cache[(1, 2)] = "value"
print(cache[(1, 2)])  # "value"

Chú ý

Đây cũng là lý do vì sao trong Python, dict yêu cầu key phải “hashable” (có __hash__), và các kiểu mutable như list, dict, set không định nghĩa __hash__ - Python chủ động chặn lỗi này ngay từ đầu thay vì để bạn gặp bug âm thầm lúc runtime.

Hai ứng dụng kinh điển

Two Sum - tìm hai số trong mảng có tổng bằng target. Thay vì so mọi cặp (O(n²)), lưu lại những gì đã thấy để tra cứu tức thời:

def two_sum(nums, target):
    seen = {}   # giá trị đã thấy -> chỉ số của nó
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:       # tra cứu O(1) thay vì quét lại từ đầu
            return [seen[complement], i]
        seen[num] = i
    return []

Đếm tần suất - đếm số lần xuất hiện của mỗi phần tử, chỉ cần một lượt duyệt:

def frequency_count(arr):
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    return freq

Mẫu số chung: bất cứ khi nào cần “tra cứu xem đã gặp/đếm được bao nhiêu lần”, hash table gần như luôn là lựa chọn đầu tiên.