Collision Handling: Chaining Strategy
You'll learn how HashMap stores multiple entries in the same bucket when hash collisions occur.
The Collision Problem
Even with good hash functions and hash spreading, two different keys can sometimes map to the same bucket index. When this happens, we have a hash collision. HashMap must store both entries without losing either one.
The Chaining Solution
HashMap uses a strategy called chaining to handle collisions. When multiple entries hash to the same bucket, they're stored together as a linked list of nodes within that bucket.
Think of it like a library shelf (the bucket): if multiple books need to go in the same spot, you simply stack them together. To find a specific book, you check each one in the stack until you find the right title.
How It Works
When you insert a key-value pair:
- HashMap calculates the bucket index from the key's hash code
- It checks if that bucket already contains entries
- If the bucket is empty, the new entry becomes the first node
- If the bucket already has entries, HashMap traverses the linked list within that bucket, checking each key with
equals() - If the key already exists, the value is updated
- If the key is new, a new node is added to the list in that bucket
When you retrieve a value, HashMap goes to the bucket and walks through the linked list, using equals() to find the matching key.
Performance Consideration
With chaining, a bucket can hold any number of entries. If many collisions occur in one bucket, that bucket's linked list grows longer, degrading search performance from O(1) toward O(n) for that bucket.
Key Takeaway: HashMap handles hash collisions by chaining multiple entries together as a linked list within the same bucket, using equals() to distinguish between different keys that share the same bucket.