Bước tới nội dung

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

n
không có tóm lược sửa đổi
(→‎top: AlphamaEditor, thay tham số coauthor không tồn tại, Executed time: 00:00:02.2684934 using AWB)
nKhông có tóm lược sửa đổi
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.
}}</ref>
 
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==
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:
 
<math>index = f(key,\ array_sizearray\_size)</math>
 
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.
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.
 
===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:
259

lần sửa đổi