Định nghĩa về băm hoàn hảo
Băm hoàn hảo được định nghĩa là một mô hình băm trong đó bất kỳ tập hợp n phần tử nào có thể được lưu trữ trong một bảng băm có kích thước bằng nhau và có thể thực hiện tra cứu trong thời gian không đổi. Nó được Fredman, Komlos và Szemeredi (1984) phát minh và thảo luận cụ thể và do đó được đặt biệt danh là "FKS Hashing".
Định nghĩa băm tĩnh
Static Hashing xác định một dạng khác của vấn đề băm cho phép người dùng thực hiện tra cứu trên một bộ từ điển đã hoàn thiện (điều đó có nghĩa là tất cả các đối tượng trong từ điển là cuối cùng cũng như không thay đổi).
Ứng dụng
Vì hàm băm tĩnh cần cơ sở dữ liệu, các đối tượng và tham chiếu của nó vẫn giữ nguyên nên các ứng dụng của nó bị hạn chế. Cơ sở dữ liệu có chứa thông tin trải qua sự thay đổi hiếm hoi cũng đủ điều kiện vì nó chỉ yêu cầu một lần chia sẻ lại toàn bộ cơ sở dữ liệu trong những trường hợp hiếm hoi. Các ví dụ khác nhau về sơ đồ băm này bao gồm các tập hợp từ và định nghĩa của các ngôn ngữ cụ thể, tập hợp dữ liệu quan trọng về nhân sự của tổ chức, v.v.
Thực hiện
Trong trường hợp tĩnh, chúng tôi được cung cấp một tập hợp với tổng số p mục nhập, mỗi mục nhập được liên kết với một khóa duy nhất, trước thời hạn. Fredman, Komlós và Szemerédi chọn bảng băm cấp một với kích thước nhóm s =2 (p-1). Để xây dựng, p mục nhập được tách thành q nhóm bằng hàm băm cấp cao nhất, trong đó q =2 (p-1). Sau đó, đối với mỗi nhóm có r mục nhập, một bảng cấp thứ hai được cấp phát với r2 vị trí và hàm băm của nó được chọn ngẫu nhiên từ một bộ hàm băm chung để nó trở nên không có xung đột và được lưu trữ cùng với bảng băm. Nếu hàm băm được chọn ngẫu nhiên sẽ tạo ra một bảng có xung đột, thì một hàm băm mới sẽ được chọn ngẫu nhiên cho đến khi có thể đảm bảo một bảng không có xung đột. Cuối cùng, với hàm băm không va chạm, các mục r được băm vào bảng cấp hai.