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.
相关文章