java - 哈希时不可避免的碰撞？

Question

如果我创建一个新的 Map:

Map<Integer,String> map = new HashMap<Integer,String>();

然后我调用 map.put() 多次，每次调用一个唯一的键，比如说，一百万次，是否会发生冲突，或者如果 key 是唯一的？

Answer 1

如果 key 是唯一的，则散列法不能保证不会发生冲突。事实上，唯一需要的是相等的对象具有相同的哈希码。碰撞次数决定了检索的效率(碰撞越少，接近 O(1)，碰撞越多，接近 O(n))。

对象的哈希码是什么取决于它是什么类型。例如，一个字符串的默认哈希码是

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

这必然将字符串的复杂性简化为一个数字——绝对有可能用两个不同的字符串达到相同的哈希码，尽管这种情况非常罕见。

如果两个事物散列为同一事物，则 hashmap 使用 .equals 来确定特定键是否匹配。这就是为什么同时重写 hashCode() 和 equals() 并确保相等的事物具有相同的哈希码非常重要。