'HashMap with List of Objects as a Key

in HashMap when I pass List of Objects as Key I get different results.

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

NewClass obj1 = new NewClass(1, "ddd", "[email protected]");
NewClass obj2 = new NewClass(2, "ccc", "[email protected]");

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", "[email protected]");
NewClass obj5 = new NewClass(2, "ccc", "[email protected]");
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());

Below is the output I see

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

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 ?

javacollectionshashmapequalshashcode


Solution 1:[1]

The problem with your code lies in many aspects: using a List as a key, re-using the same references for a second pair and the NewClass implementation. As others have already pointed out, you're using as a HashMap key an ArrayList which is a bad design choice because as a mutable object its hashCode is subject to change introducing the risk of losing access to its paired element. Furthermore, what is also hurting you is that the hashCode and the equals methods of the ArrayList are defined on the elements' implementation of said methods.

ArrayList's equals()

enter image description here

ArrayList's hashCode()

enter image description here

enter image description here

HashMap Implementation

The HashMap is implemented as a Hash table containing an array of buckets. Each key's hashCode() is mapped to a bucket (array) index and different keys are allowed to have the same hashcode ([hashCode contract][4]). This is why each bucket can contain multiple key-value pairs arranged via a Linked data structure. So, when you're invoking the get method, first, a bucket is selected by mapping the key's hashCode to the bucket index, then the target entry is searched by calling the equals() method on its key.


Code Explanation

As shown from the output, after adding the second pair with a different list as the key, we can see that the map's size is still 1. This is because you've used the exact same references (obj1 and obj2) to build both the first and second key, yielding the same hashCode for list1 and list2, as the ArrayList's hashCode is built upon its elements. Once, the second pair is added to the HashMap, its key's hashCode returns the same value of the first key, indexing the same bucket and then replacing the first pair, since the second key equals the first pair's key.

Now getting to your question. The situation described would have taken place even if the List's elements had been different references with same values as long as the NewClass' equals() method had been defined on the exact three fields passed to the constructor (int, String, String). My guess is that the NewClass' equals() method hasn't been defined or it confronts different fields. Both equals() and hashCode should work on the same set of fields. In fact, if we define your NewClass as follows, also the third addition will replace the only pair contained within the 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", "[email protected]");
        NewClass obj2 = new NewClass(2, "ccc", "[email protected]");

        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", "[email protected]");
        NewClass obj5 = new NewClass(2, "ccc", "[email protected]");
        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);
    }
}


Output

enter image description here

Conclusions

In conclusion, as others have already said, you shouldn't be using mutable objects as keys for a HashMap. The changes applied on a key internal state may alter its hashCode, making its paired value untraceable or even worst retrieving another key's value in a very remote scenario. These are some helpful guidelines on how to design a HashMap key:

Solution 2:[2]

From map V get(Object key) documentation:

 * ... 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}. ...

I'm not sure how you implemented the equals method of NewClass, but the following implementation of NewClass doesn't return null when calling 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);
    }
}

Also, as mentioned in the comments mutable keys are not a good idea, please check this link which details why.

Solution 3:[3]

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 ?

I guess this problem caused by the equals() method of your custom class. It has to be implemented in such a way that each object in a pair of objects that are equal according to equals() will have the same hash code.

As a rule of thumb, you should provide your classes with proper equals/hasHode implementations, especially when they are intended to be used with collections.

Since you didn't expose the code of NewClass I'll use java.lang.String class which maintains equals/hasHode invariant for 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());

The output will be:

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

As you can see, it doesn't matter whether a list contains pooled or non-pooled string, as soon as they equal and have the same order the lists will be equal.

The second part of the code above demonstrates why it's not a good idea to use List as a key.

HashMap is intended to be used with immutable objects. It's backed by an array. Each element of the array is a bucket that corresponds to a range of hashes, and it might contain a list of nodes (after a certain threshold a list get transformed into a tree to improve performance).

And that how the Node look like:

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

When you invoke method put() on a HashMap, the hash of the given key will be calculated. And based on the hash, it'll find an appropriate bucket for that key. Then, hashes of all nodes in this bucket will get checked against the new hash. If equal hash wasn't found, a new Node will be created and placed in that bucket. In case when two hashes collide, then these keys will be compared using equels(). And if returns falsea new node will get created, otherwise the value of the existing node will be replaced by the given value.

Note that fields key and hash are final.

Computing the hash might be very costful in some cases, and since HashMap isn't intended to be used with mutable objects, it's unnecessary to calculate the hash for the same key over and over with each new comparison.

Hence, list4 will be treated as a new key, although the hashes are the same, because the hash of list3 in the map will never get updated.

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1
Solution 2
Solution 3

Related Questions