August 12, 2026

How Java's HashMap actually works internally

javacollectionsjvm

HashMap is probably the single most-used data structure in any Java codebase, and also one of the least understood. Most developers know it's "fast" and that keys need hashCode() and equals(), and stop there. That's usually enough — until a HashMap with a badly-written key class starts behaving like a linked list, or someone asks in an interview what actually happens inside put(). Here's the internal mechanics, working from the ground up.

The mental model: an array of buckets

Underneath the API, a HashMap is a plain array — Node<K,V>[] table — where each slot is called a bucket. Every key gets mapped to exactly one bucket index, and everything that lands in the same bucket is chained together.

table[0] -> (empty)
table[1] -> ["alice" -> 30] -> ["frank" -> 41]   (two keys, same bucket)
table[2] -> (empty)
table[3] -> ["bob" -> 25]
...

The chain at each bucket used to always be a linked list. As of Java 8, it can also be a red-black tree — more on that shortly. Either way, the core idea is the same: the array gives you near-instant access to roughly the right spot, and whatever's chained at that spot handles the rare case where two different keys land in the same place.

From hashCode() to a bucket index

Turning a key into an array index happens in two steps.

Step one: spread the hash. HashMap doesn't use key.hashCode() directly — it runs it through a spreading function first:

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

This XORs the top 16 bits of the hash code into the bottom 16 bits. The reason is the next step: the table size is almost always much smaller than the full range of an int, so only the low bits of the hash actually end up mattering for the index. If a key's hashCode() implementation puts most of its "randomness" in the high bits — which happens more often than you'd expect — those bits would otherwise never influence the bucket at all, and unrelated keys would pile into the same buckets far more than they should. Folding the high bits down fixes that cheaply.

Step two: mask it to the table size. The bucket index is:

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

HashMap's capacity is always a power of two, which makes (n - 1) & hash mathematically identical to hash % n — but a bitwise AND is much cheaper than a modulo, and it's the reason capacities get silently rounded up to the next power of two even if you pass something else to the constructor.

What put() actually does

Putting the two steps together, here's the sequence for map.put(key, value):

Compute the spread hash for the key.
Mask it to get the bucket index.
If that bucket is empty, insert a new node there and stop.
If it's not empty, walk the chain. For each existing node, compare hash first (cheap), and only call .equals() if the hashes match (more expensive, and the real correctness check).
If a node with an equal key is found, its value is replaced and the old value is returned.
If the chain is walked to the end with no match, a new node is appended.
If appending pushed this particular bucket's chain to 8 or more nodes (and the table is large enough — more on that below), the bucket converts from a linked list to a tree.
If the total size now exceeds capacity × loadFactor, the whole table resizes.

get(key) does exactly steps 1, 2, and 4 — compute the bucket, walk it, compare hash then equals — and returns the matching value or null.

Why hashCode() and equals() have to agree

This is where most real-world HashMap bugs come from. Both hashCode() and equals() are used together during lookup, and if they're inconsistent, lookups silently fail instead of throwing anything.

public class UserId {
    private final String value;

    public UserId(String value) {
        this.value = value;
    }
    // no equals() or hashCode() override
}

Map<UserId, String> names = new HashMap<>();
names.put(new UserId("u-42"), "Priya");

names.get(new UserId("u-42")); // null — not what you'd expect

This returns null because UserId falls back to Object's default hashCode() and equals(), which compare identity — two separate new UserId("u-42") instances are never equal to each other, even though they wrap the same value. The fix is to override both, consistently:

public class UserId {
    private final String value;

    public UserId(String value) {
        this.value = value;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof UserId)) return false;
        return value.equals(((UserId) o).value);
    }

    @Override
    public int hashCode() {
        return value.hashCode();
    }
}

The rule that matters: if two objects are .equals(), they must return the same hashCode(). The reverse isn't required — different objects are allowed to share a hash code, that's just a collision, and the chain (or tree) at that bucket handles it correctly via equals(). But break the first rule, and HashMap will happily store two "duplicate" entries it thinks are different, or fail to find a key that's clearly already there.

Resizing: doubling without a full rehash

The default load factor is 0.75, meaning once the map's size passes 75% of its capacity, the table doubles in size. Naively, doubling the table would mean recomputing every single key's bucket index from scratch. Java 8 avoids that with a neat trick that follows directly from capacities always being powers of two.

