3 ms·
> Don't hashing functions have collisions? They do. The text is somewhat misleading and not properly explaining that. All hash functions have collisions. But
by hannob 10y ago
> Don't hashing functions have collisions?
They do. The text is somewhat misleading and not properly explaining that.
All hash functions have collisions. But from a cryptographically secure hash function we expect that nobody is able to find such a collision. They exist, but the computational power to find one is not available to humans.
- blauditore 10y agoMore precisely, collisions should be as unpredictable as hashes themselves, so the only way to find collisions is brute force.
- isolli 10y agoTo be fair, it is better explained later in the text. But definitely misleading. > Also, it should be computationally infeasible to find any other word which also hashes to '...'
- 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.