什么是哈希碰撞？

Question

什么是哈希碰撞？

22

HashMap中的哈希冲突或散列冲突并不是一个新话题，我曾经看过几篇博客和讨论版块，介绍如何产生哈希冲突或如何避免它，但这些都解释得含糊而冗长。最近在一次面试中我也遇到了类似的问题，我有很多事情要解释，但我认为精确地给出正确的解释真的很困难。如果我的问题在这里重复了，请指引我找到精确的答案：

哈希冲突到底是什么 - 是一个特性，还是一种常见的错误操作，需要避免？
是什么导致了哈希冲突 - 自定义类'hashCode（）'方法的错误定义，还是只是不完全覆盖‘equals（）’方法，而不覆盖‘hashCode（）’方法，或者是开发人员无法控制，许多流行的Java库也有可能导致哈希冲突？
当哈希冲突发生时，是否会出现任何错误或意外情况？换句话说，我们是否应该避免哈希冲突？
Java是否生成或至少尝试生成每个类的唯一hashCode，并在对象初始化期间执行此操作？如果没有，仅依赖Java以确保我的程序不会遇到JRE类的哈希冲突是否正确？如果不正确，则如何避免使用字符串等最终类作为键的哈希图中的哈希冲突？

如果您能回答一个或所有这些问题，我将不胜感激。

- sribasu

8

建议重新表述这个问题。不要使用“分享一篇精彩的博客文章”（这对于StackOverflow来说是离题的），为什么不直接询问正确答案和解释呢？ - slartidan

4

面试问题和作业问题一样，都是需要自己解决的事情。如果您在StackOverflow上发表它们作为问题，您必须提供自己的解决方案，并指出您的解决方案卡住或缺乏的地方。目前这个问题只是显示了缺乏研究的情况。 - RealSkeptic

1

请参阅TAOCP：第3卷，第6.4章哈希。 - trashgod

2

通常情况下，你不会“避免”哈希碰撞，而是通常假定这种情况会在哈希表中发生。Java集合类HashMap使用的解决方法是维护一个碰撞值的树（之前是值的列表）。如果你发现有太多的碰撞，你可能需要考虑调整哈希表中的桶数。你的问题太笼统了，我同意其他评论的观点，你应该缩小你在这里想要问的问题。 - Tim Biegeleisen

2

你确实指出这些是面试问题。所以它们与作业问题相同。无论是否简洁，它们都不遵循SO的准则（我非常惊讶人们会点赞这个问题）。首先，你应该始终在单个帖子中发布一个问题。 - RealSkeptic

显示剩余9条评论

4个回答

5

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

但是如何做呢？使用哈希函数！定义一个哈希函数f(x) = x mod 1000000。现在S中的x将被转换为[0,1000000)，好了，但你会发现许多数字在S中会转换成一个数字。例如，所有k * 1000000 + y的数字都位于y处，因为(k * 1000000 + y) % x = y。所以这是一次哈希碰撞。

如何处理碰撞？在上面提到的这种情况下，很难分隔碰撞，因为数学计算有一定的可能性。我们可以找到一个更复杂、更好的哈希函数，但不能完全消除碰撞。我们应该努力找到一个更好的哈希函数来减少哈希碰撞。因为哈希碰撞会增加我们使用哈希查找某些内容的时间成本。

简单地说，处理哈希碰撞有两种方法。链表是一种更直接的方法，例如：如果两个以上的数字在哈希函数后得到相同的值，我们就从这个值桶中创建一个链表，并将所有相同的值放入该值的链表中。另一种方法是为后续的数字找到一个新位置。例如，如果数字1000005已经占据了位置5，当2000005获得值5时，它不能定位在位置5，而是继续向前寻找一个空位置。

对于最后一个问题：Java在对象初始化期间生成或至少尝试生成每个类的唯一hashCode吗？

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

- GuangshengZuo

1

什么是哈希碰撞 - 它是一个特性，还是一种常见的错误现象，但最好避免?

哈希碰撞就是对象哈希码的冲突。

哈希碰撞是由什么导致的 - 是自定义类的hashCode()方法定义不当，还是只重写了hashCode()方法而未重写equals()方法，或者开发人员无法控制，许多流行的Java库也有可能导致哈希碰撞？

