HashMap Internals: Buckets, Hashing, and Resizing

HashMap is a bucket array where each slot is indexed by the key's hash — put("name", "John") XOR-mixes upper and lower 16 bits of hashCode(), then masks with capacity - 1 to pick a bucket. That's why put and get are O(1) on average.

Collision handling:

• Two keys in the same bucket form a linked list — worst case O(n) before Java 8
• Java 8 treeification: chains exceeding 8 nodes convert to a Red-Black tree, capping worst case at O(log n)
• Reverts to a list below 6 nodes to avoid overhead on short chains

Resizing:

• Default capacity 16, load factor 0.75 → resize triggers at just 12 entries
• Doubles the array and rehashes everything — O(n), runs synchronously on the triggering thread
• Can cause p99 latency spikes in hot paths; fix: new HashMap<>(2048) for ~1000 entries

equals/hashCode contract:

• Override equals() but forget hashCode(): put stores in one bucket, get looks in another — silently returns null
• Java records auto-generate both correctly — use them for map keys

I recommend pre-sizing HashMap in hot paths and using records or carefully implemented equals()/hashCode() for keys.