Perfect hash function là gì?

Trong khoa học máy tính (computer science), một hàm băm hoàn hảo (perfect hash function) h cho một tập (set) S là một hàm băm (hash function) ánh xạ (map) các phần tử riêng biệt trong S thành một tập hợp m số nguyên, không có đụng độ (collision). Theo thuật ngữ toán học, nó là một hàm đơn ánh (injective function).

Các hàm băm hoàn hảo (perfect hash function) có thể được sử dụng để triển khai (implement) một bảng tra cứu (lookup table) với thời gian truy cập trong trường hợp xấu nhất không đổi.

Như bất kỳ hàm băm nào, một hàm băm hoàn hảo (perfect hash function) có thể được sử dụng để triển khai các bảng băm (hash table), với ưu điểm là không cần thực hiện giải quyết đụng độ. Ngoài ra, nếu các khóa (key) không phải là dữ liệu và nếu biết rằng các khóa được truy vấn sẽ hợp lệ, thì các khóa đó không cần phải được lưu trữ trong bảng tra cứu (lookup table), tiết kiệm không gian (space).

Nhược điểm của các hàm băm hoàn hảo (perfect hash function) là S cần được biết đến cho việc xây dựng hàm băm hoàn hảo (perfect hash function) . Các hàm băm hoàn hảo không động (non-dynamic perfect hash function) cần được xây dựng lại nếu S thay đổi. Để thay đổi thường xuyên, các hàm băm hoàn hảo động (dynamic perfect hash function) S có thể được sử dụng với chi phí (cost) là không gian bổ sung. Yêu cầu về không gian để lưu trữ hàm băm hoàn hảo là O(n).