我已经在其他帖子中读到，这似乎是组合哈希值的最佳方法。能否有人将其分解并解释为什么这是最佳方法？
template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
编辑：另一个问题只询问魔数，但我想了解整个函数，而不仅仅是这一部分。
3个回答
59
说它是“最好的”是有争议的。
说它“好”，甚至“非常好”，至少在表面上很容易接受。
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
seed是hasher或此算法的先前结果。
^=意味着左侧和右侧的位都会更改结果的位。
hasher(v)被认为是对v的一种体面的哈希。但其余部分是为了防止它不是一个体面的哈希。
0x9e3779b9是一个32位值(如果size_t是64位，则可以将其扩展为64位), 它包含一半0和一半1。基本上，它是通过近似特定无理常数作为二进制小数点值来生成的随机0和1序列。这有助于确保如果哈希返回错误的值，我们仍然可以在输出中获得1和0的扩散。
(seed<<6) + (seed>>2) 是传入seed的位重排。想象一下没有
0x常数。假设哈希器几乎每个传入的v都返回常量0x01000。现在，种子的每个位都分布在下一次迭代的哈希中，在此期间它再次分布。
seed ^= (seed<<6) + (seed>>2) 0x00001000经过一次迭代后变为0x00041400，然后是0x00859500。随着您重复此操作，任何集合位都会在输出位上“扩散”。最终，右侧和左侧的位会碰撞，并且Carry会将集合位从“偶数位置”移动到“奇数位置”。随着组合操作对种子操作进行递归，相对于输入种子的位相关性以快速而复杂的方式增长。添加会导致进位，使事情更加模糊。
0x常数添加了一堆伪随机位，使得无聊的哈希值被组合后占据了超过几个位的哈希空间。它由于加法不对称（将
"dog"和"god"的哈希组合给出不同的结果），它处理无聊的哈希值（将字符映射为其ascii值，这仅涉及微调少量位）。并且，它速度相当快。在其他情况下，比较慢的加密强哈希组合可能更好。我天真地认为，使移位成为偶数和奇数移位的组合可能是个好主意（但是也许加法将偶数位从奇数位移动使该问题减轻:在3次迭代后，传入的单个种子位将碰撞并添加而导致进位）。
这种分析的缺点是只需要一次错误即可使哈希函数变得非常糟糕。指出所有好处并没有太大帮助。因此，使其现在成为好方法的另一件事是它相当有名并且在一个开源存储库中，我没有听到任何人指出它为什么不好。
- Yakk - Adam Nevraumont
6
有没有简单的方法可以看出
seed -> (seed<<6) + (seed>>2) 是双射的？ - Martin R7判断所提到的变换是否双射并不容易，因为它并非如此。在16位域中有192个冲突，在24位域中有48960个……这是假设种子和结果都具有相同的位大小的情况下。 - rAndom69
@MartinR 对于32位值的
hash_combine(x,0)，存在1346300007个冲突。 - Wolfgang Brehm2@WolfgangBrehm：我所说的是关于这个答案中已经被删除的语句“它对任何种子输入都是双射”的评论。 - Martin R
1@MartinR 哦，好的，无论如何，我刚刚为我的答案计算了一下，大约花了一个小时，觉得你可能会感兴趣 :D - Wolfgang Brehm
请给沃尔夫冈在我的回答下面点赞。他的回答更深入。 - Yakk - Adam Nevraumont
58
这并不是最好的，让我惊讶的是它甚至不是特别好。主要问题在于分布不均，这不完全是boost::hash_combine本身的错，而是与像std::hash这样分布不良的哈希函数一起使用时出现的问题，而std::hash通常实现为恒等函数。
图2：在一个随机的32位数字中改变单个位的效果对boost::hash_combine的结果的影响。x轴是输入位（两次32位，首先是新哈希值，然后是旧种子），y轴是输出位。颜色表示依赖程度。
为了证明事情会变得多么糟糕，以下是在使用hash_combine时，对于32x32网格上的点(x,y)的碰撞情况，和使用std::hash的情况：
# hash_combine(hash_combine(0,x₀),y₀)=hash_combine(hash_combine(0,x₁),y₁)
# hash x₀ y₀ x₁ y₁
3449074105 6 30 8 15
3449074104 6 31 8 16
3449074107 6 28 8 17
3449074106 6 29 8 18
3449074109 6 26 8 19
3449074108 6 27 8 20
3449074111 6 24 8 21
3449074110 6 25 8 22
对于一个良好分布的哈希函数，统计上不应该存在冲突。可以使用更多级联的 hash_combine（例如使用多个更分散的异或移位）来保留熵并扩散更多，也可以使用比特旋转而不是比特移位来改进。但实际上，你应该首先使用好的哈希函数，然后在此之后使用简单的异或即可组合种子和哈希值，如果哈希值编码了序列中的位置。为了方便实现，以下哈希函数不编码位置。为了使 hash_combine 不满足交换律，任何非交换双射操作都足够。我选择了一种不对称二进制旋转，因为它很便宜。
#include <limits>
#include <cstdint>
template<typename T>
T xorshift(const T& n,int i){
return n^(n>>i);
}
// a hash function with another name as to not confuse with std::hash
uint32_t distribute(const uint32_t& n){
uint32_t p = 0x55555555ul; // pattern of alternating 0 and 1
uint32_t c = 3423571495ul; // random uneven integer constant;
return c*xorshift(p*xorshift(n,16),16);
}
// a hash function with another name as to not confuse with std::hash
uint64_t distribute(const uint64_t& n){
uint64_t p = 0x5555555555555555ull; // pattern of alternating 0 and 1
uint64_t c = 17316035218449499591ull;// random uneven integer constant;
return c*xorshift(p*xorshift(n,32),32);
}
// if c++20 rotl is not available:
template <typename T,typename S>
typename std::enable_if<std::is_unsigned<T>::value,T>::type
constexpr rotl(const T n, const S i){
const T m = (std::numeric_limits<T>::digits-1);
const T c = i&m;
return (n<<c)|(n>>((T(0)-c)&m)); // this is usually recognized by the compiler to mean rotation, also c++20 now gives us rotl directly
}
// call this function with the old seed and the new key to be hashed and combined into the new seed value, respectively the final hash
template <class T>
inline size_t hash_combine(std::size_t& seed, const T& v)
{
return rotl(seed,std::numeric_limits<size_t>::digits/3) ^ distribute(std::hash<T>{}(v));
}
在将种子组合成计算哈希的顺序之前，需要将其旋转一次，以使计算哈希的顺序变得相关。
boost 的 hash_combine 需要少两个操作，并且更重要的是没有乘法，实际上它快了约 5 倍，但在我的机器上每个哈希大约需要 2 个周期，所以建议的解决方案仍然非常快，而且在使用哈希表时很快就能收回成本。在 1024x1024 网格上有 118 个碰撞（与 boosts 的 hash_combine + std::hash 相比的 982017 个），与预期的良好分布的哈希函数数量相同，这是我们所能要求的。
即使与良好的哈希函数一起使用，boost::hash_combine 也不是理想的选择。如果所有熵都在种子中，那么其中一些将会丢失。对于 boost::hash_combine(x,0)，存在 2948667289 种不同的结果，但应该有 4294967296 种。
总之，他们试图创建一个同时进行组合和级联的哈希函数，并且速度快，但最终得到的结果只是足够好，以至于不会立即被识别为不好。但它确实很快。
- Wolfgang Brehm
28
2好的回答。这让我怀疑为什么每个人都在使用这个函数而不是更好的东西，所以我花了几个小时在一个洞里研究这个问题。实际上，std::hash并没有将良好的位级联作为实现需要具有的属性列出来，因此虽然您正确地指出这是一种普遍意义上较差的哈希函数，但它实际上完全满足std::hash设定的要求。例如，size_t的std::hash实现通常只是恒等函数-这是完全可以的。 - Hannes Landeholm
3是的，很明显boost hash_combine是一个糟糕的哈希函数，因为你可以找到这些微不足道的碰撞，并且它显然不能满足std::hash operator()要求5：“对于两个不相等的参数k1和k2，std::hash<Key>()(k1) == std::hash<Key>()(k2)的概率应该非常小，接近于1.0/std::numeric_limitsstd::size_t::max()。”当我看到这个实现时，我一直怀疑这一点。当我看到这种特制的业余哈希函数的使用是如此广泛时，我的下巴都掉了。 - Hannes Landeholm
1然后，简单的异或运算就足够了。但是，这似乎与后面的答案相矛盾，您指出应该采取一些措施确保您的hash_combine不会对(x,y)和(y,x)执行相同的操作。最好将此部分编辑或更改，以免读者错过非常重要的细微差别。 - Milo Brandt
1我不理解这个图形和表格。这些图像轴代表什么？这些颜色代表什么？这是两个图像还是一个矩形图像？关于表格：x和y代表什么，确切地说？请尽量简单易懂地回答。 - einpoklum
1
hash 函数已经定义，但在所呈现的源代码中没有使用。它使用了 std::hash。为什么？ - plasmacel显示剩余23条评论
1
ROTL适用于VS Studio（您可以轻松推导ROTR）。 （实际上，这是回复@WolfgangBrehm的内容。）
原因：诱使编译器发出ror和/或rol指令的标准技巧在VS中会出现错误：error C4146：对无符号类型应用一元减运算符，结果仍为无符号。
因此...我通过将(-c)替换为(T(0)-c)来解决编译器错误，但这不会被优化。
添加（MS特定的）专业化可解决此问题，如发出的优化汇编代码所示。
#include <intrin.h> // and some more includes, see above...
template <typename T> // default template is not good for optimisation
typename std::enable_if<std::is_unsigned<T>::value, T>::type
constexpr rotl(const T n, const int i)
{
constexpr T m = (std::numeric_limits<T>::digits - 1);
const T c = i & m;
//return (n << c) | (n >> (-c) & m);
return (n << c) | (n >> (T(0) - c) & m);
}
template<>
inline uint32_t rotl(const uint32_t n, const int i)
{
constexpr int m = (std::numeric_limits<uint32_t>::digits - 1);
const int c = i & m;
return _rotl(n, c);
}
template<>
inline uchar rotl(const uchar n, const int i)
{
constexpr uchar m = (std::numeric_limits<uchar>::digits - 1);
const uchar c = i & m;
return _rotl8(n, c);
}
template<>
inline ushort rotl(const ushort n, const int i)
{
constexpr uchar m = (std::numeric_limits<ushort>::digits - 1);
const uchar c = i & m;
return _rotl16(n, c);
}
template<>
inline uint64_t rotl(const uint64_t n, const int i)
{
constexpr int m = (std::numeric_limits<uint64_t>::digits - 1);
const int c = i & m;
return _rotl64(n, c);
}
- Jan
2
我认为这不是stackoverflow应该工作的方式，恐怕答案需要是完整的答案。
(T(0) -c) 正是应该做的，然而，它仍然被 clang、gcc 和 icc 所识别，但似乎确实没有被 msvc 所识别，但我们谈论的是节省一两个易于流水线化的微指令，我不会担心它。 - Wolfgang Brehm网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
boost::hash_combine，而采用http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html。 - Maxim Egorushkin