Fast Perfect Hashing
jandrewrogers.com
Fast Perfect Hashing
1–10 of 43 posts
Re: Fast Perfect Hashing
#2this..seems extremely cool (?) does someone have a reference or pointer for further study about how this is 'perfect' and not just 'really good'
Re: Fast Perfect Hashing
#3this..seems extremely cool (?) does someone have a reference or pointer for further study about how this is 'perfect' and not just 'really good'
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
Re: Fast Perfect Hashing
#4this..seems extremely cool (?) does someone have a reference or pointer for further study about how this is 'perfect' and not just 'really good'
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.
Re: Fast Perfect Hashing
#5this..seems extremely cool (?) does someone have a reference or pointer for further study about how this is 'perfect' and not just 'really good'
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 ).
Re: Fast Perfect Hashing
#6The OP seems to be confusing terminology. What they construct is a permutation. Everything they say is relevant to permutations, not perfect hashing.
In particular:
> A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key
This is just false. Perfect hashing is often if not always performed on subsets of the full domain, e.g. the keywords in a programming language.
Re: Fast Perfect Hashing
#7This is awesome! In case you're wondering, the latency of _mm_aesenc_si128 on Skylake and above is only 4 clock cycles
Re: Fast Perfect Hashing
#8> A perfect hash function is one that is collision-free. By implication, the hash must be at least as many bytes as the key
I don't understand this lemma. An indexed array is a degenerate example in which the "hash" (pointer) is presumably a lot smaller than the key (index).
BTW for those not familiar with a perfect hash function they are great for things like symbol tables that are immutable at runtime. You can make a very fast lookup that requires no probing (bucket size is always one) so you can also eliminate a lot of implementation both of code and data structure.
Re: Fast Perfect Hashing
#9The algorithms presented below are much faster than most non-perfect hash functions on recent CPUs.
This is a very vague statement. I would like to see some numbers, as well as real-world use cases.
Last month there was a thread about perfect hashing in the postgres parser, but I wonder if a DFA / trie is better, since you don't have to always look at every byte.
Re: Fast Perfect Hashing
#10this..seems extremely cool (?) does someone have a reference or pointer for further study about how this is 'perfect' and not just 'really good'
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.