boost :: hash_combine中的幻数

boost::hash_combine模板函数引用一个散列（称为seed ）和一个对象v 。 根据文档 ，它结合了seed和v的散列

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

我可以看到这是确定性的。 我明白为什么使用XOR。

我敢打赌，除了有助于将相似的值映射到很远的地方之外，所以探测哈希表不会中断，但是有人能解释一下这个魔术常量是什么吗？

Answer 1

幻数应该是32个随机比特，每个比特可能是0或1，并且这些比特之间没有简单的相关性。 find一串这样的比特的常用方法是使用无理数的二进制扩展; 在这种情况下，这个数字是黄金比例的倒数：

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

所以包括这个数字“随机”改变种子的每一点; 正如你所说，这意味着连续的值将会相距甚远。 包括旧种子的移位版本确保即使hash_value()具有相当小的值范围，差异将很快在所有位上分散。

Answer 2

看一下1997年Bob Jenkins的DDJ文章 。 魔术常数（“黄金比例”）解释如下：

黄金比例确实是一个任意值。 其目的是避免将全零映射到全零。