Fibonacci Hashing: The Optimization That the World Forgot • Hacker News Board

Re: Fibonacci Hashing: The Optimization That the World Forgot

#71

Post by flurrything » Sun, Jun 17, 2018, 7:08 PM UTC

aappleby wrote: post #27

fis wrote: post #26

Earlier quoted context omitted.

I also did not follow what is special about 2^n/phi. I found this more concise justification: http://mathforum.org/kb/message.jspa?messageID=431065 "Knuth's finding was that the dispersion of indexes for a sequence of consecutive keys is maximized when M is chosen this way, thus a multiplicative hash table with a dense set of keys will have the fewest possible collisions when M approx= 2^N * R." Although, if the keys…

Murmur3 has good distribution properties and is much less code than City/Highway/Spooky. There are also some hashes based on hardware AES instructions (not crypto, just taking advantage of the mixing properties) that are near perfect but I don't recall their names and haven't benchmarked them.

The code for these hash tables is open source. You keep repeating that he should be using your hash functions for reasons xyz. Honestly, if you really believe this, show that doing so is better.

Just because you are the author of uvw does not make yo right.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#72

Post by [deleted] » Sun, Jun 17, 2018, 7:10 PM UTC

rurban wrote: post #35

fis wrote: post #26

Earlier quoted context omitted.

I also did not follow what is special about 2^n/phi. I found this more concise justification: http://mathforum.org/kb/message.jspa?messageID=431065 "Knuth's finding was that the dispersion of indexes for a sequence of consecutive keys is maximized when M is chosen this way, thus a multiplicative hash table with a dense set of keys will have the fewest possible collisions when M approx= 2^N * R." Although, if the keys…

The best is currently Leonid Yuriev's t1ha. See https://github.com/rurban/smhasher/ Note that in contrast with what Andy or DJB say, the collision safety is not a problem of the hash function per se, as you cannot fix collision attacks with any "safer" hash function. You can easily brute-force even the worst of all siphash in under 4min. Safety begins with 256 bits, in a hash table you got typically 10-14, max 32 to…

[deleted]

Re: Fibonacci Hashing: The Optimization That the World Forgot

#73

Post by allenz » Sun, Jun 17, 2018, 7:19 PM UTC

rurban wrote: post #35

fis wrote: post #26

Earlier quoted context omitted.

I also did not follow what is special about 2^n/phi. I found this more concise justification: http://mathforum.org/kb/message.jspa?messageID=431065 "Knuth's finding was that the dispersion of indexes for a sequence of consecutive keys is maximized when M is chosen this way, thus a multiplicative hash table with a dense set of keys will have the fewest possible collisions when M approx= 2^N * R." Although, if the keys…

The best is currently Leonid Yuriev's t1ha. See https://github.com/rurban/smhasher/ Note that in contrast with what Andy or DJB say, the collision safety is not a problem of the hash function per se, as you cannot fix collision attacks with any "safer" hash function. You can easily brute-force even the worst of all siphash in under 4min. Safety begins with 256 bits, in a hash table you got typically 10-14, max 32 to…

> You can easily brute-force even the worst of all siphash in under 4min

You assume that you know the seed or can directly observe the output, which is rare in practice.

> upper bits of a hash function are always superior to the lower bits

Why is that? The identity hash for ints is quite common. And for good hashes, the difference should be negligible.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#74

Post by allenz » Sun, Jun 17, 2018, 7:24 PM UTC

mickronome wrote: post #42

aappleby wrote: post #22

Don't do this. Use a real hash function that guarantees a highly random distribution, make your hash tables power-of-two sized, and map from hash value to table index using (hash & (size-1)). The fibonacci constant thing will help clean up the distribution of a bad hash function, but it does nothing for collision resistance if the underlying hash function is weak. -Austin, author of Murmurhash and SMHasher

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 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.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#75

Post by twotwotwo » Sun, Jun 17, 2018, 8:50 PM UTC

