Bucket Contents: Linked List Nodes
What you'll learn: How HashMap buckets store key-value pairs inside linked list nodes when collisions occur.
The Node Structure
You've learned that HashMap uses an array of buckets and maps hash codes to bucket indices. But what exactly lives inside each bucket? The answer is a linked list of Node objects.
Each Node is a simple container that holds:
- key: The key you stored
- value: The value associated with that key
- hash: The pre-calculated hash code (stored for efficiency)
- next: A reference to the next Node in the chain (or
nullif this is the last)
Why Linked Lists?
When multiple keys hash to the same bucket index (a collision), HashMap doesn't just throw one away. Instead, it chains them together in a linked list within that bucket. Think of it like a coat rack at a restaurant—if multiple coats need the same hook, you hang them one behind the other.
// Simplified conceptual Node structure (actual implementation is more complex)
class Node<K, V> {
final K key;
V value;
final int hash;
Node<K, V> next; // Points to next node in this bucket
}
When you look up a key, HashMap:
- Calculates the bucket index
- Follows the linked list in that bucket
- Compares keys using
equals()until it finds the right Node
An empty bucket contains null. A bucket with one entry points to a Node whose next is null. A bucket with collisions has multiple Nodes chained together.
Key Takeaway: HashMap buckets contain linked lists of Node objects, each storing a key-value pair and pointing to the next Node in the chain, enabling multiple entries to coexist in the same bucket.