不是因为定义不当，而是由于数学概率所决定的，这种情况下生日悖论是最好的解释方式。

哈希碰撞发生时是否会出现任何意外或异常情况？我指的是是否有任何理由避免哈希碰撞？

不会有任何问题，Java中的String类是非常完善的类，你不需要花费太多时间来查找哈希碰撞（检查这些字符串"Aa"和"BB"的哈希码 -> 两者都有一个哈希碰撞到2112）。

总结一下：如果你知道哈希码碰撞的作用和为什么它不同于用于证明相等性的 ID，则哈希码碰撞是无害的。

- ΦXocę 웃 Пepeúpa ツ

Java 中的 String 类是非常成熟的类，你不需要太多搜索就可以找到一个碰撞（检查字符串 "Aa" 和 "BB" 的哈希码 -> 它们都与 2112 发生碰撞）。对于这部分我对 Java 的知识较差，抱歉。 - sribasu

我的意思是即使在非常完善的类上也可能发生碰撞... String类就是一个例子... 它的2个实例会产生哈希冲突，这并不意味着该类有问题或编写不良... - ΦXocę 웃 Пepeúpa ツ

1

哈希碰撞到底是什么？它是一种特性，还是常见的现象，容易被误解但最好避免使用？

既不是特性也不是误解，它是一种常见的现象，但最好避免使用。

哈希碰撞到底是由什么引起的？是自定义类中hashCode()方法的错误定义，还是只重写了hashCode()方法而没有重写equals()方法，或者这与开发人员无关，许多流行的Java库也有可能会导致哈希碰撞？

通过错误设计hashCode()方法，你可以产生过多的碰撞，只重写hashCode()方法而没有重写equals()方法不会直接影响碰撞次数，许多流行的Java库都有可能会导致碰撞（实际上几乎所有类都有可能）。

当哈希碰撞发生时，会出现任何错误或意外情况吗？我的意思是，我们应该避免哈希碰撞的原因是什么？

性能会下降，这就是需要避免它们的原因，但程序应该继续正常工作。

Java在对象初始化时并不会尝试生成唯一的hashCode，但它有一个默认的hashCode()和equals()实现。默认实现用于判断两个对象引用是否指向同一实例，不依赖于对象内容（字段值）。因此，String类有自己的实现方式。如果不正确地依赖于Java来确保程序不会运行到JRE类的哈希冲突，则需要避免使用像String这样的final类作为键的哈希映射表中的哈希冲突。

- Maurice Perry

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user207421 · Accepted Answer

什么是哈希冲突 - 是一个特点，还是误操作但需要避免的普遍现象？

它是一个特点。它源于hashCode的本质: 从一个大的值空间映射到一个小得多的值空间。根据设计和意图，一定会有碰撞发生。

什么导致哈希冲突 - 自定义类的hashCode()方法定义不好？

设计不好会使其变得更糟，但它是这个概念的固有属性。

还是在完美重写hashCode()方法的同时留下equals()方法未被重写？

不是。

或者是不是由开发人员控制不了，许多流行的Java库中也有可能出现哈希冲突的类？

这并没有太多意义。哈希之间必然会发生冲突，算法较差会更早发生。就是这样。

哈希冲突发生时是否会出现任何错误或意外情况？

如果哈希表编写得很好，就不会发生任何错误或意外情况。哈希冲突只意味着hashCode不唯一，这将使您调用equals()方法，并且重复项越多，性能越差。

我的意思是是否有任何理由避免哈希冲突？

您必须在计算的便利性与值的扩展之间进行权衡。没有单一的黑白答案。

Java是否会生成或至少尝试在对象初始化期间为每个类生成唯一的哈希码？

不会。'唯一的哈希码'是自相矛盾的。

如果否，则仅依靠Java确保我的程序不会运行到JRE类的哈希冲突是否正确？如果不正确，则如何避免使用像String之类的最终类作为key的哈希映射时发生哈希冲突？

这个问题是没有意义的。如果你正在使用String，那么你在哈希算法方面没有任何选择，并且你还使用了一个经过专家二十年或更长时间努力打磨的hashCode方法的类。