一对基本类型的良好哈希函数

Question

我正在试图为两个原始类型的std :: pair找出一个好的哈希函数.这就是我现在实现它的方式:

template<typename T, typename U>
std::size_t operator()(const std::pair<T,U> &rhs) const
{
    return stdext::hash_value<T>(rhs.first) ^ stdext::hash_value<U>(rhs.second);
}

它似乎工作,即使我有两对,如(1,2)和(2,1)(数字翻转).它们生成相同的哈希值,但值仍然成功插入到哈希映射中.有什么想法吗？

Answer 1

一般来说,散列容器总是必须处理这种情况(散列冲突).他们可以使用几种方法,如链接和探测,其中任何一种方法都可能会损害性能.

相反,我建议使用boost::hash_combine以这种方式组合散列它们交换first并且second不生成相同的散列.

Answer 2

假设 stdext::hash_value 为第一个和第二个提供了良好的哈希值分布，如果您不期望镜像对的发生率不成比例地高（例如 (1,2) 和 ( 2,1))。如果您的数据集确实需要很多这样的数据，您可能会考虑调整哈希函数以强制它们不同。例如，反转第一个哈希值：

return ~stdext::hash_value<T>(rhs.first) ^ stdext::hash_value<T>(rhs.second);

我提到这一点只是因为您表达了对镜像对的担忧。如果您的输入在这方面接近随机，那么 ^ 应该没问题。请记住，目标是尽量减少碰撞，而不是完全避免碰撞。