How HashMap Works Internally in Java

"How does HashMap work internally?" is the most reliably asked deep-dive question in Java interviews — from 2-year service-company rounds to senior product-company loops. It is popular because one question tests four things at once: data structures, the hashCode/equals contract, bit manipulation, and whether you actually read how your tools work.

This article walks the full path of a put() and a get() through the JDK's implementation: hash computation, bucket indexing, collision chains, treeification, and resizing. Every threshold quoted here (8, 6, 64, 0.75) comes straight from the OpenJDK HashMap source.

The big picture: an array of buckets

Internally, a HashMap is a plain array called table, whose elements are the heads of buckets:

transient Node<K,V>[] table;   // from the JDK source

Each Node holds four fields: the cached hash, the key, the value, and a next pointer to the following node in the same bucket:

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
    // constructor, getters, setters...
}

So the structure is: array → linked list (or tree) per slot. Everything else — hashing, resizing, treeification — exists to keep those per-slot chains as short as possible, because chain length is what decides whether get() is O(1) or something worse.

The array starts at a default capacity of 16 and its length is always a power of two. Both facts matter, as you will see in the indexing step.

Step 1: computing the hash

When you call put(key, value), HashMap does not use key.hashCode() directly. It first spreads the hash:

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

Two things to notice. First, a null key hashes to 0, which is why HashMap can store exactly one null key — it always lives in bucket 0. Second, the XOR folds the high 16 bits of the hash code into the low 16 bits.

Why bother? Because of how the bucket index is computed next: only the low bits of the hash participate when the table is small. Hash codes that differ only in their high bits — common for Float keys or objects laid out in memory sequences — would otherwise collide constantly. One XOR and one shift is the cheapest possible defense.

Step 2: finding the bucket

The bucket index is not hash % capacity. It is:

index = (n - 1) & hash;   // n = table.length, always a power of two

When n is a power of two, n - 1 is a string of 1-bits (16 → 1111), so the AND keeps exactly the low bits of the hash — mathematically identical to hash % n for non-negative values, but a single CPU instruction with no division and no negative-number edge case.

This is the real answer to "why is capacity always a power of two?" — the indexing trick and the cheap resize (Step 5) both depend on it.

Step 3: handling collisions

Two different keys can map to the same bucket — either because their hash codes are equal or because their different hash codes share the same low bits. That is a collision, and it is normal: with 16 buckets and 13 entries, collisions are guaranteed by the pigeonhole principle.

On a collision, putVal() walks the existing chain and applies this logic for each node:

1. If node.hash == hash and the keys are equal by == or equals() → same key, replace the value.
2. Otherwise move to node.next.
3. Reached the end without a match → append a new node to the chain.

And get(key) mirrors it: compute hash → find bucket → walk the chain comparing hash first (cheap int comparison) and equals() second (potentially expensive) → return the value or null.

Here is a runnable demonstration that forces collisions and proves the map still works — because equals() disambiguates within a bucket:

import java.util.HashMap;
import java.util.Map;

public class CollisionDemo {
    static final class BadKey {
        final String name;
        BadKey(String name) { this.name = name; }

        @Override public int hashCode() { return 42; }  // every key collides!

        @Override public boolean equals(Object o) {
            return o instanceof BadKey other && name.equals(other.name);
        }
    }

    public static void main(String[] args) {
        Map<BadKey, Integer> map = new HashMap<>();
        for (int i = 0; i < 1000; i++) {
            map.put(new BadKey("key" + i), i);
        }
        // All 1000 entries share one bucket, yet lookups stay correct:
        System.out.println(map.get(new BadKey("key777"))); // 777
        System.out.println(map.size());                    // 1000
    }
}

Correct, yes — but every lookup in that bucket must compare against its neighbors. Before Java 8 this meant O(n) scans. Which brings us to the most important modern change.

Step 4: treeification — the Java 8 upgrade

Since Java 8, when a single bucket's linked list grows beyond TREEIFY_THRESHOLD = 8 nodes, HashMap converts that bucket's chain into a Red-Black tree (TreeNode instead of Node). Lookups in that bucket drop from O(n) to O(log n).

The full set of constants:

Three subtleties interviewers use as follow-ups:

Why 8? With a decent hash function, chain lengths follow a Poisson distribution; the JDK source comments note that under the default load factor a chain of length 8 occurs with probability of about 0.00000006. Reaching 8 nodes practically never happens by chance — so a chain that long signals a bad hashCode() (or a hash-flooding attack), and the tree acts as a safety net rather than a common path.

Why is the untreeify threshold 6, not 8? Hysteresis. If both thresholds were 8, a map oscillating between 7 and 9 entries in a bucket would repeatedly convert list→tree→list, each conversion costing time. The gap of 2 prevents that thrashing.

Why does MIN_TREEIFY_CAPACITY exist? In a table with fewer than 64 buckets, long chains usually mean the table is simply too small — many keys are being squeezed into few slots. Doubling the table spreads them out for free. Treeifying is reserved for when collisions persist even in a reasonably sized table.

In the BadKey example above, the single bucket holding 1,000 entries is a Red-Black tree, so get() performs roughly 10 comparisons instead of up to 1,000. The keys must ideally implement Comparable for efficient tree ordering; otherwise HashMap falls back to class-name comparison and System.identityHashCode() as tie-breakers.

