Bảng băm — Cách hàm băm hoạt động và xử lý va chạm

Bảng băm lưu trữ các cặp khóa-giá trị bằng cách băm mỗi khóa thành một chỉ số trong mảng. Nhờ vậy, bảng có thể nhảy gần đến vị trí đúng thay vì phải quét từng phần tử đã lưu một.

Đó là lý do bảng băm thường có độ phức tạp gần $O(1)$ cho tra cứu, chèn và xóa trong trường hợp trung bình. Nhưng điều này còn phụ thuộc vào điều kiện: hàm băm phải phân bố khóa đủ tốt, và bảng vẫn cần một quy tắc để xử lý va chạm.

Bảng Băm Làm Gì

Bảng băm lưu các cặp khóa-giá trị như "name" -> "Ada" hoặc 42 -> "blue". Nó có hai phần chính:

• một mảng các ô hoặc bucket
• một hàm băm ánh xạ mỗi khóa vào một trong các ô đó

Nếu mảng có $m$ ô, bạn có thể hình dung hàm băm tạo ra một chỉ số từ $0$ đến $m-1$.

Với một ví dụ nhỏ dùng số nguyên, quy tắc có thể là

$$h(k) = k \bmod 8$$

Khi đó khóa $10$ đi vào ô $2$ vì $10 \bmod 8 = 2$.

Các hàm băm thực tế được thiết kế cẩn thận hơn nhiều, đặc biệt với chuỗi và tập dữ liệu lớn. Nhưng ý tưởng cốt lõi vẫn như nhau: tính nhanh một chỉ số, rồi kiểm tra phần tử được lưu ở đó.

Vì Sao Va Chạm Băm Là Không Thể Tránh Khỏi

Va chạm xảy ra khi hai khóa khác nhau cùng ánh xạ vào một ô.

Điều đó là bình thường vì bảng thường có ít ô hơn số lượng khóa có thể có. Với

$$h(k) = k \bmod 8$$

các khóa $10$, $18$ và $26$ đều ánh xạ vào ô $2$. Vì vậy, dù hàm hoạt động đúng như định nghĩa, bảng vẫn phải giải quyết một xung đột.

Nói cách khác, bảng băm không hứa rằng mỗi khóa sẽ có một ô riêng duy nhất. Nó hứa một cách nhanh để thu hẹp phạm vi tìm kiếm, miễn là va chạm được xử lý tốt.

Ví Dụ Cụ Thể: Một Bảng, Một Va Chạm

Giả sử một bảng có $8$ ô và dùng

$$h(k) = k \bmod 8$$

Hãy chèn các khóa $10$, $18$ và $7$.

Đầu tiên, $10$ vào ô $2$ vì $10 \bmod 8 = 2$.

Tiếp theo, $18$ cũng băm ra ô $2$, nên xảy ra va chạm.

Sau đó, $7$ vào ô $7$, nên lần chèn này không va chạm.

Mẫu chung hữu ích luôn giống nhau:

1. Băm khóa.
2. Đi đến ô được đề xuất.
3. Nếu ở đó đã có một khóa khác, áp dụng quy tắc xử lý va chạm.

Khi mẫu này đã rõ, hai chiến lược xử lý va chạm chính sẽ dễ hiểu hơn nhiều.

Chaining So Với Open Addressing

Chaining giữ một bucket ở mỗi ô

Trong chaining, mỗi ô lưu một tập nhỏ các phần tử thay vì chỉ một phần tử.

Nếu $10$ và $18$ đều băm vào ô $2$, bucket $2$ có thể lưu

• $(10, \text{value}_1)$
• $(18, \text{value}_2)$

Để tìm khóa $18$, bảng nhảy đến bucket $2$ và chỉ so sánh các phần tử trong bucket đó.

Chaining đơn giản về mặt ý tưởng, và việc xóa thường cũng dễ hơn so với open addressing. Đổi lại, bucket dài sẽ làm các thao tác chậm hơn.

Open addressing chỉ dùng các ô trong mảng

