115

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?

Human-Compiler
  • 11,022
  • 1
  • 32
  • 59
Fred Foo
  • 355,277
  • 75
  • 744
  • 836
  • 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: seed ^= hash_value(v) + 0x9e3779b9 + rotl(seed, 6) + rotr(seed, 2); – John Yates Jun 02 '16 at 20:54

3 Answers3

170

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.

Mike Seymour
  • 249,747
  • 28
  • 448
  • 644
  • Nice, I had read they had noticed it worked pretty well but didn't knew it came from the golden ratio :) – Matthieu M. Feb 09 '11 at 20:53
  • 20
    Cool! I like it when number theory suddenly gets useful :) – Fred Foo Feb 09 '11 at 21:28
  • 10
    @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. – corsiKa Aug 16 '13 at 19:44
  • 1
    So the magic number should be different depending on `sizeof(size_t)`? – dalle Apr 15 '14 at 19:40
  • @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. – Sam Kellett Apr 23 '14 at 14:01
  • 5
    @SamKellett Would work even better if you used the correct number of parentheses and got `0x9e3779b97f4a7800` – Barry Sep 22 '15 at 18:51
  • 5
    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`. – kennytm Nov 27 '15 at 15:08
  • Speaking of which, this assumes that the golden ratio is what is called a [normal number](https://en.wikipedia.org/wiki/Normal_number) - which it probably is. – Iosif Spulber Sep 07 '16 at 11:43
  • 2
    @kennytm Don't you mean [`0x9e3779b97f4a7c16`](http://coliru.stacked-crooked.com/a/c977420af344e736)? I mean, it's only 1 off. – bit2shift Dec 11 '16 at 05:05
  • @bit2shift That depends on whether you want to round up or round down. – kennytm Dec 11 '16 at 07:37
  • @kennytm 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`. – bit2shift Dec 11 '16 at 17:50
  • 1
    @bit2shift rounding down is definitely 0x...c15. http://www.wolframalpha.com/input/?i=floor(2%5E64+%2F+golden+ratio)+in+base+16 – kennytm Dec 12 '16 at 07:45
  • @kennytm WolframAlpha has [loss of precision](http://www.wolframalpha.com/input/?i=floor(2%5E64+%2F+%7B(sqrt(5)+*+0.5+%2B+0.5),+((1+%2B+sqrt(5))+%2F+2),+golden+ratio%7D)) between operations. – bit2shift Dec 12 '16 at 14:06
  • @kennytm you have no way of specifying the desired precision in there. Try `long double` instead. – bit2shift Dec 12 '16 at 14:16
  • @bit2shift 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. – kennytm Dec 12 '16 at 15:46
  • 1
    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. – funny_falcon Feb 20 '20 at 10:29
  • 1
    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? – the swine Oct 26 '22 at 02:00
29

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.

NPE
  • 486,780
  • 108
  • 951
  • 1,012
1

using python to get this mgic number:

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