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