Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Fibonacci Hashing: The Optimization That the World Forgot

probablydance.com

Post reply on HN
Print view View original

21–30 of 79 posts

Re: Fibonacci Hashing: The Optimization That the World Forgot

#21

Post by extremelearning »

no_identd wrote: post #16

I wonder if, under some circumstances, one ought to use this instead for optimality of this or something similar: https://en.wikipedia.org/wiki/Plastic_number for a similar use. It shares a property with phi which no other irrational shares with it (They are known as the only two Morphic numbers, which one must avoid confabulating with a similarly named concept whose name I can't recall right now.). And Knuth liked i…

As @twic and the OP discussed, the equal distribution of numbers within a defined range is naturally achieved through low discrepancy sequences (eg recurrence,Halton, Sobol, etc..) Furthermore, in ultra high-speed / low-level computing situations the additive recurrence methods are often preferred due to the incredibly fast and simple method of calculating the each successive term simply by adding (modulo) a constant value to the previous term.

For the one-dimensional case, it is well known, and relatively easily proven that the the additive recurrence method based on the golden ratio offers the optimal 'evenness' [low discrepancy] in distribution [1]. For higher dimensions, it is still an open research question as to how to create provably optimal methods. However, one of my recent blog posts [2] explores the idea that a generalization of the golden ratio, produces results that are possibly optimal, and better than existing contemporary low discrepancy sequences. In the one dimensional case, the critical additive constant is of course, the golden ratio. In the two dimensional case, the additive constant is based on integral powers of the plastic number. The generalization to even higher dimensions follows other Pisot numbers.

[1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence#Addit...

[2] http://www.extremelearning.com.au/unreasonable-effectiveness...

Re: Fibonacci Hashing: The Optimization That the World Forgot

#22

Post by aappleby »

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

Re: Fibonacci Hashing: The Optimization That the World Forgot

#23

Post by aappleby »

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

Also, there is nothing magic about his fibonacci constant. Any large odd constant with roughly half the bits set at random will do the same thing.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#24

Post by strainer »

The Golden Ratio is proposed as a special multiplier for what is otherwise known as 'linear congruential' psuedorandom number generation. I'm not clear on whether the non-repetitive property of the ratio will benefit its performance at all.

This decimal is computed for 2^64 /1.618... 11400714819323198486 -it looks like this in binary: 1001111000110111011110011011100101111111010010100111110000010101

The runs of 7 ones, 5 zeros and 5 ones could be sub-optimal.

[1] Donald Knuth himself discovered this one for 64bits: 101100001010001111101000010110101001100100101010111111100101101

It contains a run of 7 ones, and 5, but maximum zeros in a row is 4.

I did once mine multipliers for LCGs of different bitlengths by comparing quickly measured ratios in their output to those precomputed from good psuedorandom sequences (average deviation etc) Then having found numbers which achieved the basic signature of random data, they were tested with Marsaglia's old 'diehard' battery of tests - and often passed.

Here is a multiplier discovered for a 32bit LCG 110010011101110100001011

I had a list of them I meant to examine here, but have lost it :(

Anyway, there is plenty of academic work to read on this subject:

1 - https://en.wikipedia.org/wiki/Linear_congruential_generator#...

Re: Fibonacci Hashing: The Optimization That the World Forgot

#25

Post by allenz »

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

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

Re: Fibonacci Hashing: The Optimization That the World Forgot

#26

Post by fis »

aappleby wrote: post #23
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

Also, there is nothing magic about his fibonacci constant. Any large odd constant with roughly half the bits set at random will do the same thing.

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 are dense, then we could just use the low bits directly. I guess the unstated assumption is that in the real world, we'll have a mix of keys that are sequential and keys that are strided in such a way that using low bits directly would cause a lot of collisions. So we need a multiplicative hash to take care of the latter and we should use 2^n/phi to take care of the former.

Austin, you've done a lot of great work on this. What is the hash function you'd use today for small (<=32byte) keys?

Re: Fibonacci Hashing: The Optimization That the World Forgot

#27

Post by aappleby »

fis wrote: post #26
aappleby wrote: post #23

Earlier quoted context omitted.

Also, there is nothing magic about his fibonacci constant. Any large odd constant with roughly half the bits set at random will do the same thing.

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.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#28

Post by aappleby »

allenz wrote: post #25
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

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.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#29

Post by jamiek88 »

gct wrote: post #12

If you have a reasonable hash function, why is power-of-two and bitmasking bad? If you're uniformly distributed over a range N you'll be uniformly distributed over N/2

It isn’t. You are correct. This is useful to support the underlying hash function but at that point you might as well just improve that and take the power of two, bitmask approach.

Re: Fibonacci Hashing: The Optimization That the World Forgot

#30

Post by CephalopodMD »

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

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?
Post reply on HN