Trong open addressing, mỗi ô của mảng chứa nhiều nhất một phần tử. Nếu ô gốc đã đầy, bảng sẽ dò các ô khác theo một quy tắc cố định.

Một quy tắc phổ biến là linear probing: nếu ô $2$ đã bị chiếm, thử ô $3$, rồi $4$, rồi $5$, và quay vòng lại nếu cần.

Cách này tránh phải dùng danh sách bucket riêng, nhưng các ô đầy gần nhau có thể tạo thành cụm. Một điểm nữa là tra cứu và xóa phải tuân theo đúng quy tắc dò đã dùng khi chèn.

Khi Nào Có Thể Nói $O(1)$ Là Hợp Lý

Bảng băm thường được mô tả là có tra cứu, chèn và xóa trung bình ở mức $O(1)$. Nhận định về trường hợp trung bình này phụ thuộc vào các điều kiện:

• hàm băm phân bố khóa đủ đều
• hệ số tải được giữ trong tầm kiểm soát
• chiến lược xử lý va chạm được cài đặt đúng

Hệ số tải là tỉ lệ

$$\text{load factor} = \frac{\text{số phần tử đang lưu}}{\text{số ô}}$$

Nếu bảng quá đầy, va chạm sẽ xảy ra thường xuyên hơn và hiệu năng sẽ kém đi. Đó là lý do nhiều cách cài đặt sẽ tăng kích thước mảng khi nó dần đầy.

Hiệu năng trong trường hợp xấu nhất vẫn có thể giảm dần về $O(n)$ nếu quá nhiều khóa dồn vào cùng một vùng.

Những Nhầm Lẫn Thường Gặp Về Bảng Băm

Nghĩ rằng va chạm có nghĩa là hàm băm bị lỗi

Không phải vậy. Va chạm là điều được dự đoán trước. Câu hỏi thực sự là bảng có xử lý chúng hiệu quả hay không.

Xem $O(1)$ như một điều luôn đúng

$O(1)$ thường là phát biểu cho trường hợp trung bình, không phải lời hứa cho mọi đầu vào và mọi thời điểm.

Nhầm lẫn giữa hashing ở đây với mã hóa

Trong ngữ cảnh cấu trúc dữ liệu cơ bản, hàm băm chủ yếu phục vụ việc lập chỉ mục nhanh, không phải để giữ bí mật. Đó là hai mục tiêu khác nhau.

Quên so sánh khóa thực sự

Hai khóa có thể cho cùng một kết quả băm. Sau khi đến đúng bucket hoặc vị trí dò, bảng vẫn phải kiểm tra xem khóa có thực sự khớp hay không.

Khi Nào Bảng Băm Được Dùng

Bảng băm được dùng bất cứ khi nào việc tra cứu nhanh theo khóa là quan trọng. Các ví dụ phổ biến gồm từ điển, bảng ký hiệu, bộ nhớ đệm, lập chỉ mục và đếm tần suất trong dữ liệu.

Đây là lựa chọn rất phù hợp khi tra cứu chính xác theo khóa quan trọng hơn việc giữ các phần tử theo thứ tự sắp xếp. Nếu bạn cần duyệt theo thứ tự, truy vấn theo khoảng hoặc tìm giá trị gần nhất, một cấu trúc khác có thể phù hợp hơn.

Thử Một Ví Dụ Va Chạm Tương Tự

Lấy một mảng nhỏ có $8$ ô và dùng $h(k)=k \bmod 8$. Chèn vài khóa như $3$, $11$, $19$ và $27$. Sau đó xử lý va chạm một lần bằng chaining và một lần bằng linear probing.

Chỉ một bài tập đó cũng đủ làm ý chính trở nên rất cụ thể: va chạm là không thể tránh khỏi, và quy tắc xử lý va chạm sẽ làm thay đổi cách bảng hoạt động. Nếu muốn đi thêm một bước hữu ích, hãy thử phiên bản của riêng bạn với kích thước bảng khác và xem các va chạm thay đổi ra sao.