When capacity doubles, the mask (n - 1) gains exactly one more bit. That means every existing node either stays in its current bucket index, or moves to index + oldCapacity — nothing else is possible, because only one new bit of the hash can now matter. So instead of rehashing, resize() just checks that one extra bit for each node and splits every old bucket's chain into two: a "lo" list that stays put, and a "hi" list that moves to index + oldCapacity. Both are appended in one pass, in their original relative order, without ever calling hash() or equals() again.

Treeification: capping the worst case

A linked-list bucket is O(1) on average but degrades to O(n) if too many keys collide into the same bucket — which is exactly what happens if someone crafts keys deliberately, or if a hash function just happens to be weak. Before Java 8, this was a real denial-of-service vector: enough colliding keys and a HashMap could be driven to behave like a single giant linked list.

Java 8 fixes this with treeification. Once a single bucket's chain reaches TREEIFY_THRESHOLD (8) nodes, and the table itself has at least MIN_TREEIFY_CAPACITY (64) buckets, that bucket converts from a linked list into a small red-black tree, ordered by hash. Lookups in a treeified bucket become O(log n) instead of O(n) in the worst case. If the table is still small (under 64 buckets), HashMap resizes instead of treeifying — an 8-node bucket in a tiny table is a sign the table itself is too small, not necessarily a hash collision problem. If enough entries are later removed and a treeified bucket shrinks back down to UNTREEIFY_THRESHOLD (6) nodes, it converts back to a plain list — the two thresholds are kept a couple of nodes apart on purpose, so a bucket hovering right at 7 or 8 entries doesn't flip back and forth between representations on every insert and remove.

In practice, treeification almost never triggers on well-behaved keys with a decent hashCode() — it exists as a safety net for the pathological case, not something you'll typically see on a debugger's watch window.

What's actually changed in recent JDK versions

Everything described above — the spread function, power-of-two capacities, lo/hi resize splitting, treeification — is the Java 8 HashMap, and it's worth being direct about this: Java 8 was the rewrite. Before it, HashMap was a much simpler array-of-linked-lists with no treeification and a weaker hash spread, which is exactly what made the collision-based DoS attacks of the early 2010s possible against naive Java web services.

Since Java 8, the algorithm itself has stayed remarkably stable through 11, 17, and 21:

Java 8 also added the Map default methods that changed how HashMap gets used day to day even though they don't touch its internals: computeIfAbsent, computeIfPresent, merge, getOrDefault, putIfAbsent, forEach. These matter more than they look — computeIfAbsent in particular collapses what used to be a manual "check, then insert" pattern (two lookups, and a subtle race if you weren't careful) into a single bucket traversal:
```
// before: two lookups, easy to get wrong under concurrent use
List<String> list = map.get(key);
if (list == null) {
    list = new ArrayList<>();
    map.put(key, list);
}
list.add(value);

// after: one traversal, same result
map.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
```
Java 9 introduced Map.of(...) and Map.ofEntries(...) for small immutable maps. It's easy to assume these are just a convenience wrapper around HashMap, but they're not — they're backed by a completely separate, more compact implementation (ImmutableCollections) with no resizing, no treeification, and no mutation support at all. Worth reaching for when you genuinely don't need a mutable map; not a replacement for HashMap when you do.
Java 11 through 21 haven't changed the HashMap algorithm at all. The improvements you get from running on a newer JDK come from the JVM around it — better JIT inlining, improved garbage collectors (G1's default tuning has improved considerably, and ZGC has matured a lot) — rather than from a different HashMap data structure. If you understand the Java 8 design described above, that understanding is still accurate on the JDK you're running today.

A few practical takeaways

Always override hashCode() and equals() together, never one without the other. Records get this for free — one more reason to prefer them for simple key types.
Set an initial capacity if you know roughly how many entries you'll store. new HashMap<>(expectedSize) avoids repeated resizing while the map fills up, which matters more than it sounds like on large maps built in a hot path.
Don't rely on iteration order. HashMap makes no guarantees about it, and it can visibly change across a resize. Reach for LinkedHashMap if you need insertion order, or TreeMap if you need sorted order.
Avoid mutable objects as keys. If a key's hash code can change after it's inserted, the entry effectively becomes unfindable — it's still sitting in its original bucket, but a fresh lookup will compute a different bucket index for the now-changed key.

None of this changes how you write map.get(key) day to day. But the next time a HashMap behaves strangely — a key that "should" be there isn't, or a hot path is slower than it should be — this is usually where the answer is hiding.