C++ unordered_map自定义哈希函数冲突

Question

下面的代码用于计算平面中不同斜率值的线数。建议使用一对x轴和y轴位置来表示直线的斜率，b/c直接计算除法y/x会有float精度问题。所有 x 和 y 位置都是整数。

虽然方法 I 正在测试代码中，但仍有一些我不清楚的地方:

1) 对于方法 I，对 {5, 3} 和 {3, 5} 将具有相同的哈希值 (x ^ y)，但是这两条线具有不同的斜率!为什么它不会导致考虑两条线具有相同斜率的问题？还是哈希函数值只决定了要哈希的槽，而比较实际pair值的等价性来决定是否算作相等？

2) 由于对 {5, 3} 和 {3, 5} 将被散列到同一个槽中，并且还有许多其他类似的冲突，如 {a, b} 和 {b, a}。为什么碰撞哈希表仍然产生正确的最终结果？

3) 负整数的 XOR 没问题，对吧？有没有我们通常在这里使用的更好的哈希函数来避免高冲突？

struct hashfunc
{
    //Method I:
    size_t operator() (const pair<int,int>& l) const
    { return l.first ^ l.second; }   

    //Method II is WRONG: can NOT left shift negative int!!
    size_t operator() (const pair<int, int>& l) const {
         return l.first << 32 | l.second; 
    }
};

unordered_map< pair< int,int >, int, hashfunc> lines;

Answer 1

在输出小于组合输入的任何函数中，完全没有碰撞是不可能实现的。正确性不依赖于没有碰撞，只依赖于性能。即使使用始终返回零的散列函数，您也应该获得正确的结果(尝试一下)。

the hash function value only determines the slot to be hashed, while comparing the equivalence of actual pair value determines whether to count them as equal?

正确。

通常的方法是以不可预知的方式将数字混合在一起，比如

choose distinct primes a,b,c
hash(x,y) = (a*x + b*y) % c

参见例如https://en.wikipedia.org/wiki/Universal_hashing#Hashing_integers