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

Question

目前Boost的hash_combine函数可以输出32位无符号整数（准确的说是size_t）。一些参考文献。

http:/www.boost.orgdoclibs1_43_0dochtmlhashreference.html#boost.hash_combine

http:/www.boost.orgdoclibs1_43_0dochtmlhashcombine.html

在boost::hash_combine中的魔法数字。

我想探讨一下如何创建64位版本的hash_combine。

第一件事是在64位中得到黄金比率或任何其他无理数。

第二部分是使用shifts。这一部分相当棘手，我想问一下是否有使用shift来获得hash值的最佳实践或指南？或者像原代码一样选择移位。

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

是完全随机的？

另外，如何评估 hash_combine 以确保它不会产生比原始哈希函数更多的碰撞。hash_value?

Answer 1

如果你只想要一个能将2个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的源代码和许可协议，以便自己决定)

Answer 2

阅览 http:/burtleburtle.netbobhashdoobs.html。 以获取一些关于哈希函数设计的基本信息，以及本手册中的其他文章。http:/burtleburtle.netbobhash。 更详细的信息。城市哈希值 被测试使用 http:/code.google.compsmhasher。，你可以大概测试你的 hash_combine 使用相同的测试套件。

虽然我不是哈希方面的专家，但最近的哈希函数的设计让我相信，2-shift技术可以提高我们的效率。hash_combine() 使用的已经不是最先进的，还可以改进。

Answer 3

boost::hash_combine 并不是完全随机的，它甚至不是良好的分布或 特别好.

组合两个哈希值的好方法是首先确保两个哈希值分布良好，然后你可以用xor组合两个哈希值。为了确保它们分布良好，使用 良好的整数哈希函数.

把它放在一起，你可能会有。

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) {
  return hash(v)^seed;
}

如果哈希值的分布对你的目的来说不够好 就把值加倍哈希，也许像这样。hash(hash(v))^seed