Bảng băm

Trong khoa học máy tính, bảng băm là một cấu trúc dữ liệu sử dụng hàm băm để ánh xạ từ giá trị xác định, được gọi là khóa (ví dụ như tên của một người), đến giá trị tương ứng (ví dụ như số điện thoại của họ). Do đó, bảng băm là một mảng kết hợp. Hàm băm được sử dụng để chuyển đổi từ khóa thành chỉ số (giá trị băm) trong mảng lưu trữ các giá trị tìm kiếm.
Trong trường hợp lý tưởng, hàm băm luôn chuyển đổi các khóa khác nhau đến các chỉ số khác nhau. Tuy nhiên trong thực tế, điều này hiếm khi xảy ra (trừ khi các khóa là cố định: không có thêm khóa mới nào được bổ sung vào bảng sau khi tạo bảng). Thay vào đó, hầu hết các thiết kế bảng băm đều giả sử các khóa khác nhau có thể được băm vào cùng một giá trị (gọi là va chạm băm), và cung cấp cách giải quyết va chạm.
Trong một bảng băm có kích thước đủ lớn, thời gian trung bình cho mỗi lần tra cứu là độc lập với số lượng phần tử trong bảng. Nhiều thiết kế bảng băm cũng cho phép chèn thêm và xóa bỏ tùy ý của cặp khóa-giá trị trong thời gian trung bình (hoặc trừ dần) không đổi cho mỗi thao tác.
Trong nhiều trường hợp, bảng băm có hiệu quả hơn so với cây tìm kiếm hoặc bất kỳ cấu trúc dữ liệu tìm kiếm nào. Vì lý do này, chúng được sử dụng rộng rãi trong nhiều loại phần mềm máy tính, đặc biệt là cho mảng kết hợp,lập chỉ mục cơ sở dữ liệu, tổ chức bộ nhớ đệm, và cấu trúc dữ liệu tập hợp.

Chọn một hàm băm tốt

Hàm băm tốt và thuật toán tốt là hai yếu tố cần thiết để bảng băm hoạt động hiệu quả, nhưng không dễ để đạt được.
Một yêu cầu cơ bản là hàm băm nên phân bố đều các giá trị băm trong mảng. Phân bố không đều làm tăng số lượng va chạm, và do đó tăng chi phí giải quyết chúng. Tính đồng đều đôi khi khó có thể đảm bảo trong thiết kế, nhưng có thể được đánh giá trong thực tiễn bằng cách sử dụng các bài kiểm tra thống kê, ví dụ như, kiểm tra chi-bình phương.
Trong phương pháp địa chỉ mở, các hàm băm cũng nên tránh hiện tượng phân nhóm (ánh xạ hai hay nhiều khóa đến các vị trí liên tiếp trong mảng). Phân nhóm như vậy có thể khiến chi phí tra cứu tăng vọt, ngay cả khi hệ số đầy thấp và va chạm là không thường xuyên.
Các hàm băm mật mã học được cho là hàm băm tốt cho bất kỳ kích thước bảng nào, hoặc bằng cách tính số dư hoặc bằng mặt nạ bit. Tuy nhiên, những phẩm chất này khó có thể bù lại chi phí tính toán lớn hơn nhiều và sự phức tạp của thuật toán.

Hàm băm hoàn hảo.

Nếu tất cả các khóa đều được biết trước khi tạo bảng, có thể sử dụng một hàm băm hoàn hảo để tạo ra một bảng băm hoàn hảo không có va chạm. Nếu sử dụng hàm băm hoàn hảo tối thiểu, thì mọi vị trí trong bảng băm đều được sử dụng.
Hàm băm hoàn hảo cho phép tra cứu trong thời gian hằng số trong trường hợp xấu nhất. Điều này là trái ngược với kết quả cho phương pháp kết nối và phương pháp địa chỉ mở. Hai phương pháp này có thời gian tra cứu trung bình thấp, nhưng có thể rất lớn (tỷ lệ thuận với số lượng khóa) đối với một vài khóa.

Giải quyết va chạm

Va chạm băm nói chung không thể tránh khỏi khi băm một tập hợp ngẫu nhiên của một số lượng lớn các khóa. Ví dụ, nếu băm 2500 khóa vào một triệu ô nhớ, ngay cả với một phân bố hoàn toàn ngẫu nhiên, theo vấn đề sinh nhật có 95% cơ hội ít nhất hai trong số các khóa băm cùng một ô nhớ.
Vì vậy, hầu hết các thiết kế bảng băm đều có phương pháp giải quyết va chạm. Dưới đây là một số phương pháp phổ biến. Trong tất cả các phương pháp này, các khóa (hoặc con trỏ tới chúng) được lưu trữ trong bảng, cùng với các giá trị liên quan. Một điểm quan trọng là mức độ hiệu quả của các phương pháp giải quyết va chạm không phụ thuộc trực tiếp vào số lượng khóa n, mà vào hệ số tải (hay hệ số đầy) của bảng, tỷ lệ n/s giữa n và kích thước s của bảng.

Phương pháp băm Cuckoo

Phương pháp băm cuckoo (tên gọi xuất phát từ sự tương tự giữa hoạt động thuật toán với hành vi của chim Cuckoo) đảm bảo thời gian cho mỗi phép tìm kiếm là hằng số trong trường hợp xấu nhất, và thời gian trừ dần hằng số cho chèn và xóa.