如何创建一个64位输出的好的hash_combine（受boost :: hash_combine启发）

Question

目前Boost库中有一个hash_combine函数，它输出32位无符号整数（确切地说是size_t）。以下是一些参考资料：

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/reference.html#boost.hash_combine

http://www.boost.org/doc/libs/1_43_0/doc/html/hash/combine.html

boost::hash_combine中的魔法数字

我想探索如何创建64位版本的hash_combine。

首先要获取黄金比例或其他64位的无理数。

第二部分是使用移位操作。这部分相当棘手，我想问一下是否有最佳实践或指南来使用移位操作获取哈希值？还是选择像原始代码一样的移位数：

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

这是完全随机的吗？

另外，如何评估hash_combine的输出，以确保它不会比原始哈希函数hash_value创建更多的碰撞？

- Viet

---

2^64/φ 等于 0x9E3779B97F4A7C15。 - Kerrek SB

谢谢Kerrrek。找到值不是问题。我感兴趣的是是否有任何规则或最佳实践来使用移位和加法，就像在boost::hash_combine中看到的那样。还是选择移位和加法完全是随机的。 - Viet

我认为你应该提交一个错误报告。 - kennytm

嗨Kenny，我在询问能够让我理解后能够编写代码的概念。 - Viet

Answer 1

如果你只想要一个将两个64位值哈希为一个值的hash_combine函数，并且不需要为字符串创建新的哈希函数，那么你可以从CityHash中获取一小段代码来使用，类似于这样（假设size_t是一个64位无符号整数，添加你喜欢的预处理器或模板技巧来验证）：

template <class T> inline void hash_combine(std::size_t& seed, const T& v)
{
    std::hash<T> hasher;
    const std::size_t kMul = 0x9ddfea08eb382d69ULL;
    std::size_t a = (hasher(v) ^ seed) * kMul;
    a ^= (a >> 47);
    std::size_t b = (seed ^ a) * kMul;
    b ^= (b >> 47);
    seed = b * kMul;
}

(我认为在这里和其他地方复制这段代码是可以的，因为它不构成CityHash代码的“重要部分”，但请查看CityHash源代码和许可协议，自行决定)

- Scott Howlett

---

你的神奇常量不是Kerred提到的“0x9E3779B97F4A7C15”，那它从哪里来的？ - v.oddou

Answer 2

请阅读http://burtleburtle.net/bob/hash/doobs.html，获取有关哈希函数设计的基本信息，并阅读http://burtleburtle.net/bob/hash/中的其余文章以获取更详细的信息。使用http://code.google.com/p/smhasher/测试了CityHash，您可以使用相同的测试套件测试您的hash_combine。

尽管我不是哈希方面的专家，但最近哈希函数的设计使我相信，2次移位技术提高的hash_combine()已经不再是最先进的技术，可以进行改进。

- Jeffrey Yasskin

Answer 3

boost::hash_combine 并不是完全随机的，甚至不太分散或特别好。

将两个哈希值组合成一个好的方法是首先确保两个哈希值都很好地分散，然后通过异或操作将它们组合在一起。为了确保它们分散良好，使用好的整数哈希函数。

把所有的东西放在一起，你可能会得到：

uint64_t xorshift(const uint64_t& n,int i){
  return n^(n>>i);
}
uint64_t hash(const uint64_t& n){
  uint64_t p = 0x5555555555555555; // pattern of alternating 0 and 1
  uint64_t c = 17316035218449499591ull;// random uneven integer constant; 
  return c*xorshift(p*xorshift(n,32),32);
}
uint64_t hash_combine(const uint64_t& seed, const uint64_t& v) {
  uint64_t c = 17316035218449499591ull;// random integer constant;
  return hash(v)^(seed+c);
}

如果哈希分布对您的目的不够好，只需对值进行双重哈希，可能像这样：hash(hash(v))^seed。

- Wolfgang Brehm

---

这段代码在编程中有两个重要的用例失败： 1）排列。您提出的hash_combine无法区分散列值的不同顺序：hash_combine（hash_combine（0,1），2）== hash_combine（hash_combine（0,2），1）。例如，我需要在光线追踪任务中使用哈希函数来哈希光线击中的对象的顺序。 2）零保留。hash_combine（0,0）== 0。这非常危险，因为0是最常见的值。所提出的哈希函数无法区分序列（0）和（0,0）以及（0,0,0）。这些缺陷结合起来给出了hash（1,0,2）== hash（2,1）== hash（0,0,0,1,2）等。 - Anton Sukhinov

你说Boost的hash_combine函数不好，但实际上它并没有这些缺陷。 - Anton Sukhinov

@AntonSukhinov 这是真的。有几种解决方案，可以在哈希位置i'中添加。 return hash(v*(2*i+1))^seed; ，在这种情况下将哈希函数应用于两倍宽度的整数，即unsigned __int128`，由值和种子组成，每次乘以3，返回之前再应用另一个弱哈希函数，我认为在哈希中添加随机常量可能是最经济的。 - Wolfgang Brehm