logoalt Hacker News

sph • today at 7:42 AM • 1 reply • view on HN

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

Replies

noduerme • today at 10:00 AM

Is this used for smoothing any other kinds of outputs that you know of? Like, say, removing noise from big data tables you're using for symbolic regression? I've never come across this before but it seems like it's got a lot of potential compared to other methods.