Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Magic number in boost::hash_combine

The boost::hash_combine template function takes a reference to a hash (called seed) and an object v. According to the docs, it combines seed with the hash of v by

seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);

I can see that this is deterministic. I see why a XOR is used.

I bet the addition helps in mapping similar values widely apart so probing hash tables won't break down, but can someone explain what the magic constant is?

like image 504
Fred Foo Avatar asked Feb 09 '11 18:02

Fred Foo


2 Answers

The magic number is supposed to be 32 random bits, where each is equally likely to be 0 or 1, and with no simple correlation between the bits. A common way to find a string of such bits is to use the binary expansion of an irrational number; in this case, that number is the reciprocal of the golden ratio:

phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9

So including this number "randomly" changes each bit of the seed; as you say, this means that consecutive values will be far apart. Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly small range of values, differences will soon be spread across all the bits.

like image 190
Mike Seymour Avatar answered Nov 01 '22 23:11

Mike Seymour


Take a look at the DDJ article by Bob Jenkins from 1997. The magic constant ("golden ratio") is explained as follows:

The golden ratio really is an arbitrary value. Its purpose is to avoid mapping all zeros to all zeros.

like image 24
NPE Avatar answered Nov 01 '22 21:11

NPE