What Happens When Two Keys Hash to the Same Bucket
You'll learn: How HashMap stores multiple key-value pairs in the same bucket when hash collisions occur.
When two different keys produce the same bucket index (a hash collision), HashMap doesn't just overwrite the existing entry. Instead, it stores multiple entries in that single bucket using a linked list structure.
The Collision Resolution Process
When you add a key-value pair to a bucket that already contains an entry:
- HashMap navigates to the calculated bucket index
- It finds the bucket already occupied by another key-value pair
- It creates a new node containing your key, value, hash, and a reference to the next node
- This new node is linked to the existing node(s), forming a chain
Think of it like a parking lot: each parking spot (bucket) normally holds one car (entry). When all spots are full but more cars arrive, you start stacking cars vertically at each spot. To find your car, you must check each one in the stack at that location.
Why Linked Lists?
The linked list allows HashMap to store an unlimited number of entries in a single bucket. During a get() operation, HashMap:
- Jumps to the bucket using the hash code
- Walks through the linked list, checking each node's key with
equals() - Returns the value when it finds a matching key
This is why both hashCode() and equals() are critical: the hash gets you to the right bucket, and equals() finds the right entry within that bucket's chain.
Key Takeaway: When hash collisions occur, HashMap uses linked lists (chaining) to store multiple key-value pairs in a single bucket, checking each entry sequentially using equals() to find the correct match.