在HashMap中了解equals和hashCode的工作原理

我有这个testing代码:

import java.util.*; class MapEQ { public static void main(String[] args) { Map<ToDos, String> m = new HashMap<ToDos, String>(); ToDos t1 = new ToDos("Monday"); ToDos t2 = new ToDos("Monday"); ToDos t3 = new ToDos("Tuesday"); m.put(t1, "doLaundry"); m.put(t2, "payBills"); m.put(t3, "cleanAttic"); System.out.println(m.size()); } } class ToDos{ String day; ToDos(String d) { day = d; } public boolean equals(Object o) { return ((ToDos)o).day == this.day; } // public int hashCode() { return 9; } } 

// public int hashCode() { return 9; } // public int hashCode() { return 9; }被取消注释m.size()返回2,当它被留下评论它返回三。 为什么?

你有没有重写hashCode overidden equals 。 您必须确保对于两个对象的equals返回true的情况, hashCode返回相同的值。 散列码是一个代码,如果两个对象相等,则该代码必须相等(反之不必为真)。 当你把你的硬编码价值9,你再次满足合同。

在你的哈希映射中,只有在哈希桶中才能testing相等性。 你的两个星期一对象应该是相等的,但是因为它们返回的是不同的哈希码,所以equals方法甚至没有被调用来确定它们的相等性 – 它们被直接放到不同的桶中,甚至没有考虑它们相等的可能性。

HashMap使用hashCode()==equals()来查找条目。 给定密钥k的查找顺序如下:

  • 使用k.hashCode()来确定条目存储在哪个存储桶中(如果有的话)
  • 如果find,则对于该桶中的每个条目的密钥k1 ,如果k == k1 || k.equals(k1) k == k1 || k.equals(k1) ,然后返回k1的条目
  • 任何其他的结果,没有相应的条目

为了演示使用一个例子,假设我们要创build一个HashMap ,其中的键是“逻辑等价”,如果它们具有相同的整数值,用AmbiguousInteger类表示。 然后,我们构造一个HashMap ,放入一个条目,然后尝试重写它的值并通过键检索值。

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } } HashMap<AmbiguousInteger, Integer> map = new HashMap<>(); // logically equivalent keys AmbiguousInteger key1 = new AmbiguousInteger(1), key2 = new AmbiguousInteger(1), key3 = new AmbiguousInteger(1); map.put(key1, 1); // put in value for entry '1' map.put(key2, 2); // attempt to override value for entry '1' System.out.println(map.get(key1)); System.out.println(map.get(key2)); System.out.println(map.get(key3)); Expected: 2, 2, 2 

不要重写hashCode()equals() :默认情况下,Java为不同的对象生成不同的hashCode()值,所以HashMap使用这些值将key1key2映射到不同的桶中。 key3没有相应的存储桶,因此没有值。

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 2, get as entry 2[1] map.get(key3); // map to no bucket Expected: 2, 2, 2 Output: 1, 2, null 

仅重写hashCode() HashMapkey1key2映射到同一个存储桶中,但是由于key1 == key2key1.equals(key2)检查失败,所以它们保持不同的条目,因为默认情况下equals()使用==检查,他们指的是不同的实例。 key3失败==equals()检查key1key2 ,因此没有相应的值。

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[2] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[2] map.get(key3); // map to bucket 1, no corresponding entry Expected: 2, 2, 2 Output: 1, 2, null 

仅覆盖equals()由于默认的不同hashCode() HashMap将所有密钥映射到不同的存储桶中。 ==equals()检查在这里是不相关的,因为HashMap永远不会到达需要使用它的地步。

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 2, get as entry 2[1] map.get(key3); // map to no bucket Expected: 2, 2, 2 Actual: 1, 2, null 

覆盖hashCode()equals()HashMapkey1key2key3映射到同一个存储桶中。 ==比较不同的实例时检查失败,但equals()检查通过,因为它们都具有相同的值,并被我们的逻辑视为“逻辑上等价”。

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return value; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 2, 2, 2 

