理解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方法的特定实现。

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