1. Overview

When you call:

map.put("name", "John");

Java performs several internal operations — hashing, indexing, bucket management, collision handling, resizing, and finally storing the key-value pair.

---

2. Step-by-Step Internal Process of put()

Let’s break it down:

Step 1: Calculate the hash of the key

• The key’s hash code is computed using: int hash = hash(key);
• In Java 8, this hash function is defined as: static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
• This improves distribution by mixing the high and low bits of the hash code (helps avoid collisions).

If the key is null, hash = 0.

---

Step 2: Determine the bucket index

• The index where the entry should be placed is calculated as: index = (n - 1) & hash; where n is the current size of the internal array (called the table, initially 16).
• The & operation is a fast way to get modulus when the array size is a power of 2.

Example:

hash = 123456
table.length = 16
index = (16 - 1) & 123456 = 0 to 15

---

Step 3: Check if a bucket already exists at that index

• Each bucket (array element) in a HashMap can hold:
  • null → empty bucket
  • Node<K, V> → a linked list of entries
  • TreeNode<K, V> → a red-black tree (if too many collisions)
• Internally, the bucket array is: transient Node<K,V>[] table; Each Node object contains: static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; }

---

Step 4: Handle three possible cases

1. Case 1: Empty bucket
   • If no entry exists at that index: table[index] = new Node<>(hash, key, value, null);
   • The key-value pair is simply added as the first node.
2. Case 2: Key already exists
   • If a node with the same key exists, the value is replaced: if (existingNode.key.equals(key)) existingNode.value = newValue;
   • This ensures only one unique key per map.
3. Case 3: Collision
   • If another key maps to the same index (hash collision), the new node is chained to the existing one using a linked list or red-black tree:
     • If the bucket contains a linked list: append the new node.
     • If the list size exceeds 8, it is converted into a red-black tree (treeification) for better performance (O(log n) lookup instead of O(n)).

---

Step 5: Check load factor and resize if needed

• Every HashMap has a load factor (default 0.75).
• When the number of entries exceeds (capacity * loadFactor), the map resizes — doubles the table size.

For example:

Default initial capacity = 16
Load factor = 0.75
Threshold = 16 * 0.75 = 12

When the 13th element is inserted, the map resizes to 32, and all keys are rehashed and redistributed.

---

Step 6: Return the old value (if any)

• The put() method returns the previous value associated with the key, or null if the key was not already present.

---

3. Visual Flow Summary

put(key, value)
   ↓
hash = hash(key)
   ↓
index = (n - 1) & hash
   ↓
if (bucket[index] is empty)
    create new node
else
    traverse linked list or tree
        if key exists → replace value
        else → append node
   ↓
if (size > threshold)
    resize()
   ↓
return oldValue (or null)

---

4. Example with Null Key

HashMap<String, Integer> map = new HashMap<>();
map.put(null, 100);

• Hash for null key = 0.
• It is always stored in bucket table[0].
• Any subsequent null key entry replaces the previous one.

---

5. Important Points to Remember

Concept	Description
Hash Function	(h = key.hashCode()) ^ (h >>> 16) improves hash distribution
Collision Handling	Uses linked list or tree (Java 8+)
Null Key	Stored in bucket 0
Load Factor	Default 0.75 — controls when resizing happens
Resizing	Doubles array size and rehashes entries
Thread Safety	Not thread-safe; use ConcurrentHashMap if needed
Value Replacement	put() overwrites existing value if key already exists

---

6. Example Code (with comments)

import java.util.HashMap;

public class HashMapPutInternal {
    public static void main(String[] args) {
        HashMap<String, String> map = new HashMap<>();

        map.put("A", "Apple");   // New entry
        map.put("B", "Ball");    // New entry
        map.put("A", "Air");     // Replaces old value for key "A"

        System.out.println(map.get("A")); // Output: Air
    }
}

---

7. Key Takeaway

When you call put():

1. HashMap calculates hash.
2. Determines the index (bucket).
3. Checks for existing key or collision.
4. Adds or replaces the value.
5. Resizes if threshold exceeded.
6. Returns old value or null.

Internally, it balances speed, space efficiency, and hash distribution using bit manipulation, linked lists, and trees.