Giới thiệu
Băm (Hashing) là quá trình tạo ra một giá trị từ một văn bản hoặc danh sách số bằng một hàm toán học gọi là hàm băm (hash function). Có nhiều hàm băm sử dụng khóa số hoặc alphanumeric. Các hàm băm khác nhau được đưa ra dưới đây:
Các hàm băm (Hash Functions)
Dưới đây là một số Hàm băm:
Phép chia (Division Method)
Đây là phương pháp dễ nhất để tạo hàm băm. Hàm băm có thể mô tả như sau:
h(k) = k mod n
Ở đây, h(k) là giá trị băm thu được bằng cách chia giá trị khóa k cho kích thước bảng băm n lấy phần dư. Tốt nhất n là số nguyên tố vì điều đó đảm bảo các khóa được phân bố đồng đều hơn.
Ví dụ của Phép chia:
k=1276 n=10 h(1276) = 1276 mod 10 = 6
Giá trị băm thu được là 6
Nhược điểm của phép chia là các khóa liên tiếp ánh xạ đến các giá trị băm liên tiếp trong bảng băm. Điều này dẫn đến hiệu suất kém.
Phép nhân (Multiplication Method)
Hàm băm dùng cho phương pháp nhân là:
h(k) = floor( n( kA mod 1 ) )
Ở đây, k là khóa và A có thể là bất kỳ giá trị hằng số nào giữa 0 và 1. Cả k và A được nhân và phần thập phân của chúng được tách ra. Sau đó nhân với n để lấy giá trị băm.
Ví dụ của Phép nhân:
k=123 n=100 A=0.618033 h(123) = 100 (123 * 0.618033 mod 1) = 100 (76.018059 mod 1) = 100 (0.018059) = 1
Giá trị băm thu được là 1
Ưu điểm của phương pháp nhân là nó có thể làm việc với bất kỳ giá trị A nào, mặc dù một số giá trị được tin là tốt hơn các giá trị khác.
Phương pháp giữa bình phương (Mid Square Method)
Phương pháp giữa bình phương là một hàm băm rất tốt. Nó liên quan đến bình phương giá trị khóa và sau đó trích xuất r chữ số giữa làm giá trị băm. Giá trị r có thể quyết định theo kích thước bảng băm.
Ví dụ của Phương pháp giữa bình phương:
Giả sử bảng băm có 100 vị trí bộ nhớ. Vì vậy r=2 vì cần hai chữ số để ánh xạ khóa đến vị trí bộ nhớ.
k = 50 k*k = 2500 h(50) = 50 Giá trị băm thu được là 50
Bảng băm (Hash Tables)
Bảng băm (hash table) là một cấu trúc dữ liệu ánh xạ khóa đến giá trị. Nó sử dụng hàm băm để tính chỉ số cho khóa dữ liệu và khóa được lưu trữ tại chỉ số đó.
Ví dụ của một bảng băm:
Chuỗi khóa cần lưu trữ trong bảng băm là:
35 50 11 79 76 85
Hàm băm h(k) được dùng là:
h(k) = k mod 10
Sử dụng linear probing (dò tuyến tính), các giá trị được lưu trữ trong bảng băm như sau:
