Following One Key Into a HashMap and Back Out

The contract only becomes obvious when you watch a lookup happen. Here is one key going in and coming back out, with both methods called by name.

What a hash map does with one key

Step 1 of 5

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 fatal rather than merely slow.

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 everywhere would be a list.