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

put() Operation: Insertion Process

Step-by-step walkthrough of inserting a key-value pair, from hashing to bucket traversal to insertion.

What You'll Learn

You'll learn exactly how HashMap inserts a key-value pair step-by-step, from calculating the hash to finding or creating the right bucket entry.

The Insertion Journey

When you call put(key, value) on a HashMap, a precise sequence unfolds to store your entry efficiently.

Step 1: Calculate the Hash

HashMap first calls key.hashCode() to get the raw hash value. This integer represents your key's fingerprint. HashMap then applies secondary hashing (hash spreading) to improve distribution across buckets.

Step 2: Determine the Bucket

Using the processed hash, HashMap calculates which bucket index should hold this entry:

index = hash & (array.length - 1)

This maps the hash to a valid array position.

Step 3: Check the Bucket

HashMap looks at the calculated bucket. It can be in one of two states:

  • Empty: No entries yet exist here
  • Occupied: One or more entries already live in this bucket (a collision scenario)

Step 4: Traverse or Insert

If the bucket is empty, HashMap creates a new node containing your key-value pair and places it directly in the bucket.

If the bucket is occupied (collision detected), HashMap traverses the linked list of nodes in that bucket:

  • It compares your key with each existing key using equals()
  • If a match is found: The old value is replaced with your new value, and the old value is returned
  • If no match exists: A new node is added to the end of the chain

The Result

Your key-value pair is now stored, and HashMap returns either null (new key) or the previous value (replaced key).

Key Takeaway: The put() operation combines hashing for bucket selection with traversal and equality checking for collision resolution, ensuring each key maps to exactly one value.