C++ boost::hash_combine 中的幻数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4948780/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Magic number in boost::hash_combine
提问by Fred Foo
The boost::hash_combinetemplate function takes a reference to a hash (called seed) and an object v. According to the docs, it combines seedwith the hash of vby
所述boost::hash_combine模板函数采用一个散列（称为参考seed）和对象v。根据文档，它seed与vby的哈希结合
seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
I can see that this is deterministic. I see why a XOR is used.
我可以看到这是确定性的。我明白为什么要使用 XOR。
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?
我敢打赌，添加有助于将相似的值映射得很远，因此探测哈希表不会分解，但有人可以解释魔术常数是什么吗？
回答by Mike Seymour
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:
幻数应该是 32 个随机位，其中每个位都是 0 或 1 的可能性相等，并且位之间没有简单的相关性。找到一串此类位的常用方法是使用无理数的二进制展开；在这种情况下，该数字是黄金比例的倒数：
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.
所以包括这个数字“随机”改变了种子的每一位；正如您所说，这意味着连续的值将相距甚远。包括旧种子的移位版本可确保即使hash_value()具有相当小的值范围，差异也会很快分布在所有位上。
回答by NPE
Take a look at the DDJ article by Bob Jenkins from 1997. The magic constant ("golden ratio") is explained as follows:
看一看Bob Jenkins 于 1997 年发表的DDJ 文章。魔术常数（“黄金比例”）解释如下：
The golden ratio really is an arbitrary value. Its purpose is to avoid mapping all zeros to all zeros.
黄金比例确实是一个任意值。其目的是避免将全零映射到全零。
