c++ - 如何创建具有 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

Magic number in boost::hash_combine

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

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

第二部分是使用轮类。这部分相当棘手，我想问一下是否有关于使用移位获取哈希值的最佳实践或指南？或者像原来的代码一样选择类次:

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 源代码和许可协议(protocol)以自行决定)