How a HashMap Finds a Value: Hashing and Buckets

A lookup in a map of two million takes about as long as one in a map of twenty.

A HashMap stores its entries in an array of buckets. To find a key, it computes the key's hashCode(), turns that number into a bucket index, and searches only that one bucket with equals(). It never looks at the rest of the map, which is why lookups stay fast however large it grows.

A lookup table with two million rows: finding one by reference takes about as long as in a table of twenty, and the code does not appear to search anything. The map works out where the key would be, and looks only there:

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. 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 comes from that borrowing going wrong: keys that all hash alike, keys whose hash changes, or too many entries for the buckets.

On the Java Collections cheatsheet

← → move through sections and cards