Collections II: How HashMap Really Works

You've used HashMap since the collections tour: put a key in, get a value out, about O(1). That about is doing a lot of work. A HashMap's speed isn't a promise of the Map interface — it's the emergent result of five internal decisions: the bucket array, the way it perturbs your hashCode, what happens when two keys collide, when the table resizes, and the load factor that governs it all.

You can drive a HashMap for years without knowing any of this. But the day one sits on a hot path — a session cache, a dedup index, a request router — the internals become your debugging vocabulary. This post builds that vocabulary, leaning on the equality-and-hashing rules from the earlier post on equals and hashCode, and on the Map tour from the collections post.

1. A HashMap is an array of buckets

Forget "hash table" as a black box. A HashMap is an array — internally a Node<K,V>[] table — where each slot is a bucket holding either nothing or the head of a short chain of entries. To find a key, HashMap does not scan; it computes an index straight into that array:

index = (n - 1) & hash        // n = current table capacity

Two details carry the whole design:

• Capacity is always a power of two (default 16). That's what makes & work as a fast modulo: (n - 1) & hash is equivalent to hash % n only when n is a power of two. The constructor rounds whatever you pass up to the next power of two.
• Lookup walks, then compares. get jumps to the bucket and walks its chain, comparing each node's stored hash first and calling equals only on hash matches. put does the same walk: if the key already exists (hash match and equals), it replaces the value and returns the old one; otherwise it appends a new node.

Two API facts worth knowing now: a HashMap allows exactly one null key (it hashes to 0 and lives in bucket 0) and any number of null values — so a null from get() is ambiguous, and containsKey() is how you disambiguate. And the decision rule for the whole post: HashMap is the tool for lookup by key. If you need ordering, sorted keys, or thread safety, you're holding the wrong tool — LinkedHashMap, TreeMap, and (in the concurrency track) ConcurrentHashMap are the answers to those different questions.

2. Why HashMap perturbs your hashCode

Look at the index formula again: the mask (n - 1) keeps only the low bits of the hash. With the default capacity of 16, only the lowest 4 bits decide the bucket. So a hashCode whose entropy lives entirely in the high bits is a disaster: every key lands in bucket 0.

That's not hypothetical. This is a real mistake beginners write:

class SessionKey {
    final int id;
    // ...
    @Override public int hashCode() { return id << 16; }  // entropy only in high bits!
}

HashMap defends itself against this with one line of bit-twiddling applied to every key's hash before indexing — it XORs the high 16 bits down into the low 16:

static int spread(int h) { return h ^ (h >>> 16); }

Watch what it does to that bad hashCode versus a healthy one:

public class HashSpread {
    static int spread(int h) { return h ^ (h >>> 16); }

    public static void main(String[] args) {
        int badHash = 5 << 16;   // high-bits-only hashCode, like SessionKey above
        int n = 16;              // default table capacity
        System.out.println("Raw index     : " + ((n - 1) & badHash));
        System.out.println("Spread index  : " + ((n - 1) & spread(badHash)));

        int goodHash = "session-42".hashCode();
        System.out.println("Good raw      : " + ((n - 1) & goodHash));
        System.out.println("Good spread   : " + ((n - 1) & spread(goodHash)));
    }
}

Raw index     : 0
Spread index  : 5
Good raw      : 5
Good spread   : 8

Without spreading, every SessionKey piles into bucket 0 no matter how many distinct ids you have. With spreading, the high bits get folded down and the keys distribute. Notice the healthy String hash barely moves — spreading protects you from mediocre hash functions, not from terrible ones.

The decision rule: write hashCode implementations that use all 32 bits of your fields (the field-mixing recipe from the equality post), and don't "help" by pre-masking or shifting bits yourself. Spreading is a safety net under your hash function, not a substitute for it.

3. When keys collide: chains, then trees

Two different keys can still land in the same bucket — either they genuinely share a hash, or the low bits coincide after masking. HashMap handles this by chaining: each bucket holds a linked list of nodes, and lookup walks the list. Since Java 8, chains that grow long are converted into red-black trees:

• The documented default kicks in at 8 entries in one bin — but only once the table itself has at least 64 buckets. Smaller tables resize first instead of treeifying.
• If deletions shrink a tree bin below 6 entries, it converts back to a plain list.
• Worst case per lookup drops from O(n) to O(log n) — this closed the old hash-collision denial-of-service hole where an attacker could force O(n) lookups with crafted keys.

Here's the whole picture in one diagram:

Treeification is a safety net, not a strategy. A treeified bin still costs tree traversals and pointer chasing where a healthy map costs a single array hop — you never want to rely on it. Keep the three collision outcomes straight, because they answer different debugging questions:

• Same hash + equals true → same key; put replaces the value.
• Same hash (or same bucket) + equals false → a genuine collision; chain or tree walk.
• Different hashes → different buckets, the O(1) fast path.

4. Growing up: resize and the 0.75 load factor

A HashMap doesn't stay at capacity 16. It tracks a threshold — capacity × load factor — and when the entry count passes it, the table doubles and every entry is re-placed. The defaults are a load factor of 0.75 with the initial capacity of 16, so the first resize fires at 12 entries.

