在升压幻数:: hash_combine [英] Magic number in boost::hash_combine
问题描述
在的boost :: hash_combine
模板函数需要引用一个哈希(称为籽
)和对象 v
。根据<一href="http://www.boost.org/doc/libs/release/doc/html/hash/reference.html#boost.hash_combine">docs,它结合了籽
与散v
按
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()
有一个相当小的范围值,差异将很快为s $ P $所有垫位。
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.
这篇关于在升压幻数:: hash_combine的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!