How does HashMap work internally in Java?

Understanding HashMap internals — hashing, buckets, collisions, resizing, and treeification — is one of the most commonly asked Java interview topics at mid-to-senior level.

// Internal structure:
// - Node[] table  — array of buckets (initially null, lazily allocated)
// - Default capacity: 16, load factor: 0.75
// - When size > capacity * loadFactor → resize (double capacity)

// put(key, value) steps:
// 1. Compute hash: (h = key.hashCode()) ^ (h >>> 16)  — spread high bits
// 2. Bucket index: hash & (capacity - 1)
// 3. If bucket empty: insert new Node
// 4. If bucket occupied (collision):
//    - Walk linked list: if key equals an existing node, update value
//    - Else append to linked list
//    - If list length >= TREEIFY_THRESHOLD (8) AND capacity >= 64:
//      convert to balanced Red-Black tree (O(log n) instead of O(n))

// Performance characteristics
// Best case (no collisions): O(1) get, put
// Worst case (all in one bucket, pre-Java 8): O(n)
// Worst case (all in one bucket, Java 8+): O(log n) after treeification

// Why the spread: hashCode() of strings/integers often has poor high-bit distribution
// The XOR spread: (h) ^ (h >>> 16) mixes high and low 16 bits

// Thread safety
// HashMap is NOT thread-safe
// ConcurrentHashMap: segments replaced by per-bin locking in Java 8
// Hashtable: fully synchronized (legacy, slow)
// Collections.synchronizedMap: wraps HashMap, one lock for all ops

Map map = new HashMap<>(32, 0.75f); // pre-size to avoid rehash

The load factor trade-off: a lower load factor (e.g., 0.5) means fewer collisions but more memory wasted on empty buckets. A higher load factor (e.g., 0.9) uses memory efficiently but increases collision probability, degrading performance toward O(log n) or O(n). The default 0.75 is the empirically best trade-off for general use.