WalkthroughDifficulty: Intermediate2 min

How a HashMap Uses hashCode and equals: A Walkthrough

One key going into a map and coming back out, with both methods called by name.

A HashMap uses hashCode to choose which bucket, one of its internal groups of entries, to look in, and equals to decide which entry in that bucket matches. Following one key through a put and a get shows why the two methods must agree. You need a key class that overrides both, such as Order by reference:

What a hash map does with one key

put: the key's hash code is taken

java

map.put(new Order("AB-1", 1999), "paid");

hashCode() is called on the key and produces an int. Nothing about the map's contents is consulted; the number depends only on the key.

put: the hash is turned into a bucket number

The map has a fixed number of buckets, and it reduces the hash to one of them. Two keys with the same hash always land in the same bucket; two keys with different hashes usually do not.

put: the bucket is searched with equals

If the bucket already holds an entry whose key is equals to this one, its value is replaced. Otherwise the new entry is added to the bucket. equals is called here, not ==.

get: the hash is taken again

java

String status = map.get(new Order("AB-1", 1999));

A different object, with the same contents. hashCode() is called on it, and this is the step the whole contract exists for: if it produces a different number from step one, the map is about to look in the wrong bucket.

get: that one bucket is searched with equals

text

paid

The map compares against the entries in that bucket only. It never looks anywhere else, which is what makes a lookup fast and what makes a wrong hash code, the number that chose the bucket, fatal rather than merely slow.

You know the lookup worked when get returns paid for a different object with the same contents. The run to remember is that hashCode chooses where to look and equals decides what was found. Both are called on every lookup, in that order, and a map that consulted equals on every entry would be no faster than a list.

← → move through sections and cards