HashMap Internals
HashMap stores key-value pairs in an array of buckets. Keys are hashed; the hash determines the bucket index. Collisions (different keys in the same bucket) are handled by a linked list (or tree) at that bucket.
HashMap = a post office with numbered P.O. boxes. hashCode picks the box number, the linked list is mail inside. Treeify at 8 = when one box overflows, it gets upgraded to a sorted filing cabinet.
Default initial capacity: 16 buckets. Load factor: 0.75 (resize when size > capacity * 0.75). Resize: new array 2x the size, all entries rehashed and redistributed. Treeification (Java 8+): when a single bucket's linked list reaches 8 entries, it converts to a red-black tree (TreeNode) for O(log n) lookup; untreeifies back to a list at 6. hash() applies a secondary hash (spread higher bits into lower bits) to reduce collisions from poor hashCode() implementations. HashMap is NOT thread-safe — concurrent reads during a resize caused infinite loops in Java 7 (fixed in Java 8 by using a tail-insertion algorithm).
The treeify threshold of 8 was chosen statistically — with a good hash function, the probability of 8 collisions in a bucket follows a Poisson distribution with probability ~0.00000006. The HashMap's internal Node class becomes TreeNode (extends LinkedHashMap.Entry) for treeified buckets, adding left/right/parent/red fields. LinkedHashMap extends HashMap and maintains a doubly-linked list of entries in insertion order (or access order for LRU caches). The Java 8 HashMap resize fix changed from head-insertion (which reversed bucket order) to tail-insertion, eliminating the cycle that caused infinite loops under concurrent access without synchronization.
HashMap uses an array of buckets where each bucket is a linked list that treeifies to a red-black tree at size 8 (reverts at 6). Resize triggers when occupancy exceeds capacity × 0.75 — doubles the array and rehashes all entries. A good hashCode() is critical: poor distribution fills a few buckets deeply, degrading O(1) gets to O(n) (or O(log n) after treeify). HashMap is not thread-safe — use ConcurrentHashMap for concurrent access; synchronized access during iteration still risks ConcurrentModificationException.
Using a mutable object as a HashMap key and then mutating it changes its hashCode(), which means the map can no longer find the entry — it's effectively lost in the map (a silent memory leak).