Bước đầu của việc tìm kiếm bằng phép băm là tính một hàm băm (hash function) để chuyển đổi từ khoá tìm kiếm vào địa chỉ bảng. Trường hợp lý tưởng, các khoá khác nhau nên ánh xạ vào các địa chỉ khác nhau, nhưng thực tế thì không có hàm băm hoàn chỉnh và sẽ có hai hay nhiều khoá khác nhau sẽ băm đến cùng một địa chỉ. Phần thứ hai của tìm kiếm băm là giải quyết xung đột (collision - resolution) để cư xử với các khoá như đã nói. Một trong các phương pháp giải-quyết-xung-đột mà chúng ta nghiên cứu là dùng các danh sách liên kết, bởi vì lưu trữ động lên phương pháp này thích hợp khi số lượng khoá tìm kiếm không thể tiên đoán trước. Hai phương pháp xử lý xung đột khác mà chúng ta xem xét sẽ có thời gian tìm kiếm nhanh trên các mẩu tin được lưu trữ trong một mảng cố định.

Phép băm là một thí dụ tốt về vấn đề dung hoà giữa thời gian chạy và dung lượng bộ nhớ sử dụng. Nếu không có sự giới hạn về bộ nhớ thì chúng ta có thể thực hiện bất kỳ một thao tác tìm kiếm nào chỉ với một lần truy xuất bộ nhớ bằng cách sử dụng khoá như một địa chỉ bộ nhớ. Nếu không có sự giới hạn về thời gian thì chúng ta có thể tối thiểu hoá dung lượng bộ nhớ sử dụng bằng cách dùng một phương pháp tìm kiếm tuần tự. Phép băm cung cấp một phương pháp dùng một lượng vừa phải của bộ nhớ và để làm một sự cân bằng giữa hai thái cực này. Sử dụng hiệu quả bộ nhớ có sẵn và truy xuất nhanh đến bộ nhớ là quan tâm chủ yếu của bất kỳ một phương pháp băm.

Phép băm là một bài toán “cổ điển” của khoa học máy tính đã có nhiều bài toán khác nhau được nghiên cứu và được dùng rất rộng rãi. Có một số lượng lớn những phân tích và kinh nghiệm để cung cấp các thủ tục băm cho rất nhiều ứng dụng khác nhau.

2. Các hàm Băm

Vấn đề đầu tiên là chúng ta phải tính toán hàm băm để chuyển đổi các khóa thành các địa chỉ bảng. Đây là một tính t oán số học có các tính chất tương tự như các bộ phát sinh số ngẫu nhiên mà chúng ta đã biết. Chúng ta cần một hàm chuyển đổi các khoá (các khoá có thể là những số nguyên hay các ký tự ngắn) thành các số nguyên trong khoảng [0..M-1] trong đó, M là số các mẩu tin mà có thể chứa đủ trong số lượng bộ nhớ có sẵn. Một hàm băm lý tưởng là một hàm mà dễ dàng tính và gần giống như một hàm “ngẫu nhiên”.

Vì các phương pháp chúng ta sẽ dùng là phương pháp số học, nên bước đầu tiên là chuyển các khoá thành các số để có thể thực hiện các phép toán số học. Với các khoá nhỏ thì hầu như không cần làm gì cả bởi vì chúng ta sẽ dùng biểu diễn nhị phân của các khoá như những con số. Với các khoá lớn hơn, người ta phải suy nghĩ cách xoá các bit khỏi các chuỗi ký tự và nến tất cả chúng lại thành một từ cơ sở của máy tính; tuy nhiên chúng ta sẽ thấy một phương pháp chung cho các khoá có chiều dài tuỳ ý.

Trước tiên, giả sử chúng ta có một số nguyên lớn tương ứng trực tiếp tới khoá của chúng ta. Có lẽ phơng pháp được dùng duy nhất cho phép băm là chọn M nguyên tố và với mọi k ta tính h(k)= k mod M. Đây là phương pháp đơn giản rất dễ dàng tính trong nhiều môi trường và trải khá tốt vào tập các giá trị các giá trị khóa.

