Mỗi lần bạn viết d["key"], một bảng băm đang lặng lẽ làm việc. Nó là cấu trúc dữ liệu vô hình nhất trong lập trình — có mặt trong gần như mọi chương trình, gánh phần lớn công việc tra cứu của thế giới, mà hiếm ai dừng lại nghĩ về nó. Ý tưởng cốt lõi đơn giản đến bất ngờ: biến khoá thành một con số, dùng con số đó làm chỉ số trong một mảng, rồi truy cập thẳng. Không phải dò, không phải so sánh từng phần tử — nhảy một phát tới đúng chỗ.
Va chạm là chuyện bắt buộc phải xảy ra
Không gian khoá gần như vô hạn — mọi chuỗi ký tự có thể có — còn mảng thì hữu hạn. Theo nguyên lý chuồng bồ câu, chắc chắn sẽ có hai khoá khác nhau cho ra cùng một chỉ số. Va chạm không phải lỗi thiết kế; nó là điều toán học bắt buộc, và toàn bộ nghệ thuật làm bảng băm nằm ở cách xử lý nó cho khéo. Có hai trường phái:
- Nối chuỗi: mỗi ô chứa một danh sách nhỏ; khoá va chạm thì nối thêm vào danh sách đó. Đơn giản, xoá dễ, nhưng các nút nằm rải rác trong bộ nhớ.
- Dò tuyến tính: nếu ô đã bận thì đi tìm ô trống kế tiếp. Toàn bộ dữ liệu nằm liền trong một mảng, nên thân thiện với bộ đệm CPU hơn hẳn — đó là lý do phần lớn thư viện hiện đại chọn cách này, dù việc xoá phần tử phức tạp hơn vì không được để lại "lỗ hổng" phá vỡ chuỗi dò.
Hàm băm tốt quan trọng hơn tưởng
Cả cấu trúc sụp đổ nếu hàm băm dồn nhiều khoá vào ít ô. Một hàm băm tốt phân tán khoá đều khắp mảng, kể cả khi các khoá rất giống nhau — "user1", "user2", "user3" phải rơi vào những chỗ cách xa nhau. Đây cũng là nơi bảo mật chen vào: nếu kẻ tấn công đoán được hàm băm, họ có thể cố tình gửi những khoá cùng rơi vào một ô, biến tra cứu hằng số thành tuyến tính và làm sập dịch vụ — một kiểu tấn công từ chối dịch vụ có thật, và lý do nhiều ngôn ngữ thêm một mầm ngẫu nhiên vào hàm băm.
Hệ số tải quyết định tốc độ
Hệ số tải là tỉ lệ giữa số phần tử và số ô. Khi nó vượt một ngưỡng — thường quanh 0,7 — va chạm tăng vọt và mọi thao tác chậm dần. Lúc đó bảng phải cấp một mảng mới lớn gấp đôi rồi băm lại toàn bộ phần tử vào mảng mới.
Đây là cái bẫy độ trễ ẩn: một lần chèn xui xẻo kích hoạt việc băm lại có thể chậm gấp hàng nghìn lần lần chèn bình thường. Tính trung bình thì mỗi thao tác vẫn là hằng số — chi phí băm lại được chia đều cho nhiều lần chèn. Nhưng nếu bạn đang viết một hệ thống nhạy độ trễ, nơi cái đuôi 99% mới là thứ quan trọng, thì cú giật đó có thể là thứ giết bạn đúng lúc tải cao nhất.
Vài điều thực dụng
- Nếu biết trước xấp xỉ số phần tử, hãy cấp dung lượng ngay từ đầu để tránh cả loạt lần băm lại trong lúc lớn dần.
- Khoá phải bất biến. Sửa một khoá sau khi đã chèn là làm mất phần tử: giá trị băm đã đổi, nên bảng đi tìm nó ở một chỗ khác và không bao giờ thấy lại.
- Bảng băm không giữ thứ tự chèn trừ khi ngôn ngữ cam kết rõ điều đó. Đừng dựa vào thứ tự tình cờ quan sát được hôm nay — nó có thể đổi ở phiên bản sau, và bạn sẽ có một lỗi rất khó tìm.
Thảo luận