Resize is cheaper than it sounds: hashes are not recomputed. Each node is tested against a single bit — (hash & oldCapacity) == 0 — and either stays at its index or moves to index + oldCapacity. One bit decides which half of the doubled table it belongs to. It's still an O(n) re-placement, but it's a one-time cost, amortized across all the O(1) operations that follow. On latency-sensitive paths, though, that one-time cost can show up as a visible hiccup — which is why section 7 matters.

The load factor is a space–time tradeoff, and the default encodes the JDK's chosen balance:

• Too low (say 0.1): the table stays sparse — lookups are fast, but you burn memory and resize constantly as it grows.
• Too high (say 0.95): the table packs tight — memory-efficient, but buckets fill up, chains lengthen, and lookups slow down.
• 0.75 sits between them. Override it via new HashMap<>(capacity, loadFactor) only with measurements in hand, not vibes.

5. Iteration order is unspecified — plan for it

The diagram's second caption is a warning: iteration follows bucket order, which depends on hashes and resize history — not insertion order. This prints in a different order than you inserted:

Map<String, Integer> plain = new HashMap<>();
plain.put("november", 1); plain.put("foxtrot", 2); plain.put("kilo", 3);
System.out.println("HashMap:       " + plain.keySet());

Map<String, Integer> ordered = new LinkedHashMap<>();
ordered.put("november", 1); ordered.put("foxtrot", 2); ordered.put("kilo", 3);
System.out.println("LinkedHashMap: " + ordered.keySet());

HashMap:       [november, kilo, foxtrot]
LinkedHashMap: [november, foxtrot, kilo]

The decision rule is blunt: never let program logic or tests depend on HashMap iteration order. When order is part of the contract, reach for LinkedHashMap, which threads a linked list through the entries to preserve insertion order — or access order, via the new LinkedHashMap<>(16, 0.75f, true) constructor, which is the classic building block for an LRU cache (override removeEldestEntry and the eldest entry evicts itself).

6. The constant-hashCode catastrophe

Now the failure mode that ties everything together. What happens if a key's hashCode returns the same value for every instance?

final class BadKey {
    final int id;
    BadKey(int id) { this.id = id; }
    @Override public int hashCode() { return 42; }  // EVERY key lands in one bucket
    @Override public boolean equals(Object o) {
        return o instanceof BadKey b && b.id == id;
    }
}

equals is correct, so the map still works — every key is distinct. But all 50,000 entries below land in a single bucket, which treeifies. Every lookup walks a red-black tree instead of hopping to its bucket:

import java.util.HashMap;

var bad = new HashMap<BadKey, String>();
for (int i = 0; i < 50_000; i++) bad.put(new BadKey(i), "v" + i);
long t0 = System.nanoTime();
for (int i = 0; i < 50_000; i++) bad.get(new BadKey(i));
System.out.println("BadKey  50k gets: " + (System.nanoTime() - t0) / 1_000_000 + " ms");

var good = new HashMap<Integer, String>();
for (int i = 0; i < 50_000; i++) good.put(i, "v" + i);
t0 = System.nanoTime();
for (int i = 0; i < 50_000; i++) good.get(new BadKey(i));
System.out.println("Integer 50k gets: " + (System.nanoTime() - t0) / 1_000_000 + " ms");

Run it and time it yourself: the BadKey version is dramatically slower, and the gap widens as the map grows, because each lookup pays O(log n) tree comparisons plus pointer chasing instead of a single bucket hop. Treeification saved this from being O(n) per lookup — the pre-Java-8 outcome — but "not O(n)" is cold comfort when you expected O(1).

A constant hashCode is the extreme, but the disease has milder forms: hashing only one field of a composite key, or deriving the hash from a low-cardinality field like a status enum. The debugging rule: if a profiler shows HashMap.get/put hot on a large map, audit your key's hashCode distribution before blaming the JDK.

7. Size the map up front on hot paths

Each resize is a one-time O(n) re-placement. If you know roughly how many entries a map will hold — a bulk load, a per-request cache, a parser's symbol table — pay that cost zero times by sizing the map once:

int expected = 100_000;
// The map resizes when size exceeds capacity * 0.75, so make room up front:
int capacity = (int) (expected / 0.75f) + 1;
var cache = new HashMap<String, Session>(capacity);

Two things to notice. First, passing expected itself (100,000) would not avoid a resize, because the threshold would be 75,000 — you must divide by the load factor. Second, the constructor rounds up to a power of two, so 133,334 becomes a 262,144-bucket table: no resize until 196,608 entries. That's the tradeoff made explicit — you spend memory once to buy predictable latency.

When does this matter? Hot paths and known-size bulk loads. When doesn't it? Small maps, unknown sizes, one-off utilities — the defaults (16, 0.75) are the right call until measurements say otherwise.

Field check

Five rules to carry into the next post:

1. Broken equals/hashCode contract → silently lost entries. The map can't find what it can't hash consistently.
2. Poor hash distribution → one giant bin. Your O(1) map becomes a tree crawl; treeification limits the damage but never restores the fast path.
3. Iteration order is unspecified. Depending on it gives you flaky tests; LinkedHashMap is the tool when order is contractual.
4. Growing a big map entry-by-entry on a hot path → repeated resizes. Pre-size with (int)(expected / 0.75f) + 1 when you know the size.
5. One HashMap shared across threads → corruption. Nothing in this post made it thread-safe. The concurrency track will show you ConcurrentHashMap — and why its internals look the way they do will make much more sense after this post.

Continue: Java Learning Roadmap 2026