How a Map Finds One Value Without Looking at the Others

A lookup table with two million rows in it. Finding one by reference takes the same time as finding one in a table of twenty, and the code does not appear to search anything.

A hash map does not look for your key. It works out where the key would be if it were there, and looks only in that one place.

A key's hash selects one bucket out of many, and only that bucket is searched

The three steps of a lookup, and what each one uses
Step	Uses	Result
Hash the key	`hashCode()` on the key	An `int`
Choose a bucket	That `int` and the number of buckets	One bucket out of many
Search that bucket	`equals()` on the key	The entry, or nothing

Nothing outside that one bucket is ever examined, which is why the size of the map barely matters. The cost is the hash, plus whatever is in the bucket — usually nothing or one entry.

So a map's speed is borrowed from the key's hashCode. Everything surprising about maps in the rest of this topic comes from that borrowing going wrong in one of three ways.