Hacker News Reader

winston1984

>They do. >All hash functions have collisions.

This is wrong. There is something called a perfect hash function:

https://en.wikipedia.org/wiki/Perfect_hash_function

>a perfect hash function for a set S is a hash function that maps distinct elements in S to a set of integers, with no collisions. In mathematical terms, it is a total injective function.

They are very handy for hash tables with constant worst-case lookup time.

View on HN

While very useful, you can only construct a collision-free hash function if you know all possible inputs. Otherwise perfect hash functions can only give guarantees over the frequency of collisions.

In the more general case, for a hash function with n bits output, the pigeon hole principle demands that we have a collision at least every 2^n inputs.

Though 2^n could be much larger than the number of items in the observable universe fairly quickly.

Reply on news.ycombinator.com