了解 HashMap 中 equals 和 hashCode 的工作原理 [英] Understanding the workings of equals and hashCode in a HashMap

查看:34
本文介绍了了解 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; }
}

When //public int hashCode() { return 9;} 未注释 m.size() 返回 2,当它留下注释时返回 3.为什么?

When // public int hashCode() { return 9; } is uncommented m.size() returns 2, when it's left commented it returns three. Why?

推荐答案

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

HashMap uses hashCode(), == and equals() for entry lookup. The lookup sequence for a given key k is as follows:

  • 使用 k.hashCode() 确定条目存储在哪个桶中(如果有)
  • 如果找到,对于该桶中每个条目的键 k1,如果 k == k1 ||k.equals(k1),然后返回k1的入口
  • 任何其他结果,无相应条目
  • Use k.hashCode() to determine which bucket the entry is stored, if any
  • If found, for each entry's key k1 in that bucket, if k == k1 || k.equals(k1), then return k1's entry
  • Any other outcomes, no corresponding entry

为了使用示例进行演示,假设我们要创建一个 HashMap,其中键是逻辑等效"的东西,如果它们具有相同的整数值,由 AmbiguousInteger 班级.然后我们构造一个 HashMap,放入一个条目,然后尝试覆盖它的值并通过键检索值.

To demonstrate using an example, assume that we want to create a HashMap where keys are something which is 'logically equivalent' if they have same integer value, represented by AmbiguousInteger class. We then construct a HashMap, put in one entry, then attempt to override its value and retrieve value by key.

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 没有对应的bucket,所以没有值.

Don't override hashCode() and equals(): by default Java generates different hashCode() values for different objects, so HashMap uses these values to map key1 and key2 into different buckets. key3 has no corresponding bucket so it has no value.

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() 使用 == 检查,它们指的是不同的实例.key3key1key2==equals() 检查均失败,并且因此没有对应的值.

Override hashCode() only: HashMap maps key1 and key2 into the same bucket, but they remain different entries due to both key1 == key2 and key1.equals(key2) checks fail, as by default equals() uses == check, and they refer to different instances. key3 fails both == and equals() checks against key1 and key2 and thus has no corresponding value.

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 永远不会到达需要使用它们的地步.

Override equals() only: HashMap maps all keys into different buckets because of default different hashCode(). == or equals() check is irrelevant here as HashMap never reaches the point where it needs to use them.

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映射key1key2key3 放入同一个桶中.== 检查在比较不同实例时失败,但 equals() 检查通过,因为它们都具有相同的值,并且被我们的逻辑视为逻辑等效".

Override both hashCode() and equals(): HashMap maps key1, key2 and key3 into the same bucket. == checks fail when comparing different instances, but equals() checks pass as they all have the same value, and deemed 'logically equivalent' by our logic.

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 将为每个操作分配一个不同的桶,因此你永远找不到相同的您之前输入的条目.

What if hashCode() is random?: HashMap will assign a different bucket for each operation, and thus you never find the same entry that you put in earlier.

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) 时间(或 O(logN) for Java 8),相当于使用 List.

What if hashCode() is always the same?: HashMap maps all keys into one big bucket. In this case, your code is functionally correct, but the use of HashMap is practically redundant, as any retrieval would need to iterate through all entries in that single bucket in O(N) time (or O(logN) for Java 8), equivalent to the use of 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 检查总是失败,所以 key1key2key3 被认为是逻辑上不同的",并映射到不同的条目,尽管由于相同的 hashCode(),它们仍然在同一个桶中.

And what if equals is always false?: == check passes when we compare the same instance with itself, but fails otherwise, equals checks always fails so key1, key2 and key3 are deemed to be 'logically different', and maps to different entries, though they are still in the same bucket due to same 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()),相同的条目.

Okay what if equals is always true now?: you're basically saying that all objects are deemed 'logically equivalent' to another, so they all map to the same bucket (due to same hashCode()), same entry.

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

这篇关于了解 HashMap 中 equals 和 hashCode 的工作原理的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