How does HashMap handle hash collisions, and what changed in Java 8 (treeification)?
Quick Answer
Before Java 8, colliding entries within a bucket were stored as a simple linked list, giving O(n) worst-case lookup within that bucket. Since Java 8, if a bucket accumulates more than 8 entries (TREEIFY_THRESHOLD) and the table has at least 64 buckets, that bucket is converted into a red-black tree, bounding worst-case lookup to O(log n); it converts back to a list if entries drop below 6 (UNTREEIFY_THRESHOLD).
Detailed Answer
A hash collision occurs 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 required walking the list and calling equals() on each entry — worst case O(n) if many keys collided into one bucket (which could be forced adversarially, e.g., crafted String keys with identical 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 is converted into a red-black tree, keyed by hash code (and, if comparable, natural ordering as a tiebreaker) — bounding worst-case lookup within that bucket to O(log n) instead of O(n).
If the table is too small (< 64 buckets), a busy bucket instead triggers a resize (doubling capacity) rather than treeification — since 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's converted 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.