3 ms·

this..seems extremely cool (?) does someone have a reference or pointer for further study about how this is 'perfect' and not just 'really good'

lern_too_spel 8y ago
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 https://gist.github.com/badboy/6267743
- zuzun 8y ago
  If someone is looking for modern mix functions, the ones in Murmur are a good choice.
- howard941 8y ago
  Great link, thanks
jandrewrogers 8y ago
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.
porpoisely 8y ago
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 ).
- xorand 8y ago
  The identity function is collision free. It's the fastest one.
ychen306 8y ago
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 https://en.wikipedia.org/wiki/Perfect_hash_function

lern_too_spel 8y ago

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 https://gist.github.com/badboy/6267743

zuzun 8y ago
If someone is looking for modern mix functions, the ones in Murmur are a good choice.
howard941 8y ago
Great link, thanks

jandrewrogers 8y ago

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.

porpoisely 8y ago

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 ).

xorand 8y ago
The identity function is collision free. It's the fastest one.

ychen306 8y ago

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 https://en.wikipedia.org/wiki/Perfect_hash_function