Course contentsShow
← Java
Lesson 1113 of 2,87026. Map ImplementationsFree lesson

What Happens When Two Keys Hash to the Same Bucket

Learn how HashMap handles hash collisions using linked lists to store multiple entries in a single bucket.

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:

  1. HashMap navigates to the calculated bucket index
  2. It finds the bucket already occupied by another key-value pair
  3. It creates a new node containing your key, value, hash, and a reference to the next node
  4. 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.