Magic number in boost::hash_combine

Question

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?

Phylogeny

Given that on many computers an integer rotate cost about the same as a shift would there be any benefit in converting the expression to: <code> seed ^= hash_value(v) + 0x9e3779b9 + rotl(seed, 6) + rotr(seed, 2); </code> – Anny

Answer 1

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.

Alisa

Nice, I had read they had noticed it worked pretty well but didn't knew it came from the golden ratio :) – Naphthol

Cool! I like it when number theory suddenly gets useful :) – Phylogeny

@larsmans I love your use of 'suddenly' - it's very appropriate! Number theory is like "yeah, that's nice... but I've got real work to do, sorry" in 99% of all cases. And then, as you say, 'suddenly', number theory is super super useful. It's not like a hammer where it's rather useful for a large number of things. Instead, it's like a scalpel being extremely useful for a small number of things. – Rothstein

So the magic number should be different depending on sizeof(size_t)? – Koerner

@dalle, that would make sense. This one liner: python -c "import math; print hex(int(2**64 / (1 + math.sqrt(5)) / 2))" produced 0x278dde6e5fd29e00 for me. I expect that would work fairly well for when size_t is 64-bits. – Doucette

@SamKellett Would work even better if you used the correct number of parentheses and got 0x9e3779b97f4a7800 – Herwig

Because Python's floating point number doesn't have enough precision, the 64-bit golden ratios above are not correct. The actual result should be 0x9e3779b97f4a7c15. – Stolzer

Speaking of which, this assumes that the golden ratio is what is called a normal number - which it probably is. – Nantucket

@Stolzer Don't you mean 0x9e3779b97f4a7c16? I mean, it's only 1 off. – Gamic

@Gamic That depends on whether you want to round up or round down. – Stolzer

@Stolzer that value is rounded down by casting. Which formula did you actually use? Oh wait, let me guess, you divided 0xFFFFFFFFFFFFFFFF by phi and not 2^64. – Gamic

@Gamic rounding down is definitely 0x...c15. wolframalpha.com/input/… – Stolzer

@Stolzer WolframAlpha has loss of precision between operations. – Gamic

@Stolzer you have no way of specifying the desired precision in there. Try long double instead. – Gamic

@Gamic You are introducing loss of precision because of the "0.5" (which defaults to 7 digits). Use "1/2" for exact arithmetic, or use "0.500000000000000000" if you want more precision. long double only has 64 bits of precision, it is not quite enough for the computation here. – Stolzer

Ruby console: ``` > require 'bigdecimal' => true > d64=BigDecimal.new(1<<64) => 0.18446744073709551616e20 > phi=(1+BigDecimal.new(5).sqrt(64))/2 => 0.16180339887498948482045868343656381177203091798057628621354486227052604625714285715e1 > (d64/phi).to_i.to_s(16) => "9e3779b97f4a7c15" > (d64/phi * (1<<16)).to_i.to_s(16) => "9e3779b97f4a7c15f39c" ``` Therefore "round to nearest" is certainly 0x9e3779b97f4a7c16 But for use as multiplicator 0x9e3779b97f4a7c15 is more preffered since it has lowest bit set. – Ozan

Funnily 1 / phi = phi - 1. No division is needed. And Wikipedia has golden ratio as Hexadecimal 1.9E3779B97F4A7C15. So it would seem 5 is correct and not 6? – Devastating

Answer 2

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.

Answerable

Answer 3

using python to get this mgic number:

from math import sqrt
phi = (1 + sqrt(5)) / 2
hex(int(2**32/phi))

Pellegrini