Re:Fibonacci Hashing: The Optimization That the World Forgot
by rurban on Sunday June 17, 2018 @01:21PM
(#17333269)
I haven't found a usecase yet where a better hash function leads to a faster hash table. Theoretically this would happen with CPUs with extremely slow or small cache.
It's also confirmed with the recent trend to add slower hash functions everywhere, leading to dramatic performance regressions.
"See e.g. A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing
https://infosys.cs.uni-saarland.de/publications/p249-richter...
for a concise overview of the best hash table strategies, confirming that the simpliest Mult hashing (bernstein, FNV*, x17, sdbm) always beat "better" hash functions (Tabulation, Murmur, Farm, ...) when used in a hash table."
The conclusion is not properly stated, it's surely not "always" but there are enough use cases where the simple multiplications (or, even more probably, the "rotate, multiply, xor" and variants) are the fastest in practice.
From the paper:
"We could observe that Mult produces indeed more collisions than the expected amount on uniformly distributed keys. However, this larger amount of collisions does not get highly reflected in the observed performance. Thus, we consider Mult as the best candidate to be used in practice when quality results on high throughputs is desired, but at the cost of a high variance across data distributions."
Itβs still a trade-off, but a good choice in some use cases.