▲ | senderista 4 days ago | |
This article is both confused and confusing. What he's really talking about is not a hash function but a pseudorandom permutation (functionally the same as a block cipher), i.e. a pseudorandom bijective function on an integer domain. In the context of hash functions this is often called a "mixer" or "finalizer" (since it's applied as the final step before determining the bucket). Multiplication by the golden ratio is about the simplest such permutation, but it's far inferior to others (several of which I catalogued here, along with their inverses: https://github.com/senderista/hashtable-benchmarks/tree/mast...). The important thing to remember is that multiplication only mixes low bits into high bits, but you should also mix high bits into low bits (e.g. with XOR), as I do here with the "golden ratio" multiplier: https://github.com/senderista/hashtable-benchmarks/blob/mast.... One useful property of permutations is that they're reversible, so you can reconstruct a key from its hash code, which is useful for hash tables with integer keys. I used this technique here to avoid storing keys separately from hash codes: https://github.com/senderista/hashtable-benchmarks/blob/mast.... Applying a separate "mixer" function to the result of a user-supplied hash function makes sense only if the quality of the user's hash function is suspect. If you control the hash function yourself then there's no reason to use one (as I mentioned, a high-quality hash function will include a finalizer anyway). And if you do use a mixer, you should use a better one than this. |