A Hundred Keys Spread Over Sixteen Buckets

A fresh map has sixteen buckets. Putting a hundred keys into sixteen buckets is not a problem, and watching why is what makes the rest of the topic legible.

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. The map notices and rebuilds itself, which is a later card.

The third row is the case that matters most and happens least by accident. It is what a hash map looks like when the keys' hashCode returns the same number for everything — every lookup becomes a walk, and the map has quietly become a list.

Java
Hash Tables
Java Collections