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

标签 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没有对应的bucket所以没有值。

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 对 key1 和 key2 的 == 和 equals() 检查均失败，并且因此没有对应的值。

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 将所有键映射到一个大桶中。在这种情况下，您的代码在功能上是正确的，但使用 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 总是 false 怎么办？:== 检查在我们将同一个实例与其自身进行比较时通过，否则失败， 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

关于java - 理解 HashMap 中 equals 和 hashCode 的工作原理，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1894377/

上一篇：java - JUnit:可能 'expect' 包装异常？

下一篇：java - Java 8 中的空安全集合作为流

相关文章：

java - 调试 HashMap - Java Android

java - 字符串比较应该相等时却不相等

java - 为多个对象提供服务的 GWT 服务

java - 文件为空时显示错误消息的问题

java - 添加到 HashMap 中的哈希集

java - 谁能解释一下 java 是如何设计 HashMap 的 hash() 函数的？

JavaFX:如何重写具有属性的 bean 的 hashCode 方法？

arrays - 为什么 `Array(0,1,2) == Array(0,1,2)` 没有返回预期的结果？

java - 为 JSP 创建注销链接

java - Elasticsearch 单元测试

©2024 IT工具网  联系我们