Hacker News Reader

Comment by mickronome | Hacker News Reader

He's clearly, and obviously not talking about using it as a hash, or even to consider it as a secondary hash as someone mentioned.

The use case according to the article is strictly to replace integer modulo to map into buckets for cases where that operation is the limiting factor. In his case that's when 9ns per key is too much, and roughly 1ns is good.

For small hash tables sometimes the worst case of a linear scan of the entire table is perfectly acceptable, and the additional performance the other 99.999% of the time is a welcome bonus.

View on HN

Fibonacci hashing takes the form of "h * k>>(64-b)", where k is determined by golden ratio and b is the bit size of the table. This involves one generic multiplication, which is the bottleneck. This multiplication is not strictly necessary. You can replace it with k=1033 for example, which can be implemented as "h+(h<<10)+(h<<3)". This will be a good enough safeguard against naive hash functions but is much faster to compute.

With "h * k>>(64-b)", the result has a cycle of 2^b. Suppose b=3 and you have input 1<<3|1, 2<<3|1 and 3<<3|1, Fibonacci hashing will put them to the same bucket – it is not that effective. A safer strategy is to use a proper integer hash function like Thomas Wang's 32-bit hash function. Although it involves more steps, it only involves plus and bit operations and probably can be computed faster than generic multiplication.

At the end of day, however, Fibonacci hashing or similar ideas only helps when you hash keys to similar integers but has no effect when you hash different keys to the same integer. You have to use a reasonable hash function anyway.

> Although it involves more steps, it only involves plus and bit operations and probably can be computed faster than generic multiplication.

It the most recent popular CPUs the multiplication is exactly "one step" long, that's how wonderfully fast they got to be. See e.g. Agner Fog instruction tables. And where not, the number of "steps" is typically not more than 2 or 3. The multiplication is implemented very efficiently today, unless the CPU has to be with a very low transistor count (linke in some embedded systems). The more exotic CPUs can, of course, be different.

Of course it's a secondary hash. He's mapping buckets by a hash and a shift. This is not a new strategy, and xor, Fibonacci, and "real" hashes fall along a spectrum of average vs worst case runtime tradeoffs.

He is talking about using it as a hash function and clearly states so. To quote:

> 1. Hash the key > 2. Map the hash value to a slot

> Knuth [Fibonacci Hash] uses the term “hash function” to refer to something that does both step 1 and step 2.

Actually that quote is in the article for the opposite reason. He is referencing that because historically Fibonochi hashing was coupled with a hashing function and that is why it’s overlooked as a mapping function. His article is specifically advocating using the Fibonacci method only for mapping.

He is writing from the context of writing a hash table library where the user is expected to provide their own hashing function.

When someone else pointed out that you need another hash function on the front:

Author: "Why [would] Fibonacci hashing not work as a hash function alone? It should, unless you have a use case that results in lots of Fibonacci numbers being inserted. You can use the identity function as the hash when you use Fibonacci hashing to assign a hash to an index."

Reply on news.ycombinator.com