以对象列表为键的 HashMap

Question

在 HashMap 中，当我将对象列表作为键传递时，我得到了不同的结果。

List<NewClass> list1 = new ArrayList<>();
List<NewClass> list2 = new ArrayList<>();

NewClass obj1 = new NewClass(1, "ddd", "eee@gmail.com");
NewClass obj2 = new NewClass(2, "ccc", "kkk@gmail.com");

list1.add(obj1);
list1.add(obj2);

list2.add(obj1);
list2.add(obj2);

Map<List<NewClass>, Integer> mapClass = new HashMap<>();
mapClass.put(list1, 1234);
mapClass.put(list2, 4567);

System.out.println(mapClass.size());
System.out.println(mapClass.get(list1));

NewClass obj4 = new NewClass(1, "ddd", "eee@gmail.com");
NewClass obj5 = new NewClass(2, "ccc", "kkk@gmail.com");
List<NewClass> list3 = new ArrayList<>();
list3.add(obj4);
list3.add(obj5);

System.out.println(mapClass.get(list3));

System.out.println(list1.hashCode());
System.out.println(list2.hashCode());
System.out.println(list3.hashCode());

下面是我看到的输出

hashCode() called - Computed hash: -1704251796
hashCode() called - Computed hash: -587009612
hashCode() called - Computed hash: -1704251796
hashCode() called - Computed hash: -587009612
1
hashCode() called - Computed hash: -1704251796
hashCode() called - Computed hash: -587009612
4567
hashCode() called - Computed hash: -1704251796
hashCode() called - Computed hash: -587009612
**null**
hashCode() called - Computed hash: -1704251796
hashCode() called - Computed hash: -587009612
-1879206775
hashCode() called - Computed hash: -1704251796
hashCode() called - Computed hash: -587009612
-1879206775
hashCode() called - Computed hash: -1704251796
hashCode() called - Computed hash: -587009612
-1879206775

尽管所有 3 个列表的哈希码都相同，mapClass.get(list3) 正在重新调整 null。 list3 与 list1 / list2 具有相同的对象。为什么会出现这种行为？

Answer 1

来自地图 V get(Object key) 文档：

 * ... if this map contains a mapping from a key
 * {@code k} to a value {@code v} such that
 * {@code Objects.equals(key, k)},
 * then this method returns {@code v}; otherwise
 * it returns {@code null}. ...

我不确定您是如何实现 NewClass 的 equals 方法的，但是 NewClass 的以下实现没有 return null调用 System.out.println(mapClass.get(list3));

时

public class NewClass {
    private int id;
    private String name;
    private String mail;

    NewClass(int id,String name,String mail){
        this.id = id;
        this.name = name;
        this.mail = mail;
    }

    @Override
    public int hashCode() {
        return id * name.hashCode() * mail.hashCode();
    }

    @Override
    public boolean equals(Object o) {

        if (o == this) return true;
        if (!(o instanceof NewClass)) {
            return false;
        }
        NewClass newClass = (NewClass) o;

        return newClass.id == id &&
               newClass.name.equals(name) &&
               newClass.mail.equals(mail);
    }
}

此外，正如评论中提到的可变键不是一个好主意，请查看 this link 详细说明原因。

Answer 2

Even though hashcode is same for all the 3 lists, mapClass.get(list3) is retuning null. list3 has same object as list1 / list2. Why is this behaviour ?

我猜这个问题是由你自定义的class的equals()方法引起的。它必须以这样的方式实现，即根据 equals() 相等的一对对象中的每个对象都将具有相同的哈希码。

根据经验，您应该为 class 提供适当的 equals/hasHode 实现，尤其是当它们打算与集合一起使用时。

因为你没有公开 NewClass 的代码，我将使用 java.lang.String class 维护 equals/hasHode demo-purposes.

不变

List<String> list1 = List.of("a", "b", "c");
List<String> list2 = List.of("a", "b", "c"); // list containing the same pooled strings (i.e. references to the same objects)
List<String> list3 = new ArrayList<>(List.of(new String("a"), new String("b"), new String("c")));
System.out.println("list1 is equal to list3: " + list1.equals(list3));
        
Map<List<String>, Integer> map = new HashMap<>();
map.put(list1, 1);
map.put(list2, 2);
map.put(list3, 3);
        
System.out.println("map's size: " + map.size()); // contains a single entry: list3 -> 3
map.forEach((k, v) -> System.out.println(k + " -> " + v));
    
// let's break it!
System.out.println("______________________");
        
list3.add("d"); // list3 contains "a", "b", "c", "d"
List<String> list4 = List.of("a", "b", "c", "d");
        
map.put(list4, 4);
System.out.println("map's size: " + map.size()); // contains two entries!
map.forEach((k, v) -> System.out.println(k + " -> " + v));
// let's check the hashes
System.out.println("hashCodes:\nlist3: " + list3.hashCode() + " list4: " + list4.hashCode());

输出将是：

list1 is equal to list3: true
map's size: 1
[a, b, c] -> 3
______________________
map's size: 2
[a, b, c] -> 3
[a, b, c, d] -> 4
hashCodes:
list3: 3910595 list4: 3910595

如您所见，list 是否包含合并字符串或 non-pooled 字符串并不重要，只要它们与列表相等且顺序相同将相等。

上面代码的第二部分演示了为什么将 List 用作 key.

不是一个好主意

