HashMap is one of the most widely used collections in Java applications, primarily for storing key-value pairs with efficient lookup performance. To understand its inner workings, we explore how it manages data storage, resolves collisions, handles resizing, and why it is not thread-safe.

Class Hierarchy and Core Interfaces

HashMap implements several key interfaces:

Map<K, V> — Defines fundamental operations like put, get, and remove. Cloneable — Enables shallow copying via the overridden clone() method. Serializable — Allows serialization for storage or network transmission.

It extends AbstractMap<K, V>, which provides skeletal implementations of common Map methods such as equals(), hashCode(), and toString(), reducing boilerplate code.

Internal Structures

HashMap uses multiple internal structures to optimize performance under varying data conditions:

Node<K, V> — The basic unit for storing key-value entries in a bucket (linked list form). TreeNode<K, V> — A red-black tree node used when a bucket’s chain grows beyond a threshold, improving lookup from O(n) to O(log n). KeySet, Values, EntrySet — Specialized views for iterating over keys, values, or key-value pairs.

Initialization and Load Factor

When creating a new HashMap without parameters:

Map<String, String> map = new HashMap<>();

The default initial capacity is 16, and the load factor is 0.75. The load factor determines when resizing occurs: when the number of entries exceeds capacity × loadFactor.

Why 0.75? It balances memory efficiency and access speed. A higher value reduces memory usage but increases collision likelihood; a lower value reduces collisions at the cost of more memory.

Other constructors allow customizing capacity and load factor:

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0) throw new IllegalArgumentException();
    if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException();
    
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

The tableSizeFor() method ensures the capacity is a power of two, enabling faster indexing via bitwise operations.

When constructing from another Map:

public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

Internally, putMapEntries() calculates an optimal initial size based on the source map’s size and load factor, avoiding unnecessary resizes during population.

Putting Elements: The Core Mechanism

The public put(K key, V value) method delegates to putVal():

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    
    // Initialize or resize table if empty
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    
    // Compute bucket index using bitwise AND: (n - 1) & hash
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        
        // Check if key already exists at head of bucket
        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // If bucket is a tree, insert via tree logic
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // Traverse linked list
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // Convert to tree if chain length exceeds threshold
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // If key found, update value
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    
    // Increment structure modification count and check for resize
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

Key steps:

Hash computation: The key’s hashCode() is processed by an internal hash function to distribute bits evenly. Index calculation: The bucket index is determined using (n - 1) & hash, where n is always a power of two — making this operation equivalent to hash % n but much faster. Collision handling:

  If the bucket is empty, create a new Node.
  If the bucket has a single entry, compare keys directly.
  If the bucket is a tree, insert using red-black tree logic.
  Otherwise, traverse the linked list until finding a match or reaching the end.

Treeification: When a bucket’s chain exceeds TREEIFY_THRESHOLD (default: 8), and the table size is atleast 64, the linked list is converted into a red-black tree to maintain O(log n) performance. Resize trigger: After insertion, if the size exceeds threshold (capacity × load factor), the table doubles in size and rehashes all entries.

Resizing involves creating a new array with double the capacity and redistributing all existing entries. This process ensures that keys are re-mapped to new indices based on the larger array size.

HashMap is not thread-safe because multiple threads modifying the structure simultaneously — especially during resize — can corrupt the linked list or tree structure, leading to infinite loops or data loss.