boost :: hash_combine中的幻数

Question

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

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

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

我敢打赌，这种加法有助于将相似的值分开大范围地映射，因此探测哈希表不会崩溃，但是有人可以解释魔术常数是什么吗？

Answer 1

幻数应该是32个随机位，其中每个均等可能为0或1，并且位之间没有简单的相关性。查找此类字符串的常见方法是使用无理数的二进制扩展。在这种情况下，该数字是黄金分割率的倒数：

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

因此，“随机地”包含此数字会更改种子的每一位；如您所说，这意味着连续的值将相距很远。包括旧种子的移位版本在内，可以确保即使hash_value()值的范围很小，差异也将很快分散到所有位中。