如果hashCode()是随机的呢?HashMap将为每个操作分配一个不同的存储桶,因此您永远不会find与之前放入的相同的条目。

 class AmbiguousInteger { private static int staticInt; private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return ++staticInt; // every subsequent call gets different value } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 2, set as entry 2[1] map.get(key1); // map to no bucket, no corresponding value map.get(key2); // map to no bucket, no corresponding value map.get(key3); // map to no bucket, no corresponding value Expected: 2, 2, 2 Actual: null, null, null 

如果hashCode()总是相同呢?HashMap将所有密钥映射到一个大桶中。 在这种情况下,你的代码在function上是正确的,但是使用HashMap实际上是多余的,因为任何检索都需要在O(N)时间( 或者O(logN))中遍历Java 8中的单个桶中的所有条目,相当于使用一个List

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return obj instanceof AmbiguousInteger && value == ((AmbiguousInteger) obj).value; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 2, 2, 2 

而如果equals总是假的?==检查通过,当我们比较同一个实例本身,但失败,否则, equals检查总是失败,所以key1key2key3被认为是“逻辑上不同”,并映射到不同的条目,虽然他们仍然是相同的由于相同的hashCode()

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return false; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[2] map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[2] map.get(key3); // map to bucket 1, no corresponding entry Expected: 2, 2, 2 Actual: 1, 2, null 

好吧,如果现在equals永远是真的? :你基本上是说所有对象都被认为与另一个对象在逻辑上是等价的,所以它们都映射到同一个bucket(由于hashCode()相同),同样的条目。

 class AmbiguousInteger { private final int value; AmbiguousInteger(int value) { this.value = value; } @Override public int hashCode() { return 0; } @Override public boolean equals(Object obj) { return true; } } map.put(key1, 1); // map to bucket 1, set as entry 1[1] map.put(key2, 2); // map to bucket 1, set as entry 1[1], override value map.put(new AmbiguousInteger(100), 100); // map to bucket 1, set as entry1[1], override value map.get(key1); // map to bucket 1, get as entry 1[1] map.get(key2); // map to bucket 1, get as entry 1[1] map.get(key3); // map to bucket 1, get as entry 1[1] Expected: 2, 2, 2 Actual: 100, 100, 100 

如果不覆盖hashCode()方法,则ToDos类会inheritanceObject中的默认hashCode()方法,从而为每个对象提供不同的哈希代码。 这意味着t1t2有两个不同的散列码,即使你们比较它们,它们也是一样的。 根据特定的HashMap实现,地图是分开存储的(事实上这是发生的)。

当你正确地覆盖hashCode()方法以确保相等的对象获得相同的散列码时,散列表能够find两个相等的对象并将它们放置在相同的散列桶中。

一个更好的实现会给对象相同的哈希代码,如下所示:

 public int hashCode() { return (day != null) ? day.hashCode() : 0; } 

我不能强调,你应该阅读有效的Java第3章 (警告:pdf链接)。 在这一章中,您将学习关于在Object重写方法所需要知道的一切,特别是关于equals合约。 乔希布洛赫有一个伟大的配方,覆盖你应该遵循的equals方法。 这将有助于你理解为什么你应该使用equals而不是==在你的特定实现的equals方法。

希望这可以帮助。 请阅读它。 (至less第一对夫妇的项目…然后你会想要阅读其余的:-)。

-Tom

当你评论时,它返回3;

因为从Objectinheritance的hashCode()只能被调用,这将为3个ToDos对象返回3个不同的哈希码。 不对等的哈希码意味着3个对象注定不同的桶,而equals()返回false,因为它们是它们各自桶中的第一个入口。 如果hashCode不同,则事先理解对象是不相等的。 他们会在不同的水桶。

当您取消注释时,返回2;

因为这里被重写的hashCode()被调用,它将为所有的ToDos返回相同的值,并且它们都必须进入一个桶,线性连接。 相同的hashcode不保证任何关于对象的等式或不等式。

t3的hashCode()为9,因为它是第一个入口,所以equals()是false,t3插入到bucket中,比如说bucket0。

然后t2获得与9相同的hashCode(),注定为同一个bucket0,则已存在于bucket0中的t3上的后续equals()将被覆盖equal()的定义返回false。

现在使用hashCode()作为9的t1也是针对bucket0的,随后的equals()调用与同一个bucket中的预先存在的t2相比,返回true。 t1无法进入地图。 所以地图的净大小是2 – > {ToDos @ 9 = cleanAttic,ToDos @ 9 = payBills}

这就解释了实现equals()和hashCode()的重要性,并且在确定hashCode()时也必须采用确定equals()所使用的字段。 这将保证如果两个对象相等,它们将总是具有相同的hashCode。 hashCodes不应该被认为是伪随机数,因为它们必须与equals()一致

根据Effective Java,

当您覆盖equals()时总是覆盖hashCode()

那么,为什么? 很简单,因为不同的对象(内容,而不是引用)应该得到不同的哈希码; 另一方面,相同的对象应该得到相同的哈希码。

根据以上所述,Java关联数据结构比较equals()和hashCode()调用获得的结果来创build桶。 如果两者相同,则对象是等价的; 否则不。

在特定情况下(即上面提到的那个),当hashCode()被注释时 ,为每个实例(被Objectinheritance的行为)生成一个随机数作为散列,equals()检查String的引用(记住Java String Pool)所以equals()应该返回true而不是hashCode(),结果是存储了3个不同的对象 。 让我们来看看如果hashCode()遵守合约但总是返回9,会发生什么情况。 那么,hashCode()总是相同的,equals()对于池中的两个string(即“Monday”)返回true ,对于它们来说,bucket将是相同的,仅存储2个元素

因此,在使用hashCode()和equals()重写时,一定要小心,特别是当复合数据types是用户定义的,并且它们与Java关联数据结构一起使用时。

当hashCode未注释时,HashMap将t1和t2视为相同的事物; 因此,t2的价值破坏了t1。 要理解这是如何工作的,请注意,当hashCode对两个实例返回相同的东西时,它们将最终转到相同的HashMap存储桶。 当你尝试向同一个桶中插入第二个东西时(在这种情况下,当t1已经存在的时候t2被插入),HashMap会扫描桶中另一个等于的键。 在你的情况下,t1和t2是相等的,因为他们有同一天。 在那个时候,“payBills”就是“做洗衣店”。 至于t2是否以t1为关键,我相信这是不明确的; 因此,任何行为都是允许的。

这里有几件重要的事情要考虑:

  1. 两个ToDos实例是否真的相等,因为它们每周都是同一天?
  2. 每当你实现equals,你应该实现hashCode,以便任何两个equals的对象也具有相同的hashCode值。 这是HashMap所做的基本假设。 这可能也是依赖于hashCode方法的其他东西。
  3. devise你的hashCode方法,使散列码均匀分布; 否则,你不会得到散列的性能好处。 从这个angular度来说,返回9是你能做的最糟糕的事情之一。

我认为,更有意思的是,抽象地思考一下:两个对象有不同的哈希代码的观察结果构成对象不相等的观察结果,而不是哈希代码。 因此,一个集合中没有任何对象具有特定散列码的观察结果构成了一个观察结果,即一个集合中的任何对象都不等于具有该散列码的任何对象。 此外,观察到集合中没有任何对象具有带有某些特征的哈希码构成了这样的观察结果,即它们中的任何一个都不等于任何对象。

散列表通常通过定义一系列特征来工作,其中恰好其中之一将适用于每个对象的散列码(例如“与0模47一致”,“与1模47一致”等),然后具有每个特征的对象的集合。 如果一个人被赋予了一个对象,并且可以确定哪一个特征适用于这个对象,那么人们就可以知道它必须处于一个具有该特征的事物集合中。

那个散列表通常使用一系列编号的桶是一个实现细节; 最重要的是,一个对象的散列码很快被用来识别很多不可能相等的东西,因此不需要进行比较。

无论何时在Java中创build一个新的对象,它都将被JVM本身分配一个唯一的哈希码。 如果你不重写hashcode方法,那么对象将获得唯一的hascode,因此是一个独特的桶(想象一下,bucket不过是JVM将去寻找对象的内存中的一个地方)。

(你可以通过调用每个对象的hashcode方法来检查hashcode的唯一性,并在控制台上打印它们的值)

在你的情况下,当你正在评论散列码方法,散列表首先寻找具有相同的散列码方法返回的存储桶。 每次你返回相同的哈希码。 现在当hashmap发现这个桶时,它会使用euqals方法比较当前对象和驻留在桶中的对象。 在这里,它发现“星期一”,所以hashmap实现不允许再次添加它,因为已经有一个对象具有相同的哈希码和相同的euqality实现。

当您评论散列码方法时,JVM只是简单地为所有这三个对象返回不同的散列码,因此它甚至不会用equals方法来协调对象。 所以在Map中将会有三个不同的对象被hashmap实现添加。