什么是哈希碰撞
What Exactly is Hash Collision
HashMap 中的 Hash Collision 或 Hashing Collision 并不是一个新话题，我已经看到几个博客和讨论板解释如何产生 Hash Collision 或如何以模棱两可和详细的方式避免它。我最近在一次采访中遇到了这个问题。我有很多事情要解释，但我认为准确地给出正确的解释真的很难。抱歉，如果我的问题在这里重复，请将我带到准确的答案：
- 哈希冲突到底是什么 - 它是一个特征，还是一个错误完成但最好避免的常见现象？
- 究竟是什么导致哈希冲突 - 自定义 class'
hashCode() 方法的错误定义，或者在不完全覆盖 [=10= 的同时不覆盖 equals() 方法] 方法，或者它不是由开发人员决定的，许多流行的 java 库也有 class 可能导致哈希冲突的问题？
- 发生哈希冲突时是否出现任何错误或意外情况？我的意思是我们有什么理由应该避免哈希冲突？
- 是否 Java 在对象启动期间为每个 class 生成或至少尝试生成唯一的哈希码？如果不是，仅依靠 Java 来确保我的程序不会 运行 进入 JRE classes 的哈希冲突是否正确？如果不正确，那么如何避免哈希映射与最终 classes 像 String 作为键的哈希冲突？
如果您能分享您对其中一个或所有问题的答案，我将不胜感激。
What exactly is Hash Collision - is it a feature, or common phenomenon which is mistakenly done but good to avoid?
- 哈希冲突就是那个字段哈希码在对象上的冲突...
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? I mean is there any reason why we should avoid Hash Collision?
- 不，java中的String class已经很发达了class，你不需要搜索太多就可以找到冲突（检查这个Strings的hascode "Aa" 和 "BB" -> 都与 2112 有冲突)
总结一下：
hashcode 冲突是无害的，你知道那是什么以及为什么 与用于证明相等性的 id
不同
What exactly is Hash Collision - is it a feature, or common phenomenon which is mistakenly done but good to avoid?
这是一项功能。它源于 hashCode 的性质：从大值 space 到小得多的值 space 的映射。出于设计和意图，将会发生碰撞。
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?
如果散列 table 写得很好，则不会。 hash collision只是hashCode不唯一，导致调用equals()，重复越多性能越差
I mean is there any reason why we should avoid Hash Collision?
您必须权衡计算的便利性和价值的传播。没有单一的黑白答案。
Does Java generate or atleast try to generate unique hasCode per class during object initiation?
没有。 'Unique hash code' 术语自相矛盾。
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，那么您对哈希算法没有任何选择，而且您还使用了 class，其 hashCode 已被专家们奴役了 20 年或更长时间。
What exactly is Hash Collision - is it a feature, or common phenomenon
which is mistakenly done but good to avoid?
两者都不是...都是...这是普遍现象，但不是错误的做法，最好避免。
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?
如果你的 hashCode() 方法设计不当，你可能会产生太多的冲突，让你的 equals 方法不被重写应该不会直接影响冲突的数量，许多流行的 java 库有 classes 可能会导致冲突（实际上几乎所有 classes）。
Does anything go wrong or unexpected when Hash Collision happens? I
mean is there any reason why we should avoid Hash Collision?
性能下降，这是避免它们的原因，但程序应该继续工作。
Does Java generate or at least try to generate unique hashCode 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?
Java 不会尝试在对象初始化期间生成唯一的哈希码，但它有 hashCode() 和 equals() 的默认实现。默认实现用于了解两个对象引用是否指向同一个实例，并且不依赖于对象的内容（字段值）。因此，String class 有自己的实现。
其实我觉得散列冲突是正常的。先说一个案例来思考。我们有 1000000 个大数（x 的集合 S），假设 x 在 2^64 中。现在我们想为这个数字集做一张地图。让我们将这个数字集 S 映射到 [0,1000000] 。
但是怎么办？使用哈希！！
定义一个hash函数f(x) = x mod 1000000。现在S中的x会被转换成[0,1000000)，OK，但是你会发现S中的很多数会转换成一个数字。例如。数字 k * 1000000 + y 都将位于 y 中，因为 (k * 1000000 + y ) % x = y。所以这是哈希冲突。
以及如何处理碰撞？在我们上面谈到的这种情况下，由于数学计算具有一定的可能性，因此很难定界碰撞。我们可以找到更复杂、更好的散列函数，但不能肯定地说我们消除了碰撞。我们应该努力寻找一个更好的散列函数来减少散列冲突。因为散列冲突增加了我们使用散列来查找东西的时间成本。
简单来说，有两种方法可以处理哈希冲突。链表是一种更直接的方式，例如：如果上面的两个数字在hash_function之后得到相同的值，我们从这个值桶创建一个链表，并将所有相同的值放入该值的链表中。另一种方法是为后面的数字找到一个新的位置。例如，如果数字1000005已经占据了5的位置，当2000005得到值5时，它不能定位到位置5，然后继续寻找一个空位置。
对于最后一个问题：Java 是否在对象启动期间为每个 class 生成或至少尝试生成唯一的哈希码？
Object的hashcode一般是通过将对象的内部地址转换成整数来实现的。所以你可以认为不同的对象有不同的哈希码，如果你使用对象的哈希码（）。
HashMap 中的 Hash Collision 或 Hashing Collision 并不是一个新话题，我已经看到几个博客和讨论板解释如何产生 Hash Collision 或如何以模棱两可和详细的方式避免它。我最近在一次采访中遇到了这个问题。我有很多事情要解释，但我认为准确地给出正确的解释真的很难。抱歉，如果我的问题在这里重复，请将我带到准确的答案：
- 哈希冲突到底是什么 - 它是一个特征，还是一个错误完成但最好避免的常见现象？
- 究竟是什么导致哈希冲突 - 自定义 class'
hashCode()方法的错误定义，或者在不完全覆盖 [=10= 的同时不覆盖equals()方法] 方法，或者它不是由开发人员决定的，许多流行的 java 库也有 class 可能导致哈希冲突的问题？ - 发生哈希冲突时是否出现任何错误或意外情况？我的意思是我们有什么理由应该避免哈希冲突？
- 是否 Java 在对象启动期间为每个 class 生成或至少尝试生成唯一的哈希码？如果不是，仅依靠 Java 来确保我的程序不会 运行 进入 JRE classes 的哈希冲突是否正确？如果不正确，那么如何避免哈希映射与最终 classes 像 String 作为键的哈希冲突？
如果您能分享您对其中一个或所有问题的答案，我将不胜感激。
What exactly is Hash Collision - is it a feature, or common phenomenon which is mistakenly done but good to avoid?
- 哈希冲突就是那个字段哈希码在对象上的冲突...
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? I mean is there any reason why we should avoid Hash Collision?
- 不，java中的String class已经很发达了class，你不需要搜索太多就可以找到冲突（检查这个Strings的hascode "Aa" 和 "BB" -> 都与 2112 有冲突)
总结一下： hashcode 冲突是无害的，你知道那是什么以及为什么 与用于证明相等性的 id
不同What exactly is Hash Collision - is it a feature, or common phenomenon which is mistakenly done but good to avoid?
这是一项功能。它源于 hashCode 的性质：从大值 space 到小得多的值 space 的映射。出于设计和意图，将会发生碰撞。
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?
如果散列 table 写得很好，则不会。 hash collision只是hashCode不唯一，导致调用equals()，重复越多性能越差
I mean is there any reason why we should avoid Hash Collision?
您必须权衡计算的便利性和价值的传播。没有单一的黑白答案。
Does Java generate or atleast try to generate unique hasCode per class during object initiation?
没有。 'Unique hash code' 术语自相矛盾。
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，那么您对哈希算法没有任何选择，而且您还使用了 class，其 hashCode 已被专家们奴役了 20 年或更长时间。
What exactly is Hash Collision - is it a feature, or common phenomenon which is mistakenly done but good to avoid?
两者都不是...都是...这是普遍现象，但不是错误的做法，最好避免。
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?
如果你的 hashCode() 方法设计不当，你可能会产生太多的冲突，让你的 equals 方法不被重写应该不会直接影响冲突的数量，许多流行的 java 库有 classes 可能会导致冲突（实际上几乎所有 classes）。
Does anything go wrong or unexpected when Hash Collision happens? I mean is there any reason why we should avoid Hash Collision?
性能下降，这是避免它们的原因，但程序应该继续工作。
Does Java generate or at least try to generate unique hashCode 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?
Java 不会尝试在对象初始化期间生成唯一的哈希码，但它有 hashCode() 和 equals() 的默认实现。默认实现用于了解两个对象引用是否指向同一个实例，并且不依赖于对象的内容（字段值）。因此，String class 有自己的实现。
其实我觉得散列冲突是正常的。先说一个案例来思考。我们有 1000000 个大数（x 的集合 S），假设 x 在 2^64 中。现在我们想为这个数字集做一张地图。让我们将这个数字集 S 映射到 [0,1000000] 。
但是怎么办？使用哈希！！
定义一个hash函数f(x) = x mod 1000000。现在S中的x会被转换成[0,1000000)，OK，但是你会发现S中的很多数会转换成一个数字。例如。数字 k * 1000000 + y 都将位于 y 中，因为 (k * 1000000 + y ) % x = y。所以这是哈希冲突。
以及如何处理碰撞？在我们上面谈到的这种情况下，由于数学计算具有一定的可能性，因此很难定界碰撞。我们可以找到更复杂、更好的散列函数，但不能肯定地说我们消除了碰撞。我们应该努力寻找一个更好的散列函数来减少散列冲突。因为散列冲突增加了我们使用散列来查找东西的时间成本。
简单来说，有两种方法可以处理哈希冲突。链表是一种更直接的方式，例如：如果上面的两个数字在hash_function之后得到相同的值，我们从这个值桶创建一个链表，并将所有相同的值放入该值的链表中。另一种方法是为后面的数字找到一个新的位置。例如，如果数字1000005已经占据了5的位置，当2000005得到值5时，它不能定位到位置5，然后继续寻找一个空位置。
对于最后一个问题：Java 是否在对象启动期间为每个 class 生成或至少尝试生成唯一的哈希码？
Object的hashcode一般是通过将对象的内部地址转换成整数来实现的。所以你可以认为不同的对象有不同的哈希码，如果你使用对象的哈希码（）。