一尘不染

究竟是哈希冲突

java

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

  1. 哈希冲突到底是什么?它是一项功能或常见现象,但误操作但可以避免吗?
  2. 究竟是什么导致Hash Collision(哈希冲突)的原因-自定义类hashCode()方法的错误定义,或者使equals()方法不被覆盖而hashCode()又不完美地覆盖了方法,或者不是由开发人员决定的,并且许多流行的Java库中都有可能导致哈希的类碰撞?
  3. 哈希冲突发生时,有什么地方出错或意外吗?我的意思是说有什么原因可以避免哈希冲突?
  4. Java是否在对象初始化期间为每个类生成或至少尝试生成唯一的hashCode?如果不是,仅依靠Java来确保我的程序不会在JRE类的Hash Collision中运行是否正确?如果不合适,那么如何避免将最终类(例如String)作为键的hashmap的哈希冲突?

如果您可以将一个或所有这些问题的答案分享给我,我将不胜感激。


阅读 280

收藏
2020-12-03

共1个答案

一尘不染

哈希冲突到底是什么?它是一项功能或常见现象,但误操作但可以避免吗?

这是一个功能。它是由hashCode的本质引起的:从较大的值空间到较小的值空间的映射。根据设计和意图,将会发生冲突。

到底是什么导致哈希冲突-自定义类的hashCode()方法的错误定义,

不良的设计会使情况变得更糟,但这在概念上是地方性的。

或保留不覆盖equals()方法,同时不完美地覆盖hashCode()方法的情况,

没有。

还是不是由开发人员来决定的,许多流行的Java库中都有可能导致哈希冲突的类?

这真的没有道理。哈希表早晚会冲突的,糟糕的算法会使其早日崩溃。就是这样

哈希冲突发生时,有什么地方出错或意外吗?

如果哈希表被正确写入,则不是。哈希冲突仅表示hashCode不是唯一的,这使您进入调用equals(),并且重复次数越多,性能就越差。

我的意思是说有什么原因可以避免哈希冲突?

您必须权衡易于计算和价值分散的问题。没有单一的黑白答案。

Java是否在对象初始化期间为每个类生成或至少尝试生成唯一的hasCode?

不能。“唯一哈希码”在术语上是矛盾的。

如果不是,仅依靠Java来确保我的程序不会在JRE类的Hash
Collision中运行是否正确?如果不合适,那么如何避免将最终类(例如String)作为键的hashmap的哈希冲突?

这个问题毫无意义。如果您使用的String是散列算法,那么您别无选择,您还使用的是其hashCode已被专家奴役二十多年的类。

2020-12-03