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

Question

我有这个测试代码:

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; }取消注释m.size()返回2,当它被注释 时,它返回三.为什么？

Answer 1

HashMap使用hashCode(),==并equals()用于条目查找.给定键的查找序列k如下:

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

为了演示一个例子,假设我们想要创建一个HashMapwhere键,如果它们具有相同的整数值(由AmbiguousIntegerclass 表示),则它们在逻辑上是等价的.然后我们构造一个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使用这些值映射key1和key2成不同的桶.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()仅覆盖: HashMap映射key1并key2进入同一个存储桶,但由于两者key1 == key2和key1.equals(key2)检查失败,它们保持不同的条目,因为默认情况下equals()使用==check,它们引用不同的实例.key3失败都==和equals()检查对key1和key2,因此具有没有对应的值.

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()仅覆盖: HashMap由于默认值不同,将所有密钥映射到不同的存储桶hashCode().==或者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

覆盖both hashCode()和equals():HashMapmaps key1,key2并覆盖key3到同一个存储桶中.==在比较不同的实例时检查失败,但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将为每个操作分配一个不同的存储桶,因此您永远不会找到您之前输入的相同条目.

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将所有键映射到一个大桶中.在这种情况下,您的代码在功能上是正确的,但使用HashMap实际上是多余的,因为任何检索都需要在O(N)时间内迭代该单个存储桶中的所有条目(或Java 8的O(logN)),等效使用a 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检查总是失败key1,key2并且key3被认为是"逻辑上不同",并且映射到不同的条目,尽管它们仍然在相同的桶中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现在总是如此？:你基本上是说所有对象都被认为与另一个对象"在逻辑上等同",所以它们都映射到同一个桶(由于相同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

Answer 2

你已经超越equals而没有覆盖hashCode.您必须确保equals对于两个对象返回true的所有情况,hashCode返回相同的值.哈希码是一个代码,如果两个对象相等则必须相等(反之不必为真).当您将硬编码值设置为9时,您再次满足合同.

在哈希映射中,仅在哈希桶中测试相等性.你的两个星期一对象应该是相同的,但是因为它们返回不同的哈希码,所以equals甚至不调用该方法来确定它们的相等性 - 它们被直接放入不同的桶中,甚至不考虑它们相等的可能性.

Answer 3

我不能强调你应该阅读Effective Java中的第3章(警告:pdf链接).在该章中,您将了解有关覆盖方法的所有信息Object,特别是有关equals合同的信息.乔什布洛赫有一个很好的方法来覆盖equals你应该遵循的方法.它将帮助您了解您应该使用的原因,equals而不是==您equals方法的特定实现.

希望这可以帮助.请仔细阅读.(至少是前几个项目......然后你会想要阅读其余的内容:-).

-Tom

Answer 4

当您不重写hashCode()方法时,您的ToDos类从Object继承默认的hashCode()方法,该方法为每个对象提供不同的哈希代码.这意味着t1并且t2有两个不同的哈希码,即使您要比较它们,它们也是相同的.根据特定的hashmap实现,地图可以单独存储它们(事实上这就是发生的事情).

当您正确覆盖hashCode()方法以确保相等对象获得相等的哈希码时,哈希映射能够找到两个相等的对象并将它们放在同一个哈希桶中.

更好的实现会给那些对象不等于不同的哈希码,就像这样:

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