boost::hash_combine 中的幻数

问题描述

boost::hash_combine 模板函数引用一个哈希(称为seed)和一个对象v.根据文档，它将seed 与v 的hash 组合起来，由

The boost::hash_combine template function takes a reference to a hash (called seed) and an object v. According to the docs, it combines seed with the hash of v by

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

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

I can see that this is deterministic. I see why a XOR is used.

我敢打赌，添加有助于将相似的值映射得相距甚远，因此探查哈希表不会崩溃，但有人可以解释魔术常数是什么吗?

I bet the addition helps in mapping similar values widely apart so probing hash tables won't break down, but can someone explain what the magic constant is?

推荐答案

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

The magic number is supposed to be 32 random bits, where each is equally likely to be 0 or 1, and with no simple correlation between the bits. A common way to find a string of such bits is to use the binary expansion of an irrational number; in this case, that number is the reciprocal of the golden ratio:

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

所以包括这个数字随机"改变种子的每一位；正如您所说，这意味着连续的值将相距甚远.包括旧种子的移位版本可以确保，即使 hash_value() 的值范围很小，差异也会很快扩散到所有位.

So including this number "randomly" changes each bit of the seed; as you say, this means that consecutive values will be far apart. Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly small range of values, differences will soon be spread across all the bits.

这篇关于boost::hash_combine 中的幻数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持跟版网！