java - 什么是哈希碰撞

Question

HashMap 中的 Hash Collision 或 Hashing Collision 并不是一个新话题，我已经看到几个博客和讨论板解释如何产生 Hash Collision 或如何以模棱两可和详细的方式避免它。我最近在一次采访中遇到了这个问题。我有很多事情要解释，但我认为准确地给出正确的解释真的很难。抱歉，如果我的问题在这里重复，请将我带到准确的答案:

1. Hash Collision 到底是什么 - 它是一个特征，还是一个错误完成但最好避免的常见现象？
2. 究竟是什么导致了哈希冲突 - 自定义类的 hashCode() 方法的错误定义，或者不完全覆盖 equals() 方法而不覆盖单独使用 hashCode() 方法，或者它不是由开发人员决定的，许多流行的 java 库也有可能导致哈希冲突的类？
3. 发生哈希冲突时是否出现任何错误或意外情况？我的意思是我们有什么理由应该避免哈希冲突？
4. Java 是否在对象初始化期间为每个类生成或至少尝试生成唯一的哈希码？如果不是，仅依靠 Java 来确保我的程序不会遇到 JRE 类的哈希冲突是否正确？如果不正确，那么如何避免以 String 等最终类作为键的散列映射的散列冲突？

如果您能分享您对其中一个或所有问题的答案，我将不胜感激。

Answer 1

What exactly is Hash Collision - is it a feature, or common phenomenon which is mistakenly done but good to avoid?

这是一个功能。它源于 hashCode 的性质:从大值空间到小得多的值空间的映射。出于设计和意图，将会发生碰撞。

What exactly causes Hash Collision - the bad definition of custom class' hashCode() method,

糟糕的设计会让事情变得更糟，但它在这个概念中是普遍存在的。

OR to leave the equals() method un-overridden while imperfectly overriding the hashCode() method alone,

没有。

OR is it not up to the developers and many popular java libraries also has classes which can cause Hash Collision?

这真的没有意义。哈希迟早会发生碰撞，而糟糕的算法会使碰撞发生得更早。就是这样。

Does anything go wrong or unexpected when Hash Collision happens?

如果哈希表写得很好，就不会。哈希冲突仅意味着哈希代码不是唯一的，这会让您调用 equals()，重复越多性能越差。

I mean is there any reason why we should avoid Hash Collision?

您必须权衡计算的便利性和值(value)的传播。没有单一的黑白答案。

Does Java generate or atleast try to generate unique hasCode per class during object initiation?

没有。 “唯一哈希码”在术语上是自相矛盾的。

If no, is it right to rely on Java alone to ensure that my program would not run into Hash Collision for JRE classes? If not right, then how to avoid hash collision for hashmaps with final classes like String as key?

这个问题毫无意义。如果您使用的是 String，那么您对哈希算法没有任何选择，而且您还在使用一个类，其 hashCode 已被专家使用了二十年或更长时间。