HashMap Example: A Crowded Bucket Turns Into a Tree

Keys that all hash to 1, and the safety net Java 8 added for exactly that case.

When one bucket collects too many entries, a Java 8 or later HashMap converts it from a chain into a balanced tree, so a lookup in that bucket compares a handful of keys instead of all of them. A key class whose hash code, the number hashCode() returns to choose a bucket, is always 1 shows it:

java

record BadKey(String id) {
    @Override public int hashCode() { return 1; }
}

every key hashes to the same number, so every key lands in the same bucket

With a few entries the bucket is a short chain, and each lookup walks it. Once the chain reaches eight entries, and the map has at least sixty-four buckets, the map converts that one bucket into a balanced tree, ordered by hash and then by the keys' natural order, the order their compareTo defines, where they have one.

Cost of a lookup in one overloaded bucket holding n entries
Bucket shape	A lookup compares
A chain	Up to n keys
A tree	About log n keys

A thousand colliding keys means a thousand comparisons as a chain and about ten as a tree, so the conversion turns a disaster into something merely bad. It is a safety net, added partly because deliberately colliding keys were used to slow web servers down on purpose.

Nothing here fixed the hashCode. The map is still doing work it should not have to, and the right answer is always a key whose hash spreads.

Java
Hash Tables
Performance

← → move through sections and cards