What does a hashmap check do when calling 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)); 

At first, I expected the code to print “false” because lis and lis2 are different objects. Surprisingly, the code printed "true". What does a hashmap check do when calling containsKey ()?

Answer 1

It checks .hashCode to find the bucket, and then uses .equals . List.equals returns true if all items are in the same order and .equals as .equals . ArrayList.hashCode will return the same value for two instances of ArrayList with the same elements, so it will find the right bucket, then use .equals and see that the list items are the same and in the same order.

For instance:

 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 a key in a HashMap . By changing the key, you can cause the bucket 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 list, hashCode used to select the bucket. By adding a new item, you will change the bucket that it will use, but it will not change the record bucket that you have already added to the map. Addendum to the above:

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

He resolves another bucket a second time, so he sees it as the second element.

In this case, you should use Collections.unmodifiableList to “freeze” the list, add it, and then never touch it:

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

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

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

This will raise an UnsupportedOperationException .

Answer 2

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

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

The method containsKey in the source code (HashMap) 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 have identified the hash map as

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

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

map.containsKey (lis2) will try to find a match for this key. Thus, the equals method will be called on every key. Since the key is actually a list of integers, the equality method will be called for each element of this list in sequence.

That is why the conclusion is right.

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

Answer 4

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

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

And two arraylists are considered equal if (copied from an ArrayList document):

Compares the specified object with this list for equality. Returns true if and only if the specified object is also a list, both lists are the same size, and all the corresponding pairs of elements in 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 to see if the specified object is specified. 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 the corresponding pairs of elements. If any comparison returns false, this method returns false. If either the iterator ends before the other, it returns false (since the lists are of unequal length); otherwise it returns true when the iteration is complete.

Since the two lists contain the same number of elements in the same order, therefore they are considered equal , and therefore map.containsKey(lis2) returns true .