6.3 The perfect hash function

The perfect hash function is one that is injective. In other words, two different keys are guaranteed to map to two different integer values. Such a function does not exist, in general. With sufficient constraints on K, however, it is possible to derive a perfect hash function.

For example, if we restrict that a name can only have 4 characters, then we have severely limited the number of possible key values. Then, assuming we have a hash table with a capacity of 232 entries, we only need to concatenate the 8-bit ASCII codes together. Each unique key is guaranteed to concatenate to a unique 32-bit pattern. Of course, this is extremely wasteful and restrictive, but it is an illustration that the perfect hash function does exist in some cases.