boost::hash_combine 中的幻数

2021-12-06 00:00:00 algorithm hash c++ boost magic-numbers

boost::hash_combine 模板函数引用一个哈希(称为seed)和一个对象v.根据文档,它将seedv 的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.

相关文章