boost :: hash_combine中的幻数

Question

所述boost::hash_combine模板函数采用一个散列(称为参考seed)和对象v.根据文档,它结合seed了vby 的哈希

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

我可以看出这是确定性的.我明白为什么要使用XOR.

我敢打赌,这个加法有助于将相似的值广泛分开,因此探测哈希表不会崩溃,但有人可以解释这个神奇常数是什么吗？

Answer 1

幻数应该是32个随机位,其中每个位同样可能是0或1,并且位之间没有简单的相关性.找到一串这样的位的常用方法是使用无理数的二进制扩展; 在这种情况下,该数字是黄金比例的倒数:

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

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

凉!当数论突然变得有用时我喜欢它:) (12认同)
@larsmans我喜欢你'突然'的使用 - 这是非常合适的!数论就像"是的,那很好......但我有99%的情况下都要做真正的工作,抱歉".然后,正如你所说,"突然",数论超级有用.它不像锤子,而是对很多东西都很有用.相反,它就像一把手术刀对于少数事情非常有用*. (8认同)
@SamKellett如果你使用了正确数量的括号并得到了"0x9e3779b97f4a7800",它会工作得更好 (5认同)
由于Python的浮点数没有足够的精度,因此上面的64位黄金比例不正确.实际结果应为"0x9e3779b97f4a7c15". (5认同)
@kennytm你不是说[`0x9e3779b97f4a7c16`](http://coliru.stacked-crooked.com/a/c977420af344e736)吗？我的意思是，只有1折。 (2认同)

Answer 2

看看Bob Jenkins从1997年开始的DDJ文章.神奇常数("黄金比例")解释如下:

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