ExampleDifficulty: Intermediate1 min

HashMap Example: A Hundred Keys Across Sixteen Buckets

Why a map does not stay small, and what it becomes when every key hashes alike.

How evenly keys spread across buckets decides how much work each lookup does. A new HashMap has sixteen buckets; counting word occurrences puts a hundred distinct words into it:

java

Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
    counts.merge(word, 1, Integer::sum);
}

What a well-spread hundred keys look like across buckets
Buckets	Keys	Keys per bucket, on average	A lookup compares
16	100	About 6	About 6 keys
256	100	Under 1	0 or 1 key
256	100 with identical hashes	All 100 in one	Up to 100 keys

The first row is why a map does not stay at sixteen buckets: six comparisons per lookup is six times the cost of one, so the map grows its bucket array and spreads the keys out again.

The third row matters most and rarely happens by accident. It is a map whose keys' hashCode returns the same number for everything: every lookup becomes a walk, and the map has quietly become a list.

← → move through sections and cards