What does hashmap check when it calls containsKey()?

Question

    ArrayList<Integer> lis = new ArrayList<Integer>();
    lis.add(2);
    lis.add(3);
    ArrayList<Integer> lis2 = new ArrayList<Integer>();
    lis2.add(2);
    lis2.add(3);
    HashMap<ArrayList<Integer>, Integer> map = new HashMap<ArrayList<Integer>, Integer>();
    map.put(lis, 7);
    System.out.println(map.containsKey(lis2));

Initially, I expected the code to print out 'false' because lis and lis2 are different objects. Surprisingly, the code printed out 'true'. What does hashmap check when it calls containsKey()?

Answer 1

It checks .hashCode to find the bucket, then uses .equals. List.equals returns true if all the elements are in the same order and are also .equals. ArrayList.hashCode will return the same value for two ArrayList instances with the same elements, so it finds the right bucket, then uses .equals and sees that the lists' elements are the same and in the same order.

For example:

ArrayList<Integer> lis = new ArrayList<Integer>();
lis.add(2);
lis.add(3);
ArrayList<Integer> lis2 = new ArrayList<Integer>();
lis2.add(2);
lis2.add(3);
System.out.println(lis.equals(lis2)); // Prints "true"

It's also worth noting that you should never use a mutable object as the key in your HashMap. By modifying the key, you can cause the bucket that it's in to be invalid. For example, if I do this:

map.put(lis, 7);
lis.add(3);
System.out.println(map.get(lis)); // Prints "null", *not* "7"

This is because adding another element changed the value of lis.hashCode(). When you put the list, the hashCode is used to pick a bucket. By adding the new element, you change the bucket that it would use, but it doesn't change the bucket of the entry that you already added to the map. Adding to the above:

map.put(lis, 7);
lis.add(3);
map.put(lis, 7);
System.out.println(map.size()); // Prints "2"

It resolves to a different bucket the second time, so it treats it as a second element.

In this case, you would use Collections.unmodifiableList to "freeze" the list, add it, then never touch it again:

map.put(Collections.unmodifiableList(lis), 7);

Then later, if you call get().add(3):

map.get(7).add(3);

This will throw a UnsupportedOperationException.

Answer 2

This is because the hashCode of lis and lis2 are equal.

lis2.hashCode() == lis.hashCode() is true.

Method containsKey in source code (HashMap) is as follows:

/**
 * Returns <tt>true</tt> if this map contains a mapping for the
 * specified key.
 *
 * @param   key   The key whose presence in this map is to be tested
 * @return <tt>true</tt> if this map contains a mapping for the specified
 * key.
 */
public boolean containsKey(Object key) {
    Object k = maskNull(key);
    int hash = hash(k.hashCode());
    int i = indexFor(hash, table.length);
    Entry e = table[i]; 
    while (e != null) {
        if (e.hash == hash && eq(k, e.key)) 
            return true;
        e = e.next;
    }
    return false;
}

Answer 3

You defined the hash map as

HashMap<ArrayList<Integer>, Integer> map = new HashMap<ArrayList<Integer>, Integer>();

So the key is a list of integers and the value is an integer.

map.containsKey(lis2) will try to find a match for the given key. So the equals method will be invoked on each key. Since the key is actually a list of integers, the equal method will be invoked on each item of that list in sequence.

That's why the output is true.

If you change any of the items of the second list or even the sequence of the items, then the output will be false.

Answer 4

map.containsKey returns true if this map contains a mapping for the specified key. It uses equals method of the key to check for equality:

key != null && key.equals(k)

And two arraylists are said to be equal, if (copied from ArrayList doc):

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists have the same size, and all corresponding pairs of elements in the two lists are equal. (Two elements e1 and e2 are equal if (e1==null ? e2==null : e1.equals(e2)).) In other words, two lists are defined to be equal if they contain the same elements in the same order.

This implementation first checks if the specified object is this list. If so, it returns true; if not, it checks if the specified object is a list. If not, it returns false; if so, it iterates over both lists, comparing corresponding pairs of elements. If any comparison returns false, this method returns false. If either iterator runs out of elements before the other it returns false (as the lists are of unequal length); otherwise it returns true when the iterations complete.

As the two lists contain the same number of elements in the same order, so they are considered to be equal, and thats why map.containsKey(lis2) is returning true.