Perfect hashing (And Minimal perfect hashing)

Perfect Hashing:

A hash function that is injective—that is, maps each valid input to a different hash value—is said to be perfect. 

With such a function one can directly locate the desired entry in a hash table, without any additional searching. 


Minimal perfect Hashing:

A perfect hash function for n keys is said to be minimal if its range consists of n consecutive integers, usually from 0 to n−1. Besides providing single-step lookup, a minimal perfect hash function also yields a compact hash table, without any vacant slots. Minimal perfect hash functions are much harder to find than perfect ones with a wider range.



原文地址:https://www.cnblogs.com/vigorz/p/10499136.html