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

我有这个测试代码:

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，当留下注释时，它返回3。为什么？

最佳答案

HashMap使用hashCode()，==和equals()进行条目查找。给定键k的查找顺序如下:

如果有

，请使用k.hashCode()确定条目存储在哪个存储桶中

如果找到，则针对该存储桶中每个条目的键k1，如果是k == k1 || k.equals(k1)，则返回k1的条目

其他任何结果，没有相应的条目

为了举例说明，假设我们要创建一个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使用这些值将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()使用==检查，并且它们引用不同的实例。 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

覆盖hashCode()和equals() :HashMap将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将所有 key 映射到一个大存储桶中。在这种情况下，您的代码在功能上是正确的，但是HashMap的使用实际上是多余的，因为任何检索都需要在O(N)时间(or O(logN) for 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检查始终失败，因此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