HashMap 旨在与不可变对象一起使用。它由一个数组支持。数组的每个元素都是一个 bucket，对应于 范围的哈希值 ，它可能包含节点的列表（在某个阈值之后，列表被转换为树以提高性能） .

还有 Node 的样子：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
...

当您在 HashMap 上调用方法 put() 时，将计算给定 key 的哈希值。并且基于 hash，它会为那个 key 找到合适的 bucket。然后，将根据 新哈希 检查此存储桶中所有节点的哈希。如果未找到相等的 hash，将创建一个新的 Node 并将其放入该存储桶中。如果两个哈希值发生冲突，那么将使用 equels() 比较这些 keys。如果 returns falsea 新节点 将被创建，否则现有节点的 value 将被替换给定值.

注意字段 key 和 hash 是 final.

在某些情况下，计算散列可能成本很高，并且由于 HashMap 不打算与可变对象一起使用，因此没有必要计算散列对于相同的 key 每次新的比较都会一遍又一遍。

因此，list4 将被视为 新密钥 ，尽管哈希值相同，因为 map 中 list3 的散列永远不会更新。

Answer 3

您的代码的问题在于很多方面：使用 List 作为键，re-using 第二对的相同引用和 NewClass 实现。正如其他人已经指出的那样，您使用 ArrayList 作为 HashMap 键，这是一个糟糕的设计选择，因为作为 mutable 对象，它的 hashCode 可能会发生变化，从而引入失去访问权限的风险它的配对元素。此外，还伤害了您的是 ArrayList 的 hashCode 和 equals 方法是在元素实现所述方法时定义的。

ArrayList 的 equals()

ArrayList 的 hashCode()

HashMap 实现

HashMap 实现为包含桶数组的哈希 table。每个键的 hashCode() 映射到一个桶（数组）索引，不同的键允许具有相同的哈希码（[hashCode 契约][4]）。这就是为什么每个桶可以包含多个 key-value 通过链接数据结构排列的对。因此，当您调用 get 方法时，首先，通过将键的 hashCode 映射到存储桶索引来选择存储桶，然后通过对其键调用 equals() 方法来搜索目标条目。

代码解释

如输出所示，在添加具有不同列表的第二对作为键之后，我们可以看到映射的大小仍然为 1。这是因为您使用了完全相同的引用（obj1 和 obj2）来构建第一个和第二个键，为 list1 和 list2 产生相同的 hashCode，因为 ArrayList 的 hashCode 是建立在它的元素之上的。一旦将第二对添加到 HashMap，其键的 hashCode returns 与第一个键的值相同，索引相同的存储桶然后替换第一对，因为第二对的键等于第一对的键。

现在开始回答您的问题。即使列表的元素是具有相同值的不同引用，只要在传递给构造函数的确切三个字段上定义了 NewClass' equals() 方法（int，字符串，字符串）。我的猜测是 NewClass 的 equals() 方法没有被定义或者它面对不同的领域。 equals() 和 hashCode 应该在同一组字段上工作。事实上，如果我们按如下方式定义您的 NewClass，第三次添加也将替换 HashMap 中包含的唯一对。

public class Test {
    public static void main(String[] args) {
        List<NewClass> list1 = new ArrayList<>();
        List<NewClass> list2 = new ArrayList<>();

        NewClass obj1 = new NewClass(1, "ddd", "eee@gmail.com");
        NewClass obj2 = new NewClass(2, "ccc", "kkk@gmail.com");

        list1.add(obj1);
        list1.add(obj2);

        list2.add(obj1);
        list2.add(obj2);

        Map<List<NewClass>, Integer> mapClass = new HashMap<>();
        mapClass.put(list1, 1234);
        mapClass.put(list2, 4567);

        System.out.println(mapClass.size());
        System.out.println(mapClass.get(list1));

        NewClass obj4 = new NewClass(1, "ddd", "eee@gmail.com");
        NewClass obj5 = new NewClass(2, "ccc", "kkk@gmail.com");
        List<NewClass> list3 = new ArrayList<>();
        list3.add(obj4);
        list3.add(obj5);

        System.out.println(mapClass.get(list3));

        System.out.println(list1.hashCode());
        System.out.println(list2.hashCode());
        System.out.println(list3.hashCode());
    }
}

class NewClass {
    int id;
    String s1, s2;

    public NewClass(int id, String s1, String s2) {
        this.id = id;
        this.s1 = s1;
        this.s2 = s2;
    }

    public int hashCode() {
        return Objects.hash(id, s1, s2);
    }

    @Override
    public boolean equals(Object obj) {
        if (obj == this) return true;
        if (obj == null || obj.getClass() != getClass()) return false;
        NewClass nc = (NewClass) obj;
        return nc.id == id && Objects.equals(s1, nc.s1) && Objects.equals(s2, nc.s2);
    }
}

输出

结论

总之，正如其他人已经说过的那样，您不应该使用 mutable 对象作为 HashMap 的键。应用于密钥内部状态的更改可能会改变其 hashCode，使其配对值无法追踪，甚至最糟糕的是在非常远程的情况下检索另一个密钥的值。这些是关于如何设计 HashMap 键的一些有用指南：

以对象列表为键的 HashMap

HashMap with List of Objects as a Key

java

collections

equals

hashmap

hashcode

ArrayList 的 equals()

ArrayList 的 hashCode()

HashMap 实现

代码解释

输出

结论