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.

Hàm băm

Bài chi tiết: Hàm băm

Tại trung tâm của thuật toán bảng băm là một mảng thường được gọi là bảng băm. Thuật toán bảng băm tính ra một chỉ số cho mỗi khóa và dùng chỉ số này để đặt dữ liệu vào mảng. Hàm số thực hiện việc tính toán này gọi là hàm băm, f:

chỉ-số = f(khóa, kích-thước-mảng)

Hàm băm tính toán một chỉ số trong mảng từ khóa và kích thước của mảng. Trong hợp ngữ hoặc các ngôn ngữ lập trình bậc thấp khác, một hàm băm có thể tạo ra chỉ số chỉ với một hoặc hai lệnh máy.

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 kết nối

Trong phương pháp kết nối (còn gọi là kết nối riêng rẽ, kết nối trực tiếp), mỗi ô của bảng là một con trỏ tới một danh sách liên kết chứa các cặp khóa-giá trị được băm tới cùng một vị trí. Để tìm kiếm, thuật toán duyệt qua danh sách để tìm khóa cho trước. Để chèn khóa mới, thuật toán chèn khóa đó vào đầu danh sách ở ô nhớ tương ứng với giá trị băm của khóa. Để xóa một khóa, thuật toán phải duyệt qua danh sách và xóa khóa đó khỏi danh sách.

Phương pháp địa chỉ mở

Trong phương pháp địa chỉ mở, mọi cặp khóa-giá trị được lưu trực tiếp trong bảng. Khi một cặp khóa-giá trị mới được chèn vào bảng, thuật toán duyệt trong bảng theo một thứ tự thăm dò nhất định bắt đầu từ ô tương ứng với giá trị băm của khóa, cho tới khi tìm được một ô trống. Cặp khóa-giá trị mới được chèn vào ô trống đó. Khi tìm kiếm, thuật toán cũng duyệt theo thứ tự thăm dò bắt đầu từ ô tương ứng với giá trị băm.

Một số thứ tự thăm dò phổ biến bao gồm:

• Thăm dò tuyến tính, trong đó khoảng cách giữa hai vị trí thăm dò liên tiếp là cố định (thường là 1)
• Thăm dò bậc hai, trong đó khoảng cách giữa hai vị trí thăm dò liên tiếp tăng dần tuyến tính
• Băm hai lần, trong đó khoảng cách giữa hai vị trí thăm dò liên tiếp là một hàm băm khác

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.