Bảng băm (hash table): cách hoạt động, code và độ phức tạp

Bảng băm giải quyết vấn đề gì

Giả sử bạn lưu một triệu bản ghi người dùng và cần tìm một bản ghi theo email. Quét danh sách là O(n). Giữ danh sách đã sắp xếp cho phép tìm nhị phân trong O(log n), nhưng việc chèn trở nên chậm. Bảng băm tìm bản ghi trong O(1) trung bình, dù có bao nhiêu bản ghi, và chèn, xóa cũng nhanh như vậy.

Đó là lý do bảng băm có mặt ở khắp nơi: từ điển và tập hợp trong các ngôn ngữ lập trình, chỉ mục băm của cơ sở dữ liệu, bộ nhớ đệm, bảng ký hiệu trong trình biên dịch và loại bỏ trùng lặp.

Ý tưởng giải thích đơn giản

Hãy tưởng tượng một phòng gửi áo khoác có 100 móc đánh số. Thay vì tìm áo trên tất cả các móc, nhân viên tính ra số móc từ tên bạn rồi đi thẳng tới đó. Hàm tính ra số đó là hàm băm. Một hàm băm tốt thì nhanh, luôn cho cùng một số với cùng một khóa, và phân bố các khóa khác nhau đều trên các móc.

1. Tính h = hash(key).
2. Chọn bucket: index = h % capacity.
3. Chỉ tìm khóa trong bucket đó.

Ví dụ minh họa: xung đột với nối chuỗi

Lấy một bảng có 4 bucket và một hàm băm đồ chơi: tổng vị trí các chữ cái (a = 1, b = 2, ...).

act và bee xung đột với cat. Giờ tra cứu bee nghĩa là kiểm tra ba mục trong bucket 0. Với hàm băm kém (tổng chữ cái bỏ qua thứ tự) hoặc quá ít bucket, chuỗi sẽ dài ra và bảng trở nên chậm. Hàm băm thực tế trộn mọi bit của khóa, và bảng thực tế sẽ lớn thêm khi quá đầy.

Cài đặt bằng Python với nối chuỗi

Mỗi bucket là một danh sách các cặp [key, value]. Khi số phần tử vượt quá 0,75 lần số bucket (hệ số tải - load factor), bảng nhân đôi dung lượng và chèn lại tất cả.

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._resize()
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False
    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.size = 0
        for k, v in old:
            self.put(k, v)

t = HashTable()
for i, word in enumerate(["red", "green", "blue", "cyan", "pink", "gold", "gray"]):
    t.put(word, i)
t.put("red", 100)
t.delete("blue")
print(t.get("red"), t.get("blue"), t.size, len(t.buckets))  # 100 None 6 16

So sánh các chiến lược xử lý xung đột

dict của CPython dùng địa chỉ mở với chuỗi dò có nhiễu (perturbed) và, từ Python 3.7, đảm bảo việc duyệt theo thứ tự chèn. HashMap của Java dùng nối chuỗi và biến các chuỗi dài thành cây cân bằng.

Độ phức tạp thời gian và không gian

O(1) trung bình phụ thuộc vào hàm băm tốt và hệ số tải bị chặn. Python ngẫu nhiên hóa giá trị băm của chuỗi theo từng tiến trình (hash seeding) để kẻ tấn công không dễ gửi nhiều khóa xung đột làm máy chủ chậm xuống O(n) cho mỗi yêu cầu.

Lỗi thường gặp

• Dùng đối tượng khả biến làm khóa, hoặc định nghĩa __eq__ cho một lớp mà không có __hash__ tương ứng. Các đối tượng bằng nhau phải có giá trị băm bằng nhau.
• Mong đợi thứ tự đã sắp xếp. Bảng băm cho tra cứu nhanh chứ không cho thứ tự; hãy dùng danh sách đã sắp xếp hoặc cây cân bằng (cây tìm kiếm nhị phân) khi cần truy vấn theo khoảng hoặc khóa nhỏ nhất.
• Dựa vào giá trị hash() giữa các lần chạy: giá trị băm của chuỗi thay đổi giữa các tiến trình Python trừ khi cố định PYTHONHASHSEED. Hãy dùng hashlib để có giá trị băm ổn định.
• Coi bảng băm là một thành phần bảo mật. Bảng băm dùng hàm băm nhanh không mật mã; mật khẩu cần các hàm băm mật khẩu chuyên dụng.

Khi nào dùng và các cách dùng điển hình trong phỏng vấn

Hãy dùng bảng băm bất cứ khi nào bạn cần trả lời nhanh câu hỏi "mình đã thấy cái này chưa?" hoặc "khóa này ứng với giá trị nào?". Dùng cây tìm kiếm nhị phân hoặc mảng đã sắp xếp khi bạn còn cần thứ tự, khoảng hoặc khóa gần nhất.

Các bài toán kinh điển: two sum (lưu chỉ số của mỗi số, tra target - x), đếm tần suất (collections.Counter), nhóm các từ đảo chữ theo chữ cái đã sắp xếp, phát hiện trùng lặp và ghi nhớ kết quả (memoization) trong quy hoạch động.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)