哈希冲突到底是什么 [英] What Exactly is Hash Collision

问题描述

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

Hash Collision or Hashing Collision in HashMap is not a new topic and I've come across several blogs and discussion boards explaining how to produce Hash Collision or how to avoid it in an ambiguous and detailed way. I recently came across this question in an interview. I had lot of things to explain but I think it was really hard to precisely give the right explanation. Sorry if my questions are repeated here, please route me to the precise answer:

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

1. What exactly is Hash Collision - is it a feature, or common phenomenon which is mistakenly done but good to avoid?
2. 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?
3. Does anything go wrong or unexpected when Hash Collision happens? I mean is there any reason why we should avoid Hash Collision?
4. 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?

如果能与您分享一个或所有这些问题的答案，我将不胜感激.

I'll be greateful if you could please share you answers for one or all of these questions.

推荐答案

散列碰撞到底是什么-它是一项功能或常见现象，但误操作但可以避免吗?

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

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

It's a feature. It arises out of the nature of a hashCode: a mapping from a large value space to a much smaller value space. There are going to be collisions, by design and intent.

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

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

糟糕的设计会使情况变得更糟，但这在概念上是地方性的.

A bad design can make it worse, but it is endemic in the notion.

OR使equals()方法不被覆盖，同时不完美地覆盖hashCode()方法，

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

否.

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

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

这真的没有道理.哈希表早晚会冲突的，糟糕的算法会使它早些时候发生冲突.就是这样.

This doesn't really make sense. Hashes are bound to collide sooner or later, and poor algorithms can make it sooner. That's about it.

发生哈希冲突时，有什么地方出错或无法预料吗?

Does anything go wrong or unexpected when Hash Collision happens?

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

Not if the hash table is competently written. A hash collision only means that the hashCode is not unique, which puts you into calling equals(), and the more duplicates there are the worse the performance.

我的意思是为什么我们应该避免哈希冲突?

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

您必须权衡易计算性和价值分散性.没有黑白答案.

You have to trade off ease of computation against spread of values. There is no single black and white answer.

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

不.术语唯一哈希码"是一个矛盾.

No. 'Unique hash code' is a contradiction in terms.

如果否，是否仅依靠Java来确保我的程序不会在JRE类的Hash Collision中运行是正确的吗?如果不正确，那么如何避免将String之类的最终类作为键的哈希映射的哈希冲突?

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已被专家奴役20年或20年以上的类.

The question is meaningless. If you're using String you don't have any choice about the hashing algorithm, and you are also using a class whose hashCode has been slaved over by experts for twenty or more years.

这篇关于哈希冲突到底是什么的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！