Ví dụ kích thước bảng của ta là 101 và cần phải tính một chỉ số cho một khoá bốn ký tự A K E Y: nếu khoá được mã hoá bằng mã 5 bit đơn giản (ký tự thứ i trong bảng được biểu diễn bởi biểu diễn nhị phân của số i) thì chúng ta có thể xem khoá trên như số nhị phân 000010110010111001, số này tương đương với 44217 thập phân. Bây giờ ta có 44217 = 80(mod 101), vì vậy khoá A K E Y được áp tới vị trí 80 trong bảng. Vì có rất nhiều vị trí khoá nhưng lại các vị trí trong bảng nên có khả năng các khoá khác nhau được áp tới cùng một vị trí trong bảng (ví dụ như khoá B A R H cũng có địa chỉ 80 theo cách băm nói trên).

Tại sao kích thước M của bảng băm phải nguyên tố? Trả lời cho câu hỏi này phụ thuộc vào tính chất số học của hàm mod. Chúng ta đang dùng khoá giống như số cơ số 32, một chữ số chính là một ký tự trong khoá, khoá A K E Y (tương ứng với số 44217) cũng có thể viết là

1. 32³ + 11. 32² + 5. 32¹ + 25. 32⁰

bởi vì A là cữ cái đầu tiên, K là chữ cái thứ 11,…Bây giờ ta giả sử rằng, chúng ta vô tình chọn M= 32 thì giá trị của k mod 32 không ảnh hưởng khi thêm vào các bội số của 32 và hàm băm của mọi khoá chỉ đơn giản là giá trị của ký tự cuối cùng của khoá ! Một hàm băm tốt nên lấy tất cả cá ký tự của một khoá để tính toán. Phương pháp đơn giản nhất để bảo đảm điều này là chọn M nguyên tố.

Nhưng hoàn cảnh thông thường nhất là khi các khoá không là các số, không ngắn, chẳng hạn có thể là một chuỗi dài các ký tự. Làm sao chúng ta có thể tính toán hàm băm cho một khoá cỡ như: V E R Y L O N G K E Y? Trong cách mã hoá của chúng ta số này là một chuỗi dài 55 bit

1011000101100101100101100011110111000111010110010111001

Hay là số:

22.32¹⁰ + 5.32⁹+18.32⁸+25.32⁷+12.32⁶+15.32⁵+14.32⁴+7.32³+11.32²+5.32¹+25

số này quá lớn đối với các hàm số học thông thường trên hầu hết các máy tính. Thực tế chúng ta có thể gặp các khoá dài hơn rất nhiều, trong hoàn cảnh như thế chúng ta vẫn có thể tính một hàm băm giống như trên, lần lượt chuyển đổi từng mẩu một của khóa. Một lần nữa chúng ta lợi dụng tính chất của hàm mod và dùng một cách tính toán đơn giản gọi là phương pháp Horner. Phương pháp này dựa trên một cách viết khác của số tương ứng với các khoá với ví dụ trên, chúng ta viết biểu thức tính khoá như sau:

(((((((((22.32+5)32+18)32+25)32+12)32+15)32+14)32+7)32+11)32+5)32+25

Điều này dựa trên một phương pháp số học trực tiếp để tính hàm băm như sau:

Trong đó h là giá trị băm cần tính và key[i] được giả sử chứa j nếu ký tự thứ i trong khoá là ký tự thứ j trong bảng chữ cái. Hàm chuyển đổi ký tự ord của Pascal có thể được dùng để tính (và một mảng chữ cái lớn có thể được cung cấp nếu cần bằng cách dùng 64 hay 128 thay vì 32). Nếu không có hàm mod, đoạn chương trình trên sẽ tính số tương với khoá nhỏ trong phương trình trên, nhưng tính toán có thể tràn đối với khoá dài. Tuy nhiên với sự hiện diện của hàm mod, nó tính hàm băm chính xác bởi vì các tính chất cộng và nhân của hàm mod, và mặt khác trường hợp tràn sẽ tránh khỏi vì hàm mod luôn luôn cho một kết quả nhỏ hơn M. Địa chỉ băm được tính bởi chương trình này cho V E R Y L O N G K E Y với M=101 là 97.

School@net