Java HashMap Internals: Buckets, Collisions, Treeification, and Resizing

“How does HashMap work?” is probably the single most-asked Java interview question — and for once, the interview obsession is justified. HashMap’s internals explain why equals/hashCode have a contract, why mutating keys corrupts maps, what load factor means, and why Java 8 quietly put red-black trees inside a hash table.

This guide walks the whole path of a put and a get, then covers the failure modes that show up in production.

The Core Idea: Trade Memory for Address Math

A list answers contains by checking every element. A hash map skips the search entirely: it computes where a key must live.

put("cat", 1):
  "cat".hashCode()  ─▶  98262   ─spread─▶  index = hash & (capacity-1)  ─▶  bucket 6

table (capacity 16):
  [0] [1] [2] [3] [4] [5] [6]────▶ ("cat" → 1)
                          [7] ... [15]

Storage is a plain array of buckets (default capacity 16). The key’s hashCode() — any int, positive or negative — is squeezed into a valid index. Because capacity is always a power of two, hash & (capacity - 1) does the job with a single AND instruction instead of a modulo.

A get("cat") recomputes the same index, jumps straight to bucket 6, and confirms the key with equals. No scanning — that’s the O(1).

One refinement worth knowing because interviewers love it: before indexing, HashMap spreads the hash — h ^ (h >>> 16) — XOR-ing the high 16 bits into the low 16. Since indexing only uses the low bits, hashCodes that differ only in high bits (common for e.g. sequential values) would otherwise collide constantly. This one line of bit-twiddling is why mediocre hashCodes still perform tolerably.

Collisions: When Two Keys Want One Bucket

Different keys can produce the same index — different hashCodes squeezed to the same slot, or genuinely equal hashCodes (perfectly legal: the contract says equal objects → equal hashes, not unequal objects → unequal hashes; with ~4 billion ints and unlimited possible keys, collisions are mathematically unavoidable).

HashMap’s answer: each bucket holds a linked list of entries (each storing hash, key, value, next):

  [6] ──▶ ("cat" → 1) ──▶ ("act" → 9) ──▶ null

Both put and get walk the chain, comparing hashes first (cheap int compare) and then equals (potentially expensive) only on hash matches. Short chains keep this effectively O(1).

Java 8’s twist: treeification

Long chains degrade toward O(n) — and before Java 8, attackers exploited exactly this: flood a server with request parameters engineered to share one bucket, and the hash map underlying the parameter parsing becomes a linked list, turning O(n) requests into O(n²) CPU (a real denial-of-service class, hash-flooding).

Since Java 8, when a single bucket’s chain exceeds 8 entries (and the table has at least 64 buckets), the chain converts into a red-black tree, dropping worst-case bucket operations from O(n) to O(log n). It converts back to a list if the bucket shrinks below 6. For this to work well, keys should be Comparable — String and the numeric wrappers are, which covers most real maps.

Practical translation: HashMap’s worst case is now O(log n) even under adversarial keys — but you should still never rely on that; a decent hashCode keeps you on the fast path.

Resizing: Load Factor and the Cost of Growth

More entries → more collisions. HashMap monitors its load factor — entries ÷ capacity — and when it crosses the threshold (default 0.75), the table doubles and every entry is redistributed:

capacity 16, threshold 12 ─▶ 13th entry arrives ─▶ new table of 32, rehash all

Why 0.75? It’s the empirically chosen elbow of the memory/speed curve — beyond it chains lengthen fast; below it you’re buying little speed with a lot of empty slots. You’ll essentially never change it.

What you should change: initial capacity, when you know the size in advance.

// about to insert ~10,000 entries?
Map<String, User> users = new HashMap<>(14_000);   // ≈ 10_000 / 0.75, rounded up

Without this, the map resizes ~10 times on the way to 10k entries, rehashing everything each time. HashMap.newHashMap(10_000) (Java 19+) does the load-factor math for you. This is one of the cheapest micro-optimizations that’s actually worth doing.

A power-of-two detail that makes resizing elegant: doubling capacity adds one bit to the index mask, so every entry either stays at its index or moves to exactly index + oldCapacity — decided by a single bit of its hash. No full rehash computation per key.

The Contract, Now With Consequences

The rules from the records guide — equal objects must share a hashCode; override both or neither — stop being abstract once you’ve seen the machinery:

Broken: equals without hashCode. Two equal keys hash to different buckets. map.get(equalKey) looks in the wrong bucket, returns null, and your “cache” silently stores duplicates under keys it can never find again.

Legal but catastrophic: constant hashCode. hashCode() { return 42; } satisfies the contract and turns your map into one bucket — a linked list (or tree) wearing a HashMap costume. Interviewers ask this as “what happens if hashCode always returns the same value?” — the answer is “it still works, at O(log n) per op after treeification, O(n) before.”

The mutation trap — the one that bites in production:

Set<Point> visited = new HashSet<>();   // HashSet is a HashMap in disguise
Point p = new Point(2, 3);
visited.add(p);          // stored in the bucket for hash(2,3)
p.x = 99;                // hash is now different...
visited.contains(p);     // false — looks in bucket for hash(99,3)
visited.size();          // 1 — the entry still exists, unreachable

