How does HashMap handle hash collisions, and what changed in Java 8 (treeification)?

A hash collision happens when two different keys map to the same bucket index. HashMap has always handled this by chaining multiple entries in the same bucket:

Pre-Java 8: each bucket was a simple singly-linked list of entries. Looking up a key meant walking the list and calling equals() on each entry — worst case O(n) if many keys collided into one bucket. This could be forced adversarially, for example with crafted String keys sharing the same hashCode(), as a denial-of-service vector.

Java 8+ (treeification): if a single bucket's chain grows beyond TREEIFY_THRESHOLD (8 entries) and the table itself has at least MIN_TREEIFY_CAPACITY (64) buckets, that bucket's linked list converts into a red-black tree, keyed by hash code (and, if comparable, natural ordering as a tiebreaker). This bounds worst-case lookup within that bucket to O(log n) instead of O(n).

If the table is too small (fewer than 64 buckets), a busy bucket triggers a resize (doubling capacity) instead of treeification — a small table just needs its collisions spread across more buckets, not a smarter per-bucket structure.

If entries are later removed and a treeified bucket shrinks below UNTREEIFY_THRESHOLD (6), it converts back to a plain linked list, since the tree's extra memory overhead isn't worth it for a small bucket.

This change specifically hardens HashMap against algorithmic-complexity attacks, where an attacker supplies many keys engineered to collide, without changing the map's average-case O(1) behavior for well-distributed keys.