C++ unordered_map 自定义散列函数冲突

Question

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

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

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

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

3) 负整数的 XOR 没问题，对吧？有没有我们这里常用的更好的hash函数来避免高碰撞？

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

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

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

C++ unordered_map 自定义散列函数冲突

C++ unordered_map self defined hash function collision

c++

hash

unordered-map

xor