哈希碰撞究竟是什么

Question

HashMap中的Hash Collision或Hashing Collision不是一个新主题,我遇到了几个博客和讨论板,解释了如何产生Hash Collision或如何以模糊和详细的方式避免它.我最近在一次采访中遇到了这个问题.我有很多事要解释,但我认为很难准确地给出正确的解释.对不起,如果我的问题在这里重复,请告诉我确切的答案:

1. Hash Collision究竟是什么 - 它是一个特征,或者是一个错误的常见现象,但是要避免它？
2. 究竟是什么导致Hash Collision - 自定义类' hashCode()方法的错误定义,或者equals()在不完全覆盖hashCode()方法的情况下保持方法不被覆盖,或者不是由开发人员决定的,许多流行的java库也有可能导致Hash的类碰撞？
3. 当Hash Collision发生时,是否出现任何问题或意外？我的意思是,为什么我们应该避免哈希碰撞？
4. 在对象启动期间,Java是否生成或至少尝试为每个类生成唯一的hashCode？如果不是,单独依靠Java来确保我的程序不会遇到JRE类的Hash Collision是正确的吗？如果不对,那么如何避免使用像String这样的最终类作为键的哈希映射的哈希冲突？

如果你能分享一个或所有这些问题的答案,我会很感激.

Answer 1

Hash Collision究竟是什么 - 它是一个特征,或者是一个错误的常见现象,但是要避免它？

这是一个功能.它产生于hashCode的本质:从大值空间到更小值空间的映射.根据设计和意图,会发生碰撞.

究竟是什么导致Hash Collision - 自定义类'hashCode()方法的错误定义,

糟糕的设计可能会使情况变得更糟,但它在这个概念中是流行的.

或者保持equals()方法不被覆盖,而不完全覆盖hashCode()方法,

没有.

或者它不是由开发人员和许多流行的Java库也有可能导致哈希冲突的类？

这没有多大意义.哈希迟早会发生碰撞,而糟糕的算法可能会更快地发生.就是这样.

当Hash Collision发生时,是否出现任何问题或意外？

如果哈希表写得很好,则不会.哈希冲突只意味着hashCode不是唯一的,这会让你进入调用equals(),而重复的越多,性能越差.

我的意思是,为什么我们应该避免哈希碰撞？

你必须权衡计算的简易性和价值的传播.没有单一的黑白答案.

Java是否生成或至少尝试在对象启动期间为每个类生成唯一的hasCode？

不,"唯一哈希码"在术语上是矛盾的.

如果不是,单独依靠Java来确保我的程序不会遇到JRE类的Hash Collision是正确的吗？如果不对,那么如何避免使用像String这样的最终类作为键的哈希映射的哈希冲突？

这个问题毫无意义.如果你正在使用String你,你对哈希算法没有任何选择,你也使用了一个类,其hashCode已经被专家服务了20年或更长时间.

Answer 2

其实我认为哈希冲突是正常的。讲一个案例来思考。我们有 1000000 个大数（x 的集合 S），假设 x 在 2^64 中。现在我们要为这个数字集做一个映射。让我们将此数字集 S 映射到 [0,1000000] 。

但是如何？使用哈希！！

定义一个hash函数f(x) = x mod 1000000。现在S中的x会转化为[0,1000000)，好的，但是你会发现S中的很多数都会转化为一个数。例如。数字 k * 1000000 + y 将全部位于 y 中，因为 (k * 1000000 + y ) % x = y。所以这是一个哈希冲突。

以及如何处理碰撞？在我们上面谈到的这种情况下，由于数学计算具有一定的可能性，因此很难界定碰撞。我们可以找到更复杂、更好的哈希函数，但不能肯定地说我们消除了冲突。我们应该努力寻找更好的散列函数来减少散列冲突。因为哈希冲突增加了我们使用哈希来查找某些东西的时间成本。

简单地说，有两种方法可以处理散列冲突。链表是一种更直接的方式，例如：如果上面的两个数在hash_function后得到相同的值，我们就从这个值桶创建一个链表，所有相同的值都放在这个值的链表中。另一种方法是为后面的数字找到一个新位置。例如，如果数字1000005已经在5中占据了位置，当2000005得到值5时，它就无法定位在5位置，那么它就继续寻找一个空的位置来占据。

对于最后一个问题：Java 是否会在对象启动期间为每个类生成或至少尝试生成唯一的 hashCode？

Object 的 hashcode 通常是通过将对象的内部地址转换为整数来实现的。所以你可以认为不同的对象有不同的哈希码，如果你使用对象的 hashcode()。