A Bucket That Grew Long Enough to Become a Tree

A deliberately bad key class, and what a map does once one bucket has filled up with 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 handful of 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 from a chain into a balanced tree, ordered by hash and then by the keys' natural order where it can.

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 is a thousand comparisons as a chain and about ten as a tree, so the conversion turns a catastrophe into something merely bad. It is a safety net, added in Java 8 partly because deliberately colliding keys were a denial-of-service technique against web servers.

What to notice: nothing here fixed the hashCode. The map is still doing work it should not have to, and the right answer is always a key that spreads.

Java
Hash Tables
Performance