c++ - 一对碰撞几率很低的整数的最小哈希函数是什么？

Question

这是我目前所拥有的:

struct pairhash {
public:
  inline std::size_t operator()(const std::pair<int, int> &c) const
  {
     int x = c.first;
     int y = c.second;
     return ((x+y)*(x+y+1)/2 + y); // Cantor's enumeration of pairs
  }
};

我需要使用这个哈希函数，这样我就可以像这样将这对整数放入 unordered_set 中:

std::unordered_set< std::pair<int, int>,  pairhash> mySet;

编辑:忘记从这对中获取坐标。更新了代码。 编辑:删除了模板代码 - 错误地添加了它。

编辑:根据 SO 上的另一个类似答案更改了函数，与 Cantor 的对枚举相关: hash function providing unique uint from an integer coordinate pair

编辑:无碰撞不是必需的(感谢 Petr)。

Answer 1

如果您打算将它与unordered_set 一起使用，则不需要哈希函数是无冲突的。 (以及大多数其他容器和算法)。此外，哈希表和哈希函数的一般概念是它们允许冲突，它们只是希望冲突很少发生。

cppreference says about the requirements for hashing :

5. For two different parameters k1 and k2 that are not equal, the probability that std::hash<Key>()(k1) == std::hash<Key>()(k2) should be very small, approaching 1.0/std::numeric_limits<size_t>::max().