在boost::hash_combine中的魔数

Question

boost::hash_combine模板函数接受一个指向哈希（称为seed）和一个对象v的引用。根据文档，它通过以下方式将seed与v的哈希组合起来：

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

我可以看出这是确定性的。我明白为什么要使用异或操作。

我猜加法有助于将类似的值映射到远离彼此的位置，这样探测哈希表就不会崩溃，但是有人能解释一下魔术常数是什么吗?

- Fred Foo

---

鉴于许多计算机上整数旋转的成本与移位相当，将表达式转换为以下形式是否有任何好处：<code> seed ^= hash_value(v) + 0x9e3779b9 + rotl(seed, 6) + rotr(seed, 2); </code> - John Yates

Answer 1

魔数应该是32个随机位，每个位都有同样的概率是0或1，并且位之间没有简单的相关性。找到这样一串位的常见方法是使用一个无理数的二进制展开；在这种情况下，该数字是黄金比例的倒数：

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

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

- Mike Seymour

---

好的！当数论突然变得实用时，我很喜欢它 :) - Fred Foo

我喜欢你使用“突然”的方式——非常适当！在99%的情况下，数论就像是“好吧，这很好……但我有真正的工作要做，对不起”。然后，就像你所说，“突然”，数论变得超级超级有用。它不像锤子那样对许多事情都相当有用。相反，它像手术刀一样，对于少数几件事情来说，非常非常有用。 - corsiKa

@SamKellett如果您使用正确数量的括号并获得0x9e3779b97f4a7800，效果会更好。 - Barry

由于Python的浮点数精度不足，上述64位黄金比率是不正确的。实际结果应该是 0x9e3779b97f4a7c15。 - kennytm

@kennytm 你是不是指的是0x9e3779b97f4a7c16？我的意思是，只相差1。 - bit2shift

Answer 2

请看1997年Bob Jenkins在DDJ杂志上发表的文章《关于哈希函数》。其中所解释的“黄金比例”（magic constant）如下：

黄金比例确实是一个任意值。它的作用是避免将所有零映射到所有零。

- NPE

Answer 3

使用Python获取这个神奇数字：

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

- Peng