pubby wrote: post #43

The comments here have given me an idea for my own hash tables. Rather than accounting for poor hash functions using phi or fmix, I'm going to measure the hash function's distribution at run time and throw an error if its bad. For release builds I'll disable these checks.

Runtime errors seem a little bit fussy, but "try a fast approach that usually works, detect worst-case behavior, then fall back to a thing that's usually slower but avoids the worst case" is a common implementation pattern (think introsort). In principle, you could start with something trivial as your hash, then rehash your key with a better-behaved-but-slower function if your normal probing strategy is going on far longer than it ought to given the load factor.

But we rarely see that, and there are probably good reasons. Hash tables are more rarely the bottleneck in the real world than in benchmarks, and when they are an issue, other factors (size, concurrency, weird pathologies, mem latency) may matter more often than hashing time.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#76

Post by injinj » Mon, Jun 18, 2018, 1:36 AM UTC

bradleyjg wrote: post #48

aappleby wrote: post #27

Earlier quoted context omitted.

Murmur3 has good distribution properties and is much less code than City/Highway/Spooky. There are also some hashes based on hardware AES instructions (not crypto, just taking advantage of the mixing properties) that are near perfect but I don't recall their names and haven't benchmarked them.

This one? https://github.com/stg7/haesni

Look at the aeshash in the go runtime:

https://github.com/golang/go/blob/master/src/runtime/asm_amd...

Re: Fibonacci Hashing: The Optimization That the World Forgot

#77

Post by allenz » Mon, Jun 18, 2018, 6:02 AM UTC

flurrything wrote: post #70

allenz wrote: post #64

Earlier quoted context omitted.

It's the same API, but I highly doubt that his implementation is fully compliant with the C++ standard.

It is, and so is boost::unordered_map, that's the whole point of the comparison. Just check the implementation out.

Source on that claim? Here's a comment chain where the author admits that his library is noncompliant: https://probablydance.com/2017/02/26/i-wrote-the-fastest-has.... Also note the complete lack of a standards test suite.

This library uses Robin Hood hashing for speed. As my original link explains, standard implementations use chained buckets so that users can cache lookups and to have better worst-case performance: https://news.ycombinator.com/item?id=9675964

Re: Fibonacci Hashing: The Optimization That the World Forgot

#78

Post by jrootabega » Mon, Jun 18, 2018, 12:34 PM UTC

jrochkind1 wrote: post #52

CephalopodMD wrote: post #30

Earlier quoted context omitted.

Wait, I thought the author was saying to use this _after_ using a more secure hash function, not instead of it. Why wouldn't you do that?

It's about "hash tables" (ie associative arrays, HashMap), right? Is security even an issue in hash functions for this purpose? I honestly don't know, it's not obvious to me that it is.

Perhaps for DOS resistance like the hashdos vulnerability from 2011?

https://nakedsecurity.sophos.com/2011/12/28/large-percentage...

Re: Fibonacci Hashing: The Optimization That the World Forgot

#79

Post by thomasmg » Tue, Jun 19, 2018, 6:13 AM UTC

aappleby wrote: post #28

allenz wrote: post #25

Earlier quoted context omitted.

This is for a hashmap library where the hash functions are user-defined, so a secondary hash is justifiable.

A good secondary hash would be the fmix methods from Murmur, or multiply-byteswap-multiply. However, having seen a lot of terrible user-defined hashes (I do a bit of consulting on an internal Google mailing list), I strongly advise against rolling your own.

As a secondary (supplemental) hash, I found the Murmur finalizer methods are ok, but you can get better if you use different constants. See my result in this answer: https://stackoverflow.com/questions/664014/what-integer-hash...

I measured the avalanche effect (the number of output bits that change if a single input bit is changed; should be nearly 16 on average for a 32 bit hash), independence of output bit changes (output bits should not depend on each other), and the probability of a change in each output bit if any input bit is changed.