CODEWITHSUNDEEP
javacollectionshashmapequalshashcode
Lolly
Lolly

Reputation: 36392

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 ?

Upvotes: 3

Views: 3874

Answers (3)

dani-vta
dani-vta

Reputation: 6830

Code Problems

The problem with your code lies in many aspects:

  • Using lists as keys
  • Re-using the same references for more than one entry's key
  • The implementation of NewClass

As others have already pointed out, you're using ArrayList instances as keys, which is a bad design choice, since the hashcode of mutable objects is subject to change, introducing the risk of losing access to the paired values.

Furthermore, since the implementation of ArrayList.equals() and ArrayList.hashCode() is based on the equals() and hashCode() of its elements, you also need to make sure that their class implements the methods properly.

HashMap Implementation

The HashMap class is implemented as an array of buckets, where a bucket is either a linked list or a tree structure. When a key-value pair is added to a HashMap, the key's hashcode is mapped to a bucket's index, and then the entry is added to the bucket. This means that a bucket can contain multiple entries with different keys, since different objects can share the same hashcode (see the hashCode contract). Once a bucket has been selected, the HashMap verifies whether this bucket contains a pair whose key is equal to the key of the new entry. If it does, the pair with the matching key is updated with the new entry's value; if it doesn't, the new entry is simply added to the bucket.

Code Explanation & Answer

As shown from the output above, after adding the second entry with a different list as its 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 construct both the first and second key. In this scenario, regardless of NewClass providing a definition for equals() and hashCode(), the two lists will always be equal and yield the same hashcode. This is because the hashcode of an ArrayList is computed from the hashcode of its elements (both lists contain the same references). While ArrayList.equals() relies on the Objects.equals method, which first compares the memory address of the two given references, and then invokes the equals() method of the first parameter. Hence, the second entry updating the first one, as explained in the section above.

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?

Instead, when you're trying to retrieve with list3 the value associated to list1 or list2, you're getting null because NewClass does not provide a proper definition of the equals() and hashCode() methods. These methods should be defined on the same set of attributes as explained in the equals and hashCode contract.

Here, I've attached an implementation of NewClass which honors the equals() and hashCode() contract, and that allows the first entry's value to be returned when list3 is passed.

public 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);
    }
}

Conclusions

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

Upvotes: 1

Alexander Ivanchenko
Alexander Ivanchenko

Reputation: 28968

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.

Upvotes: 1

happy songs
happy songs

Reputation: 873

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.

Upvotes: 2

Related Questions