Bước tới nội dung

Khác biệt giữa bản sửa đổi của “Bảng băm”

tiếp tục dịch thêm từ wiki tiếng Anh
Không có tóm lược sửa đổi
(tiếp tục dịch thêm từ wiki tiếng Anh)
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 mứchệ độ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 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 [[họ Cu cu|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.
==Ghi chú==
{{reflist}}
494

lần sửa đổi