A perfect hash function has no collisions. Typically, people are interested in perfect hashes constructed on types that themselves are not represented in the number of output bits but with an input cardinality that is less than or equal to the output's cardinality.

What the author is describing here is more commonly called a mixing function. There are many fast mixing functions. https://gist.github.com/badboy/6267743

If someone is looking for modern mix functions, the ones in Murmur are a good choice.

Great link, thanks

I really dislike posts like this one. For technical stuff like this people should start out with definition so everyone know what the author means by, for example, "perfect hashing".

> By implication, the hash must be at least as many bytes as the key and the function is theoretically reversible

No. At least not by the standard definition[1]. In standard context, the problem of constructing a perfect hash function is, given (ahead of time) a list of items, you find a hash function that can map them to a smaller "range" without collision.

[1] https://en.wikipedia.org/wiki/Perfect_hash_function

Encryption algorithms must be reversible, which means each of the internal sub-block operations they are composed from must also be reversible. AES is amenable to isolating reversibility in sub-block ranges.

It is easy to exhaustively test for collisions in the key space for smaller keys and to do thorough statistical tests for larger keys where enumerating all keys is not possible.

The first sentence of the article explains what a perfect hash function is : "A perfect hash function is one that is collision-free.". Essentially, a perfect hash function is one where no two domain elements map to the same range element.

If you want to explore it further, you can search for injective functions and one-to-one mapping.

An example of a function that produces collisions is the ABS function.

ABS( 2 ) = 2.

ABS( -2 ) = 2.

Two domain elements ( 2 and -2 ) map to the same range element ( 2 ).

The identity function is collision free. It's the fastest one.