根据我的理解,我认为:

两个对象具有相同的hashcode是完全合法的。 如果两个对象相等(使用equals()方法),则它们具有相同的hashcode。 如果两个对象不相等,那么它们就不能有相同的hashcode

我说的对吗?

如果我没猜错的话,我有以下问题: HashMap在内部使用对象的hashcode。那么,如果两个对象可以具有相同的hashcode,那么HashMap如何跟踪它使用的键呢?

有人能解释一下HashMap内部是如何使用对象的hashcode的吗?


当前回答

你可以在http://javarevisited.blogspot.com/2011/02/how-hashmap-works-in-java.html上找到很好的信息

总结:

HashMap的工作原理是哈希

put(key, value): HashMap将key和value对象都存储为Map.Entry。Hashmap应用hashcode(key)来获取桶。如果有碰撞,HashMap使用LinkedList存储对象。

get(key): HashMap使用key Object的hashcode来查找桶的位置,然后调用keys.equals()方法来识别LinkedList中的正确节点,并在Java HashMap中返回该键的相关值对象。

其他回答

你在第三点上错了。两个条目可以具有相同的哈希码,但不相等。看一下HashMap的实现。从OpenJdk中获取。你可以看到它检查哈希值是否相等键值是否相等。如果第三点成立,那么检查键值是否相等就没有必要了。哈希码在键之前进行比较,因为前者是更有效的比较。

如果您有兴趣进一步了解这方面的知识,请参阅Wikipedia关于开放寻址冲突解决的文章,我认为这是OpenJdk实现使用的机制。这种机制与另一个答案中提到的“桶”方法略有不同。

我不会详细介绍HashMap是如何工作的,但是会给出一个例子,这样我们就可以通过将HashMap与现实联系起来来记住它是如何工作的。

我们有Key, Value,HashCode和bucket。

在一段时间内,我们将把它们与以下内容联系起来:

一个社会 HashCode ->社会地址(总是唯一的) 社会中的房子 Key ->房屋地址。

使用Map.get(key):

Stevie想去他的朋友(Josse)的房子,他住在一个VIP社会的别墅里,让它成为javalavers社会。 Josse的地址是他的SSN(每个人都不一样)。 有一个索引,我们可以根据社会安全号找到协会的名字。 这个索引可以被认为是一个找出HashCode的算法。

SSN协会名称 92313(Josse’s) -爪哇 13214—AngularJSLovers 98080—javalover 53808 -生物爱好者


这个SSN(密钥)首先给我们一个HashCode(来自索引表),它只是社会的名字。 现在,多个房子可以在同一个社会中,所以HashCode可以是公共的。 假设,社会对两个房子都是公用的,我们如何识别我们要去哪个房子,是的,通过使用(SSN)密钥,它只是房子的地址

使用Map.put(关键字,值)

这将通过查找HashCode为该值找到一个合适的社会,然后存储该值。

我希望这能有所帮助,而且这是可以修改的。

两个对象相等,意味着它们具有相同的hashcode,而不是相反。 2个相等的对象------>他们有相同的hashcode 2个对象具有相同的hashcode ----xxxxx—>,它们不相等

HashMap中的Java 8更新

在代码中执行这个操作

myHashmap.put("old","old-value");
myHashMap.put("very-old","very-old-value");

所以,假设你的hashcode为“old”和“very old”两个键返回的hashcode是相同的。然后会发生什么。

myHashMap是一个HashMap,假设最初您没有指定它的容量。所以每个java的默认容量是16。所以现在只要你使用new关键字初始化hashmap,它就创建了16个桶。现在当你执行第一个语句

myHashmap.put("old","old-value");

然后计算“old”的hashcode,因为hashcode也可以是非常大的整数,所以,Java内部做了这个(hash是hashcode, >>>是右移)

hash XOR hash >>> 16

为了给出一个更大的图,它会返回一个索引值,在0到15之间。现在,键值对“old”和“old-value”将被转换为Entry对象的键值实例变量。然后这个entry对象会被存储在bucket中,或者你可以说在一个特定的索引处,这个entry对象会被存储。

入口是Map接口- Map中的一个类。条目,带有这些签名/定义

class Entry{
          final Key k;
          value v;
          final int hash;
          Entry next;
}

现在当你执行下一条语句时

myHashmap.put("very-old","very-old-value");

“very old”给出了与“old”相同的哈希码,所以这个新的键值对再次被发送到相同的索引或相同的存储桶。但是因为这个存储桶不是空的,所以Entry对象的下一个变量被用来存储这个新的键值对。

并且它将存储为每个具有相同hashcode的对象的链表,但TRIEFY_THRESHOLD的值为6。在此之后,链表转换为以第一个元素为根的平衡树(红黑树)。

你的第三个断言是不正确的。

两个不相等的对象拥有相同的哈希码是完全合法的。它被HashMap用作“第一遍过滤器”,以便映射可以快速找到具有指定键的可能条目。然后测试具有相同哈希码的键是否与指定的键相等。

您不会希望要求两个不相等的对象不能具有相同的哈希码,否则将限制为232个可能的对象。(这也意味着不同类型甚至不能使用对象的字段来生成哈希码,因为其他类可以生成相同的哈希码。)

每个Entry对象表示键值对。如果一个桶有多于1个Entry,则字段next指向其他Entry对象。

有时候,两个不同对象的hashcode可能是相同的。在这种情况下,2个对象将保存在一个桶中,并将显示为LinkedList。入口点是最近添加的对象。该对象引用具有next字段的其他对象,等等。最后一项为空。 当您使用默认构造函数创建HashMap时

数组的大小为16,默认负载平衡为0.75。

(源)