https://github.com/rurban/smhasher#:~:text=fibonacci
Because it is not a general purpose hash function, it is barely a hash function, but for a specific purpose it does everything needed while being much faster than everything else.
Fibonacci Hashing: The Optimization That the World Forgot
21–30 of 30 posts
Re: Fibonacci Hashing: The Optimization That the World Forgot
#22I love this property of phi, I used this in a project a while back to order a an initial keyframe stream where it was important to quickly allow the user to arbitrarily jump to any given point in the timeline. It's super easy to implement and you guaranteed that you have something near the query point to show the user right away.
Re: Fibonacci Hashing: The Optimization That the World Forgot
#23Why the golden ratio? Because the continued fraction of the golden ratio is all 1's [0]. So it is uniquely hard to approximate with a rational number. The golden ratio is the bound on Hurwitz's theorem [1]. And avoiding a rational number is what you want for good hashing, because multiplying with a rational number doesn't mix your digits well. [0] https://codegolf.stackexchange.com/questions/48589/generate-... [1] ht…
> So it is uniquely hard to approximate with a rational number.
Fun fact. The best rational approximations for golden ratio are sequential fibonnaci numbers. E.g. fibonacci(n+1)/fibonacci(n)
or for a more concrete example, 21/13
Re: Fibonacci Hashing: The Optimization That the World Forgot
#24To summarize: multiplication hashes are inferior but when used with the golden ratio derived integer, they are actually superior
Poor summary. Better summary. Fibonacci hashing isn't a great hash function, but it is a really good solution to mapping large integers to small integers. Using it for that doubles the speed of hashing in practice.
Why not just xor all the bits together?
Re: Fibonacci Hashing: The Optimization That the World Forgot
#25This 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.
Re: Fibonacci Hashing: The Optimization That the World Forgot
#26While reading this article it occurred to me to wonder if the CPU CRC32C instruction would be good for hash functions; I think the latency is about the same as an integer multiply.
Re: Fibonacci Hashing: The Optimization That the World Forgot
#27I think the author has misunderstood things here. This technique is orthogonal to integer mod. Indeed the author multiplies by their magic constant and then does an integer mod to map into their hashtable's buckets. This technique is actually just applying a fast integer hash on the input keys to the hashtable before mapping the keys to buckets. You can then map to buckets however you want. The additional hash is use…
The way I understood this article, the problem Fibonacci hashing seems to solve is that it turns a hashing strategy that would require a prime modulo into something that can use a power of two modulo.
I think there are some hashing functions around that are already designed to solve that problem at "step 1".
So the question just boils down to which is faster
Re: Fibonacci Hashing: The Optimization That the World Forgot
#28Oh -- this has a name? And it is not commonly known to be better than modulo? Forgotten? I feel old.
The reason multiply+use of high bits is better than modulo is not the golden ratio. In fact, any number using a lot of bits is good (well, not all are the same, like 0 is extremely bad, and 1 and all powers of two are quite bad, because they just shift. But OTOH, the golden ratio is not outstandingly good either -- many values are good.). This is because in the result of a multiplication, higher bits depend on all lower-bits of the operands, because the carry propagates from low bits to higher bits through the resulting value. In contrast, modulo essentially cuts off the upper bits, and so the upper bits are lost for the distribution entropy. This means that if you take the high bits of a multiplication result to distribute into a small set of integers, then you get a better distribution than using only the lower bits, because more bits of the input value are significant for the output result.
I thought this was common knowledge. The man page on rand() used to tell you that you should always multiply into the target range instead of modulo into the target range. It is surprising to see that all big hash libraries seem to miss this.
Re: Fibonacci Hashing: The Optimization That the World Forgot
#29This information density in the article is extremely low.
Re: Fibonacci Hashing: The Optimization That the World Forgot
#30The Linux kernel integer hash uses something similar, so not totally forgotten.
\* These are the negative, (1 - phi) = phi\*2 = (3 - sqrt(5))/2,
\* which is very slightly easier to multiply by and makes no
\* difference to the hash distribution.