HashMap is one of the most widely used key-value containers in Java. Since JDK 8, its underlying structure became a combination of "array + linked list + red-black tree", making it a core component of the Java Collections Framework.

You can abstract its key fields like this:

        public class HashMap<K, V> {
    transient Node<K, V>[] table;  // hash bucket array
    transient int size;            // number of key-value pairs
    int threshold;                 // resize threshold
    final float loadFactor;        // load factor
}

    

Each bucket holds linked list nodes or red-black tree nodes:

        static class Node<K, V> {
    final int hash;
    final K key;
    V value;
    Node<K, V> next;
}

    

What are hash buckets?

Think of table as a row of slots, each slot being a "bucket".

When you call put(key, value), HashMap:

1. Computes a hash value for the key
2. Finds the bucket index based on the hash
3. Stores the key-value pair in that bucket

The bucket index formula is roughly:

        int index = hash & (table.length - 1);

    

Bitwise AND is used instead of modulo. This requires table.length to always be a power of two — which is why HashMap capacity is always a power of two.

What does hash() do?

HashMap does not use key.hashCode() directly. It applies a "perturbation" step:

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

    

XOR-ing the high 16 bits with the low 16 bits makes the higher bits participate in the bucket index calculation, reducing hash collisions.

Without this, many high-bit patterns would be discarded by & (n-1), leading to more collisions.

How are hash collisions handled?

Different keys may map to the same bucket — that is a hash collision.

HashMap resolves this with separate chaining:

• Multiple entries in the same bucket are linked as a list
• In JDK 8+, when the list length exceeds 8 and the array length is >= 64, the list is converted to a red-black tree

The benefit:

• Linked lists are simple and cheap when collisions are rare
• Long linked lists make lookup O(n), but a red-black tree reduces that to O(log n)

A red-black tree reverts to a linked list when its node count drops to <= 6.

How does put work?

map.put(key, value) roughly:

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

    

putVal logic at a high level:

1. If table is empty, initialize by resizing first
2. Compute bucket index i = (n-1) & hash
3. If the bucket is empty, create a new node and place it there
4. If the bucket is not empty:
   • If the first node has the same key, overwrite its value
   • If it is a tree node, follow the tree insert path
   • Otherwise traverse the list: overwrite if a matching key is found, or append at the end
5. If the list length reaches >= 8 after appending, consider converting to red-black tree
6. If size exceeds threshold, trigger a resize

How does get work?

map.get(key) roughly:

        public V get(Object key) {
    Node<K, V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

    

getNode logic:

1. Compute the bucket index from hash
2. Check if the first node in the bucket matches the key
3. If not, determine whether it is a tree or list and follow the respective lookup logic

When hashes are well distributed and collisions are minimal, get runs close to O(1).

Default capacity and load factor

        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;

    

• Default initial capacity: 16
• Default load factor: 0.75

Resize threshold = capacity × load factor.

So when size exceeds 16 × 0.75 = 12, a resize is triggered.

Why 0.75 for the load factor?

It is an empirical value balancing time and space:

• Too low (e.g., 0.5): fewer collisions but more wasted array space
• Too high (e.g., 1.0): better space usage but more collisions and slower performance
  0.75 strikes a reasonable balance between the two.

How does resizing work?

When size > threshold, resize() is triggered.

Core resize logic:

        // new capacity is double the old
int newCap = oldCap << 1;
int newThr = oldThr << 1;

    

After resizing, every existing node must be redistributed to new bucket positions (rehash).

JDK 8 optimized the rehash process:

        // A node's new position can only be one of two:
// 1. Same as before
// 2. Old index + old capacity
if ((e.hash & oldCap) == 0) {
    // goes to the low-index list (same index)
} else {
    // goes to the high-index list (old index + oldCap)
}

    

This optimization leverages the power-of-two capacity: checking a single bit in the hash value is enough to determine the new bucket — no need to fully recompute the hash mapping.

How is a null key handled?

HashMap allows null as a key, and it is always placed in bucket index 0:

        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);

    

When the key is null, hash returns 0, and the bucket index resolves to 0.

Thread safety

HashMap is not thread-safe.

Under concurrent put calls, you may encounter:

• Data overwrites (two threads writing the same bucket simultaneously)
• Infinite loop caused by circular linked lists in JDK 7 (fixed in JDK 8)

Thread-safe alternatives:

• Collections.synchronizedMap(map): wraps all operations in synchronized, simple but low throughput
• ConcurrentHashMap: JDK 8 uses CAS + synchronized at the bucket level, offering much better concurrency

In production, prefer ConcurrentHashMap for concurrent scenarios.