HashMaps: Collisions & Resizing

Collisions: When Two Keys Map to the Same Index

A collision occurs when two different keys produce the same array index after hashing and modulo. For example, both "apple" and "mango" might hash to index 5. Since you cannot store two values in one slot, you need a collision resolution strategy.

Chaining (most common in practice):
Each array slot holds a pointer to a Linked List of all key-value pairs that mapped to that index. On lookup, you hash to the index, then scan the linked list for the exact key.

Index 5: → [("apple", "red")] → [("mango", "yellow")] → null

Open Addressing (alternative):
When a collision occurs, probe for the next available slot using a defined sequence (linear probing, quadratic probing, or double hashing). All data stays in the array itself — no linked lists. Better cache performance but more complex deletion logic.

Impact of collisions on performance:
If many keys collide at the same index (a "hot spot"), the linked list at that index grows long. In the worst case — all N keys hash to the same index — every lookup degrades to O(N) list traversal. This is why hash function quality matters and why adversarial inputs can deliberately cause hash collisions to degrade performance (a real security concern called a Hash DoS attack).

Resizing: The Load Factor

To prevent chains from growing too long, HashMaps monitor their load factor:

Load Factor = (Number of stored entries) / (Array capacity)

When the load factor exceeds a threshold (typically 0.75 in Java's HashMap), the map rehashes:

1. Allocate a new backing array of double the size.
2. Re-compute the index for every existing key-value pair (because hash(key) % new_size produces different indices than hash(key) % old_size).
3. Insert each pair into the new array.

This is an O(N) operation, but like dynamic array resizing, it happens infrequently enough that the amortized cost per insertion remains O(1).

Key Point: The load factor threshold of 0.75 is a deliberate engineering trade-off. A lower threshold (e.g., 0.5) means fewer collisions and faster lookups, but wastes more memory. A higher threshold (e.g., 0.9) saves memory but increases collision probability and degrades lookup performance. This trade-off — time vs. space — is a recurring theme in systems design interviews. When an interviewer asks "how would you tune this HashMap for a read-heavy workload?", the answer involves lowering the load factor to reduce collision chains at the cost of higher memory usage.