Hàm băm và bảng 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 các số bằng cách sử dụng một hàm toán học được gọi là hàm băm. Có nhiều hàm băm sử dụng các phím số hoặc chữ và số. Các hàm băm khác nhau được đưa ra bên dưới:

Hàm băm

Sau đây là một số Hàm băm -

Phương pháp phân chia

Đây là phương pháp dễ nhất để tạo một hàm băm. Hàm băm có thể được mô tả là -

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 của bảng băm n sử dụng phần dư. Tốt nhất là n là số nguyên tố để đảm bảo các khóa được phân phối đồng đều hơn.

Ví dụ về Phương pháp Phân chia như sau -

k=1276
n=10
h(1276) = 1276 mod 10
= 6

Giá trị băm thu được là 6

Một nhược điểm của id phương thức phân chia là các khóa liên tiếp ánh xạ tới 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ương pháp nhân

Hàm băm được sử 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ị không đổi nào từ 0 đến 1. Cả k và A đều được nhân và phần phân số của chúng được tách biệt. Sau đó, giá trị này được nhân với n để nhận giá trị băm.

Ví dụ về Phương pháp Nhân như sau -

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

Một ưu điểm của phương pháp nhân là nó có thể hoạt động với bất kỳ giá trị nào của A, mặc dù một số giá trị được cho là tốt hơn những giá trị khác.

Phương pháp Mid Square

Phương thức bình phương giữa là một hàm băm rất tốt. Nó liên quan đến việc bình phương giá trị của khóa và sau đó trích xuất các chữ số r ở giữa làm giá trị băm. Giá trị của r có thể được quyết định theo kích thước của bảng băm.

Ví dụ về Phương pháp Hình vuông giữa như sau -

Giả sử bảng băm có 100 vị trí bộ nhớ. Vì vậy, r =2 vì cần có hai chữ số để ánh xạ chìa khóa tới vị trí bộ nhớ.

k = 50
k*k = 2500
h(50) = 50

The hash value obtained is 50

Bảng băm

Bảng băm là một cấu trúc dữ liệu ánh xạ các khóa đến các giá trị. Nó sử dụng hàm băm để tính toán chỉ số cho khóa dữ liệu và khóa được lưu trữ trong chỉ mục.

Ví dụ về bảng băm như sau -

Chuỗi khóa cần được lưu trữ trong bảng băm là -

35 50 11 79 76 85

Hàm băm h (k) được sử dụng là:

h(k) = k mod 10

Sử dụng thăm dò tuyến tính, các giá trị được lưu trữ trong bảng băm dưới dạng -