The entry is a ghost: present, iterable, but unfindable by lookup, and even remove(p) fails. Nothing throws. This is the argument for immutable keys — records, Strings, and value types. If a key must be mutable, never mutate hash-relevant fields while it’s in a map.

Null, Order, and Other Behavioral Fine Print

• One null key is allowed (stored in bucket 0) and any number of null values. But get returning null is ambiguous — missing key, or present-with-null-value? Prefer getOrDefault / containsKey, and better yet, don’t store null values.
• Iteration order is unspecified and unstable — it can change after a resize. Code that accidentally depends on HashMap order breaks on JVM upgrades; tests that assert on it flake. Need order? LinkedHashMap (insertion) or TreeMap (sorted).
• Not thread-safe. Concurrent writes can lose updates, and in old Java versions concurrent resize could even create infinite loops. Under concurrency use ConcurrentHashMap — lock-striped, no global lock, and its compute/merge are atomic. (More in the concurrency guide.)
• HashSet is literally a HashMap whose values are a shared dummy object — every fact above applies to sets verbatim.

Walking put() End to End

Interview-ready mental replay of map.put("cat", 9) on a map already containing "cat" → 1:

1. Compute h = spread("cat".hashCode()).
2. Index: i = h & (table.length - 1).
3. Bucket empty? → new entry, done. Else walk the chain/tree:
4. For each node: if node.hash == h && node.key.equals("cat") → replace value, return old value 1.
5. No match by chain end → append new node; if chain length now > 8 (and table ≥ 64) → treeify.
6. If ++size > capacity × 0.75 → double and redistribute.

get is steps 1–4 without the writes. If you can narrate this unprompted, you’re ahead of most candidates — and more importantly, every “weird map behavior” you meet now has a mechanical explanation.

Choosing Among the Map Family (Recap With New Eyes)

EnumMap is the underused one: keys that are enums get a flat array indexed by ordinal — no hashing at all.

Writing a Good hashCode (and Recognizing a Bad One)

Since the whole machine turns on hash quality, it’s worth knowing what “good” means: equal objects equal hashes (the contract), unequal objects usually unequal hashes (the quality bar), and all bits of the input influencing the output (the spread).

In practice you almost never hand-roll it:

// records: generated correctly, done
public record RouteKey(String origin, String destination, LocalDate date) {}

// regular classes: Objects.hash covers nearly every case
@Override public int hashCode() {
    return Objects.hash(origin, destination, date);
}

Objects.hash uses the classic 31-multiplier polynomial internally — the same scheme String.hashCode has used for decades (31 being an odd prime whose multiply optimizes to shift-and-subtract). Its one cost is varargs boxing; only hot-path types with millions of lookups justify hand-writing the polynomial to avoid it.

Bad hashCodes to recognize in review: hashing only one field of a multi-field key (“all routes from Delhi collide”), hashing a mutable field (the ghost-entry trap above), and XOR-ing fields symmetrically (a.hashCode() ^ b.hashCode() makes (x, y) collide with (y, x) — a real problem for pair-like keys; the 31-polynomial’s asymmetry exists precisely to avoid this).

Frequently Asked Questions

Does HashMap shrink when entries are removed? No — capacity only grows. A map that once held a million entries keeps its giant table after clear(). In the rare case that matters (a long-lived map with a one-time bulk phase), replace it with a fresh new HashMap<>(map) sized to current contents.

Why is iteration order different between runs or JVMs? Order is a function of capacity and each key’s spread hash — both implementation details. String hashes are stable across JVMs, but default Object.hashCode (identity-based) is not, and any resize reshuffles everything. Treat the order as random; if a test asserts on it, the test is wrong.

How does ConcurrentHashMap differ internally? Same bucket-array-plus-treeified-bins design, but writes use fine-grained per-bin synchronization (CAS for empty bins, a tiny lock for occupied ones) and reads are entirely lock-free. That’s why it scales where Collections.synchronizedMap — one global lock — does not. Full context in the concurrency guide.

Is WeakHashMap related? Structurally similar, but keys are held by weak references: once a key is otherwise unreachable, the entry evaporates at the GC’s convenience. It’s the canonical fix for the listener-registry and metadata-cache memory leaks — association without ownership.

Self-Check

1. Why must HashMap’s capacity be a power of two?
2. A key class’s hashCode returns 1 for every instance. Is the equals/hashCode contract violated? What’s the performance consequence?
3. After map.put(key, v), someone mutates a field of key used in its hashCode. Describe exactly what map.get(key) does now, step by step.
4. You’re about to bulk-load 1M entries into a fresh HashMap. What one constructor argument saves roughly 20 rehash-everything passes, and what value should it be?
5. Why did Java 8 add trees to buckets rather than just recommending better hashCodes?

(Answers: so hash & (cap-1) replaces modulo and resize moves entries by one bit. No — the contract permits it; all entries share one bucket, O(log n) after treeify. It spreads the new hash, indexes to a different bucket, finds no entry there, returns null — while the stale entry sits in the old bucket. Initial capacity ≈ 1_000_000/0.75 ≈ 1.34M. Because key quality is in users’ hands and adversaries exploit collisions deliberately — the JDK needed a worst-case guarantee it controls.)

Next: the feature that changed how Java code reads more than any other — Streams and Lambdas, where collections stop being loops and start being pipelines.