boost::hash_combine
模板函数采用对散列(称为seed
)和对象v
的引用。根据docs , 它结合了 seed
和 v
by
seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
我可以看到这是确定性的。我明白为什么要使用 XOR。
我敢打赌,这个加法有助于将相似的值映射得很远,这样探测哈希表就不会崩溃,但有人能解释一下魔法常数是什么吗?
最佳答案
魔数(Magic Number)应该是 32 个随机位,其中每个位同样可能是 0 或 1,并且位之间没有简单的相关性。找到一串这样的位的常用方法是使用无理数的二进制展开;在这种情况下,该数字是黄金比例的倒数:
phi = (1 + sqrt(5)) / 2
2^32 / phi = 0x9e3779b9
因此,“随机”包含这个数字会改变种子的每一位;正如您所说,这意味着连续值将相距甚远。包括旧种子的移位版本可确保即使 hash_value()
具有相当小的值范围,差异也会很快扩散到所有位。
关于c++ - boost::hash_combine 中的魔数(Magic Number),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4948780/