7

我试图为两个原始类型的 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) （数字翻转），它似乎也能工作。它们生成相同的哈希值，但这些值仍然成功插入到哈希映射中。有什么想法吗？

4

5 回答 5

5

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

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

于 2013-05-09T23:13:31.170 回答
2

这是hash_combine基于当前版本的 boost 文档的实现：( http://www.boost.org/doc/libs/1_53_0/doc/html/hash/reference.html#boost.hash_combine )

template<typename T> void hash_combine(size_t & seed, T const& v) {
  seed ^= stdext::hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

你会这样使用它：

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

我实际上不能保证这个函数背后的逻辑，但它看起来比这里提到的大多数选项更可靠。

于 2013-05-10T00:22:38.267 回答
1

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

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

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

于 2013-05-09T22:10:07.263 回答
0

正如其他人所指出的，散列函数只影响散列表的效率，而不影响正确性。仅当镜像对频繁出现时，您的功能才会很糟糕。由于在某些应用程序中这可能是一个问题，交换一个哈希值的上半字和下半字然后异或是合理的。许多其他方案是可能的，但这个方案非常快速和简单。

template<typename T, typename U>
std::size_t operator()(const std::pair<T,U> &rhs) const
{
    const int h = sizeof(size_t) * 8 / 2;
    size_t a = stdext::hash_value<T>(rhs.first);
    return ((a << h) | (a >> h)) ^ stdext::hash_value<U>(rhs.second);
}
于 2013-05-09T23:35:32.310 回答
0

只是为了好玩，这是另一种简单且直接解决问题案例的方法，具体来说：

  • 如果两者first和second相同，则返回它们的公共哈希值
  • 否则，它会对这些值进行异或，但是：
    • 为了防止 h(a, b) 与 h(b, a) 碰撞，它使用 a < b 在 h(a)^h(b) 和 h(a)^h(~b) 之间进行选择

执行：

1 template<typename T, typename U>
2 std::size_t operator()(const std::pair<T,U> &rhs) const
3 {
4     std::size_t a = stdext::hash_value<T>(rhs.first);
5     return rhs.first == rhs.second ? a :
6            a ^ (rhs.first < rhs.second ? stdext::hash_value<U>(rhs.second)
7                                        : stdext::hash_value<U>(~rhs.second));
8 }

不过说真的，我建议遵循 Mark B 的建议并使用 boost::hash_combine - 减少分支可能会提高速度。

于 2013-05-10T02:00:08.390 回答