C++ 哈希限制

Question

如 cppreference.com 中所述

The probability of h(a)==h(b) for a!=b should approach 1.0/std::numeric_limits<std::size_t>::max().

我想创建一个哈希表 (a, b) , 其中(a, b) == (b, a) (无序对)，所以我的哈希函数是:

struct hash_pair {
  template<class T>
  std::size_t operator()(std::pair<T, T> const& p) const
  {
     std::hash<T> h;
     return std::hash<std::size_t>(h(p.first) + h(p.second));
  }
};

假设h(ti)和 std::hash<std::size_t>满足要求，将hash_pair也满足吗？

进一步思考后:

(一些额外的细节)

• p.first != p.second以我的用例为前提。
• T将是 std::size_t在大多数情况下，它的哈希值就是它自己，所以 h(n) == n因此 P(n1 == n2)什么时候n1 != n2是0 .
• 由于和是可交换的，hash(pair(n1, n2)) == hash(pair(n2, n1)) ，这是有意的。

所以我们只有两种情况，两对可以不同，当它们只有一个共同元素时，或者当没有共同元素时:

 P1 = P(n1 + n2 == n1 + n3) = P(n2 == n3) = 0 // Because n2 != n3
 P2 = P(n1 + n2 == n3 + n4) = ? // n1 != n3 and n2 != n4

所以我的问题被简化为计算P(none_in_common) * P(n1 + n2 == n3 + n4) . P(none_in_common)是用例特定的(在我的情况下这个概率可能很高)，但是，P2 呢？ ？有什么帮助吗？

注意:我的问题不是这里其他类似问题的重复，因为我问的是我提议的哈希函数的统计属性，而不是如何做。

Answer 1

它不满足该属性，因为最终的概率计算与哈希概率无关。它必须独立计算，并且根据我的理解，您不能对其应用任何代数性质。

四个不同数字给出相同哈希值的概率，来自 this question我也做了，用更数学的方法是(n 是每个数字的域):

 (2 * n^2 + 4 * n + 3) / (3 * (n + 1) ^ 3)

它给出了大约 3.61e-20，这非常完美(比散列单个数字差 1.5 倍，但概率仍然可以忽略不计)。这必须乘以拥有两对完全不同数字的概率。

注意 我的第一句话错了。由于模运算溢出，如果哈希函数本身是均匀分布的，则哈希和是均匀分布的。