Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

They hardly forgot it. It's just that today we prefer hash functions that are seeded, so we use a random number instead of the "magical" fibonacci constant.

See for example multiply shift hashing in https://arxiv.org/abs/1504.06804



The article is not about using Fibonacci hash to replace the hash function, but to replace integer modulo when remapping the hash value to smaller space.


Yet, no one in their sane mind uses module on hashing, it's always power of 2 table, so the operation is just: hash & (len -1) which is absolutely trivial. It has been this way for decades.


And yet just here in this article someone asked how it compares to a recent hash implementation that offers non-power of two tables and uses modulo if you let it do that, and I have seen many other recent hash table implementations do so.

But that is also not the only issue: If you use powers of two and resort to bitwise and to pick the bucket, you're even more dependent on a good hash function, which may be impossible to guarantee if implementinf APIs that let the user choose hash function as in the article.

Unless you follow the suggestion in this article and uses this method to pick buckets.


Personally I do murmur smear that involves a RoL, an add and two muls on all input hashes.


To the contrary almost everybody who knows a bit about DDOS security uses primes, not power's of two. This has been this way for decades, see the relevant hash tables for glibc, gcc, binutils, ...


The common "Multiply Shift" hash function is exactly what the article calls "Fibonacci Hashing" except for which constant is being multiplied by. That "Shift" part of "Multiply Shift" is what I assume you're referring to with "remapping".


Only partially, in that the number of bits to shift needs to change if the hash table is resized. And so if your hash table also controls the hashing of the keys, those steps can be combined. But it's often the case that its not in control of that, and so they're often separate steps.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: