Remix.run Logo
▲ sph 2 hours ago

I just learned about Fibonacci hashing, where you multiply a hash function by a certain factor derived from the golden ratio, which gives you better distribution than a bare integer modulo.

https://probablydance.com/2018/06/16/fibonacci-hashing-the-o...

The graph of the distribution is indeed very similar to the LEDs in this article: https://book.huihoo.com/data-structures-and-algorithms-with-...

So if you find yourself doing:

    bucket = hash % total_buckets;
Consider introducing Fibonacci hashing. And the reason this works, and provides uniform distribution is this: https://en.wikipedia.org/wiki/Equidistribution_theorem