问boost::hash_combine中的幻数
EN

Stack Overflow用户

提问于 2011-02-10 02:14:32

回答 1查看 24.2K关注 0票数 103

boost::hash_combine模板函数接受对散列(称为seed)和对象v的引用。根据docs的说法，它通过以下方式将seed与v的散列结合在一起

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

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

我敢打赌，这个加法有助于将相似的值映射得很远，这样探测哈希表就不会崩溃，但是有人能解释一下魔力常数是什么吗？

回答已采纳

发布于 2011-02-10 02:32:40

幻数被认为是32个随机比特，其中每个比特都可能是0或1，并且比特之间没有简单的相关性。查找此类位字符串的一种常见方法是使用无理数的二进制展开；在这种情况下，该数字是黄金比例的倒数：

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

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

票数 153

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/4948780

复制

相似问题

问boost::hash_combine中的幻数EN