Interview note: "What changed in HashMap in Java 8?" has three correct answers, and strong candidates give all of them: (1) treeification of long chains, (2) the simplified h ^ (h >>> 16) hash spreading, and (3) resize now preserves node order within a bucket — Java 7 reversed the list on transfer, which under illegal concurrent use could create an infinite loop; Java 8's order-preserving split removed that particular failure mode (the map is still not thread-safe).

Step 5: resizing and the 0.75 load factor

HashMap doubles its table when:

size > capacity × loadFactor      // default: 16 × 0.75 = 12

The load factor 0.75 is a space-time compromise. Lower values waste memory on empty slots; higher values lengthen chains. At 0.75, most buckets hold zero or one node, keeping the O(1) average honest while the table stays mostly utilized.

Resizing allocates a table of double the size and redistributes every entry — an O(n) operation. Here the power-of-two capacity pays off a second time. When capacity goes from 16 to 32, the index mask grows from 1111 to 11111: exactly one new bit of the hash becomes relevant. So each node either:

• stays at its old index (new bit is 0), or
• moves to old index + oldCapacity (new bit is 1).

Java 8 splits each bucket into a "low" and "high" list in one pass using (hash & oldCap) == 0 — no re-hashing, no modulo, order preserved.

import java.util.HashMap;
import java.util.Map;

public class ResizeCost {
    public static void main(String[] args) {
        int entries = 1_000_000;

        long t1 = System.nanoTime();
        Map<Integer, Integer> resizing = new HashMap<>();       // 16 buckets
        for (int i = 0; i < entries; i++) resizing.put(i, i);
        long grew = System.nanoTime() - t1;

        long t2 = System.nanoTime();
        Map<Integer, Integer> presized = new HashMap<>(1 << 21); // 2,097,152
        for (int i = 0; i < entries; i++) presized.put(i, i);
        long fixed = System.nanoTime() - t2;

        System.out.println("With ~17 resizes: " + grew / 1_000_000 + " ms");
        System.out.println("Pre-sized:        " + fixed / 1_000_000 + " ms");
    }
}

Run it a few times: the pre-sized map is consistently faster because the growing map re-buckets its entries on every doubling from 16 up past 1 million. This is why pre-sizing is the one HashMap tuning that matters in practice, as covered in HashMap best practices.

Pro tip: To hold n entries without resizing, the capacity must exceed n / 0.75. For one million entries that is ~1,333,334, so the next power of two is 2²¹ = 2,097,152. Java 19+ does this arithmetic for you with HashMap.newHashMap(n).

The hashCode/equals contract — where it all connects

Everything above assumes keys behave. The contract:

1. Equal objects (per equals()) must return the same hashCode().
2. Unequal objects may share a hash code (that is just a collision).
3. hashCode() must be consistent — same value across calls while the object is unchanged.

Break rule 1 and equal keys hash to different buckets, so get() looks in the wrong place:

import java.util.HashMap;
import java.util.Map;

public class BrokenContract {
    static final class UserId {
        final int id;
        UserId(int id) { this.id = id; }

        @Override public boolean equals(Object o) {
            return o instanceof UserId u && u.id == id;
        }
        // BUG: hashCode() not overridden -> defaults to identity hash
    }

    public static void main(String[] args) {
        Map<UserId, String> names = new HashMap<>();
        names.put(new UserId(7), "Anil");

        System.out.println(names.get(new UserId(7)));       // null!
        System.out.println(names.containsKey(new UserId(7))); // false!
        System.out.println(names.size());                    // 1 - it IS there
    }
}

The entry exists, but it is unreachable through an equal key — the most common cause of "HashMap is losing my data" bug reports. The same failure happens if you mutate a key after insertion so that its hash changes: the node sits in the bucket chosen by the old hash, while lookups probe the bucket for the new one.

This is also why String is such a good key: it is immutable and caches its hash code after the first computation, so repeated lookups don't even re-hash. The String immutability guide covers that design in depth.

Common mistake: A common mistake beginners make is overriding equals() for business logic and forgetting hashCode() — the compiler does not force the pair. Use records, Lombok's @EqualsAndHashCode, or your IDE's generator so the two can never drift apart.

Walking through put() end to end

Tie it together with the exact sequence for map.put("dosa", 65) on a default-sized map:

1. Compute "dosa".hashCode(), spread it: h ^ (h >>> 16).
2. Index: (16 - 1) & hash → a bucket from 0 to 15.
3. Bucket empty → place a new Node there. Done.
4. Bucket occupied → walk the chain (or search the tree): if a node has the same hash and an equal key, replace its value and return the old one.
5. No match → append the node; if the chain now exceeds 8 and the table has ≥ 64 buckets, treeify the bucket.
6. Increment size; if size > capacity × 0.75, double the table and redistribute using the one-bit split.

get() is steps 1, 2 and the chain/tree search — nothing else. If you can narrate those six steps and justify each threshold, you can handle any variation of this question in a Java collections interview.

What this means in practice

• Trust the O(1) average, but earn it — with immutable keys and honest hashCode() implementations.
• Pre-size known-large maps; resizing is the only routinely avoidable cost.
• Treat treeification as a safety net, not a feature — if your buckets are treeifying, your hash function is the problem.
• Remember the boundaries of the design: none of this machinery is thread-safe. Concurrent writes need ConcurrentHashMap, and the historical alternative Hashtable is compared in HashMap vs Hashtable.

The bucket-array-plus-chain model also explains HashSet (a HashMap with dummy values), LinkedHashMap (the same table plus a linked list through entries), and half of the Map interface family. Learn the internals once, and four other classes come free.