collections
intermediateHashMap Internals
Understand the bucket array, hash collisions, and the treeify threshold so you can reason about HashMap performance.
A HashMap stores key-value pairs in an array of buckets and uses the key's hash to decide which bucket holds an entry, giving average O(1) get and put. Understanding the internals explains both why it is fast and the handful of ways it can degrade — which is exactly what interviewers probe.
A coat-check counter with numbered hooks. The ticket number tells you which hook (bucket); if two coats share a hook, you walk the chain hanging from it.
Key Concepts
1
When you put a key, the map computes hashCode(), spreads the bits (Java perturbs the high bits down to reduce collisions), and maps the result to a bucket index. If two keys land in the same bucket — a collision — the entries form a linked list within that bucket. Since Java 8, once a single bucket exceeds the treeify threshold of 8 entries (and the table is at least 64 wide), that bucket converts from a linked list into a balanced red-black tree, so worst-case lookups within it drop from O(n) to O(log n). The map also tracks a load factor, 0.75 by default: when the entry count exceeds capacity × load factor, the table resizes to double its capacity and every entry is rehashed into the larger array.
hashCode()
2
The everyday consequences are worth internalising. hashCode() and equals() must be consistent and well-distributed — a poor hashCode that returns a constant collapses every key into one bucket and turns the map into a list. Keys should be immutable, because mutating a key after insertion changes its hash and effectively loses the entry. And if you can estimate the final size, presizing the map avoids repeated resizes. Note that plain HashMap is not thread-safe; concurrent writes can corrupt it or, historically, spin into an infinite loop during resize.
hashCode()equals()hashCodeHashMap