3 ms·
>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_fu
by winston1984 10y ago
>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 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.
- halomru 10y agoWhile 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.
- chris_va 10y agoThough 2^n could be much larger than the number of items in the observable universe fairly quickly.