Analysis of Java HashMap put Method and Internal Mechanics

HashMap is a fundamental data structure in Java collections, widely used in development and interview questions. This article analyzes the put method implementation.

Underlying structure: HashMap uses a hash table (array of Node<K,V>) where each entry is a linked list (or tree) to resolve collisions. The Node class is defined as:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // constructors and methods...
}

Collision resolution methods include linear probing, pseudo‑random, and chaining. HashMap adopts chaining (linked list) and converts long chains to red‑black trees.

The put method workflow:

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

It first computes the hash of the key:

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

If the table is null, resize() creates an array of default capacity 16 and threshold 12 (load factor 0.75). The insertion position is calculated as (n‑1) & hash, which is equivalent to hash % n when n is a power of two.

When a slot is empty, a new node is stored directly. If a node already exists, the algorithm checks whether the existing key matches; if so, the value is replaced, otherwise the new node is appended to the chain. If the chain length exceeds a threshold, it may be transformed into a tree.

Handling duplicate keys: inserting a second entry with key "name" updates the existing node's value and returns the old value.

Key takeaways:

HashMap capacity is always a power of two; non‑power‑of‑two capacities are rounded up.

Default capacity is 16 with an effective usable size of 12 (load factor 0.75).

When size exceeds the threshold, the table is resized to double its capacity. put performs initialization, hash calculation, slot lookup, collision handling, and possible resizing.

Chain addressing resolves collisions; long chains become red‑black trees.

Keys must correctly implement hashCode() and equals() for proper behavior.