增强中的神奇数字: : hash_merge

boost::hash_combine模板函数接受对散列(称为 seed)和对象 v的引用。根据 医生，它将 seed与 v的 hash 结合在一起

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

我知道这是确定性的，我知道为什么使用 XOR。

我敢打赌，这个加法有助于将相似的值广泛地映射到不同的地方，这样探测散列表就不会崩溃，但是谁能解释一下这个神奇的常量是什么呢？

26680 次浏览
小开
最佳答案

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

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.

小开

Take a look at the DDJ article by Bob Jenkins from 1997. The magic constant ("golden ratio") is explained as follows:

The golden ratio really is an arbitrary value. Its purpose is to avoid mapping all zeros to all zeros.

小开

using python to get this mgic number:

from math import sqrt
phi = (1 + sqrt(5)) / 2
hex(int(2**32/phi))

提交答案