HashMap: The Default Map and What the Table Actually Does

You need "ORD-1001" → that Order on the hot path. The Map contract names the job. HashMap is the class you new until order, sorting, identity equality, or another thread says otherwise.

HashMap is an array of bins plus a hash that picks one. Layout theory — what a bucket is, chaining vs open addressing, expected O(1) vs a collapsed hash — lives on Hash Tables. This post is the JDK machine interviewers draw: spreading, (n - 1) & hash, treeify, resize, and the key that moves after insert. Glossary words such as fail-fast and “keys honor equals / hashCode” live on the Collections roadmap. The language contract itself is equals and hashCode.

The default map

The lab is still Order.id as the key:

Map<String, Order> byId = new HashMap<>();
byId.put(order.id(), order);
Order found = byId.get("ORD-1001");

Default capacity is 16, default load factor is 0.75, table allocated on the first put. One null key, null values allowed. Not thread-safe. Iterators are fail-fast. Java 8+ iteration order is repeatable for a given table shape and not a specified encounter order — HashMap is not sequenced. Need insertion order? LinkedHashMap. Need sorted keys? TreeMap, in Navigable Collections.

Pass a capacity hint when you know the size, so you do not resize through 16, 32, 64 on the way to a known thousand:

Map<String, Order> byId = new HashMap<>(1_024);

The hint is rounded up to a power of two. It is not a hard cap. The Map methods this class delivers:

Constructor / method	Job
`new HashMap<>()`	Default: capacity 16, load 0.75, table on first `put`
`new HashMap<>(n)`	Capacity hint (rounded up to a power of two)
`new HashMap<>(n, loadFactor)`	Tune resize; leave `0.75` until a profile says otherwise
`new HashMap<>(other)`	Copy mappings; independent table
`get` / `put` / `remove` / `containsKey`	Expected `O(1)` — hash, then the bin
`containsValue`	`O(n)` scan of values
`keySet` / `values` / `entrySet`	Fail-fast views on this table

Everything else on the Map contract — computeIfAbsent, merge, Map.of — works. This post is what the table does when those methods run.

What to draw: a table of nodes

Interviewers want this picture, not a textbook “hash % n” that Java does not use.

table: Node<K,V>[]          length n = 16, 32, 64, …  (always a power of two)

[0]  -> null
[1]  -> Node(hash, "ORD-1001", orderA, next)
[2]  -> null
[3]  -> Node(ORD-1003) -> Node(ORD-1019) -> Node(ORD-1100)   // collision chain
…
[15] -> null

Node:  final int hash | final K key | V value | Node next

get("ORD-1001") computes a spread hash, indexes the array, then walks that bin. It compares hash first, then == on the key, then equals. Other bins are not visited.

String id = "ORD-1001";
int hc = id.hashCode();
int h = hc ^ (hc >>> 16);                  // HashMap.hash
int i = (table.length - 1) & h;            // bin index
for (Node<String, Order> e = table[i]; e != null; e = e.next) {
    if (e.hash == h && (e.key == id || e.key.equals(id))) {
        return e.value;
    }
}
return null;

That loop is the whole lookup. A fat bin makes it a scan of that bin. A decent hash keeps bins short. Hash Tables already named that bet; here is how this class keeps it.

Why XOR shift: hash ^ (hash >>> 16)

Index is (n - 1) & hash because n is a power of two — a cheap mask instead of %. The mask only looks at the low bits. Keys whose hashCode differs only in the high half would all land in the same bin.

HashMap.hash folds the high 16 bits into the low half:

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

A whiteboard number:

key.hashCode()          = 0xABCD0000
hash >>> 16             = 0x0000ABCD
hash ^ (hash >>> 16)    = 0xABCDABCD

n = 16, n - 1 = 0xF
without spread:  0xABCD0000 & 0xF  = 0     // every such key → bin 0
with spread:     0xABCDABCD & 0xF  = 0xD   // bin 13

The XOR is spreading for a power-of-two table, not encryption and not a second hashCode. You still owe an honest hashCode on the key type. A constant 0 makes every key bin 0 after spreading too.

The null key is special-cased to hash 0, so it lives in bin 0. One of them.

Collisions stay a chain — until they do not

Two different ids can mask to the same index. The bin is a linked list of Nodes. Insert walks the chain: replace if equals, else append. That is chaining, the layout the hash-table post already drew.

Map<String, Integer> qtyBySku = new HashMap<>();
for (LineItem item : order.items()) {
    qtyBySku.merge(item.sku(), item.quantity(), Integer::sum);
}

merge is still “find the bin, find the key, write.” Collisions are normal. A chain of two is not a bug.

Treeify at 8, but only if capacity is at least 64

A hostile or unlucky hash can put eight-plus keys in one bin. Walking that list is O(length of bin). Java 8+ converts a long bin into a red-black tree (TreeNode) so that bin’s worst case is O(log n) instead of O(n).

The constants interviewers want by name:

TREEIFY_THRESHOLD      = 8     // bin length that triggers treeifyBin
UNTREEIFY_THRESHOLD    = 6     // tree small enough to become a list again
MIN_TREEIFY_CAPACITY   = 64    // do not treeify a tiny table — resize first

Decision on insert, when the bin reaches eight nodes:

bin length >= 8
    table.length < 64  →  resize()          // spread first; trees are not free
    table.length >= 64 →  convert that bin to a red-black tree

Eight is necessary, not sufficient. A map of sixteen buckets that stuffed eight colliding keys resizes rather than treeifies. Trees cost more than a list of seven, and a small table is often just undersized. After the table has grown to 64 or more, a still-fat bin is allowed to become a tree.

Hysteresis is the pair 8 / 6. If both thresholds were 8, a bin would flip list → tree → list on a single remove/insert. Untreeify at 6 (on split or remove) stops the chatter.

When hashes in a tree bin are equal, TreeNode uses compareTo if the key is Comparable (a String id is), otherwise a class-name / identity tie-break. That is how the tree stays ordered when spreading could not. It does not make get O(1) for a broken hashCode. It makes the hostile bin O(log n).

Typical bins never treeify. Do not design as if they will. Do not skip hashCode because “Java will tree it.”

Resize doubles, then rebins

Load factor default 0.75. When size would pass capacity * 0.75, the table grows. Capacity doubles. Every live node is placed into the new array.

Because n is a power of two, Java 8+ does not recompute hash % newN from scratch. It tests one extra bit: hash & oldCap.

old n = 16, new n = 32
old index i = (16 - 1) & hash

hash & 16 == 0  →  stay at i
hash & 16 != 0  →  move to i + 16

A four-bucket sketch:

old (n = 4)                    new (n = 8)
[0] A (hash & 4 == 0)          [0] A
[1] B → C                      [1] B          // C had hash & 4 != 0
[2]                            [2]
[3] D                          [3] D
                               [4]
                               [5] C          // i + oldCap
                               [6]
                               [7]

Lo / hi split is the name for that stay-or-move. Tree bins split the same way, then each half untreeifies if it shrank to six or fewer.

Resize is the expensive put: allocate a larger array, walk every node, relink. Averaged over many inserts it is amortized, like ArrayList growth. The put that crosses the threshold is not expected O(1) on that call.

Pre-size when you know n. Do not tune the load factor before a profile says 0.75 is the problem.

One null key, null values, fail-fast, not shared

byId.put(null, order);             // legal — bin 0
byId.put("ORD-1001", null);        // legal — key present, value null
Order v = byId.get("ORD-1001");    // null — missing or mapped-to-null?
boolean here = byId.containsKey("ORD-1001"); // true

Iterators on keySet / values / entrySet are fail-fast: a structural put / remove from outside that iterator throws ConcurrentModificationException. Iterator.remove is allowed. Fail-fast is not a memory barrier. The hub already said so.

for (String id : byId.keySet()) {
    if (id.startsWith("TMP-")) {
        byId.remove(id);           // CME — structural change during iteration
    }
}

byId.keySet().removeIf(id -> id.startsWith("TMP-")); // the supported bulk form

HashMap is not thread-safe. Two writers, or a writer and a reader without a happens-before you own, can lose updates or throw CME. Pre-Java 8 a concurrent resize could livelock a reader; Java 8 rewrote transfer and closed that loop. The type is still not a concurrent map. Shared maps: ConcurrentHashMap. The legacy whole-table lock: Hashtable, in Legacy Collections. Do not pick Hashtable because the Javadoc says synchronized.

Mutable keys lose the entry

The table finds a bin with hashCode, then confirms with equals. Mutate a field that participates in either after put, and get looks in a different bin than the node occupies. The equals and hashCode post owns that contract; this section is the table’s consequence.

final class MutableOrderId {
    String id;
    MutableOrderId(String id) { this.id = id; }

    @Override
    public boolean equals(Object o) {
        return o instanceof MutableOrderId m && id.equals(m.id);
    }

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

Map<MutableOrderId, Order> byMutable = new HashMap<>();
MutableOrderId key = new MutableOrderId("ORD-1001");
byMutable.put(key, order);

key.id = "ORD-9999";
byMutable.get(new MutableOrderId("ORD-1001")); // null — wrong bin
byMutable.get(new MutableOrderId("ORD-9999")); // null — looks in the new bin, node is in the old
byMutable.containsValue(order);                // true — the node is still in the table

The entry did not vanish from memory. It vanished from the hash’s point of view. size() still counts it. You will not find it by key.

Record keys work because components define equals and hashCode, and those fields are final:

public record Order(
        String id,
        String customerEmail,
        List<LineItem> items,
        BigDecimal total,
        boolean active) {}

Map<String, Order> byId = new HashMap<>();
byId.put(order.id(), order);
byId.get(new String("ORD-1001")); // same chars → same hash → equals → hit

Key by Order.id (String), or by a small record of the identifying components. Do not key by a mutable Order bean and then change id. Arrays are identity for equals / hashCode — wrap values in a record instead.

Note: Two records with the same components are equal even if they are different objects. That is what you want in a map key. IdentityHashMap is the type that asks == instead — see IdentityHashMap and WeakHashMap.

Iteration is not a sequence

Walking entrySet after Java 8 follows bins, then chains or trees. Resize and treeify can change that walk. It is stable until the next structural change, and it is not insertion order, not access order, not sorted keys.

Map<String, Order> byId = new HashMap<>();
byId.put("ORD-1001", a);
byId.put("ORD-1002", b);
byId.put("ORD-1003", c);
for (String id : byId.keySet()) {
    // some order of 1001/1002/1003 — do not assert it in a test
}

If a test (or a customer) needs a first and a last, you wanted a sequenced map. LinkedHashMap implements SequencedMap on Java 21. HashMap does not.

vs LinkedHashMap, TreeMap, IdentityHashMap

Same Map contract. Different extra promise.

Type	Encounter order	Nulls	Extra promise
`HashMap`	none (unspecified)	one null key, null values	default; expected `O(1)`
`LinkedHashMap`	insertion or access	same as HashMap	iterate in that order; LRU hook
`TreeMap`	sorted by key	no null key (natural order)	`O(log n)`, ceiling / floor
`IdentityHashMap`	none	yes (identity)	keys compared with `==`

Pick HashMap unless you can name the extra promise you are paying for.

When not to use HashMap

Skip the default when the extra promise is the job:

Encounter order. Packing slips, audit trails, tests that assert first-seen keys. That is LinkedHashMap.
Sorted keys or a range. “All ids ≥ ORD-1000,” ceilingKey, first/last by key. That is TreeMap.
== instead of equals. Canonicalizing interned keys, or identity-sensitive caches. That is IdentityHashMap.
Another thread writes. ConcurrentHashMap. Not a synchronized wrapper around this class as a default, and not Hashtable.
The key will mutate. Fix the key type. A HashMap cannot save a bean whose id changes after put.

Five entries in an ArrayList you already scan is not a hash-table problem. Do not add a map to look serious.

Interview lens

This is the flagship map question. They want the drawing, the mask, the treeify numbers, and the sentence “expected O(1), not worst-case O(1).”

Complexity.

get / put / remove / containsKey    expected O(1)    worst O(n) in a fat list bin
                                                     O(log n) in a tree bin
resize (that one put)               O(n)             amortized across puts
iteration                           O(n)
containsValue                       O(n)

Expected assumes a hash that spreads and a load factor you respect. Treeify is a mitigation for a bad bin, not a new law.

What to draw. Power-of-two Node[]. One chain of three. Formulae on the side: h = hashCode ^ (hashCode >>> 16), i = (n - 1) & h. Caption: treeify at 8 if n >= 64, else resize. Load 0.75, double on resize, lo/hi rebin. One null key in bin 0.

h = key.hashCode() ^ (key.hashCode() >>> 16)
i = (n - 1) & h

[ i ] -> Node -> Node -> Node     length 7: list
                                  length 8 and n >= 64: TreeNode (red-black)
                                  length 8 and n < 64: resize, try not to tree

Typical questions:

Question	Honest answer
Draw `HashMap`.	`Node[]` of power-of-two length. Each bin a list (or a tree). Index `(n - 1) & spreadHash`.
Why XOR `>>> 16`?	Power-of-two tables only use low bits. Spreading mixes high bits down so keys that differ only in the top half do not all collide.
Treeify at 8 — why also 64?	Eight nodes in one bin is the trigger. If the table is still smaller than `MIN_TREEIFY_CAPACITY` (64), resize and rebin instead of paying for a tree on an undersized array. Untreeify at 6 so the bin does not flap.
What does resize do?	Double capacity. Rebin with `hash & oldCap`: stay at `i` or move to `i + oldCap`. Threshold is `capacity * 0.75`.
`equals` / `hashCode`?	Equal keys must share a `hashCode`. The table buckets on hash, then `equals`. Break the pair and `get` misses. Records keep them in sync.
Mutable key?	Mutate a hashed field after `put` and the node sits in the old bin. `get` uses the new hash. The entry is lost to lookup.
`HashMap` vs `Hashtable` vs `ConcurrentHashMap`?	`HashMap` is the default, nulls allowed, not shared. `Hashtable` is a legacy whole-table lock, no nulls — skip it. `ConcurrentHashMap` is the shared map, no nulls, weakly consistent iterators.
Is `get` always `O(1)`?	Expected `O(1)`. A constant `hashCode` makes one list (`O(n)`). A tree bin is `O(log n)` for that bin. Resize of that `put` is `O(n)`.

Wrong answer: “HashMap.get is always O(1), even with a broken hashCode.” A collapsed hash is a linked list (or a tree of equal hashes). The Javadoc’s “constant time” is the expected bet, not a guarantee on the next call.

Cheat sheet

Default        new HashMap<>() — 16, load 0.75, lazy table
Index          h = hashCode ^ (hashCode >>> 16);  i = (n - 1) & h
Bin            Node chain; TreeNode if length >= 8 and n >= 64
Untreeify      bin / split size <= 6
Resize         double n; lo/hi via hash & oldCap; threshold n * 0.75
Nulls          one null key (bin 0), null values
Order          unspecified; not SequencedMap
Threads        not safe — ConcurrentHashMap, not Hashtable
Iterators      fail-fast
Keys           equals + hashCode; records; do not mutate after put
get            expected O(1); worst O(n) list / O(log n) tree bin

Do:

new HashMap<>() (or a capacity hint) as the default Map.
Key by Order.id or an immutable record of the identifying fields.
Say “expected O(1)” and name treeify / resize when they ask for the asterisk.

Don’t:

Mutate a key already in the table.
Depend on iteration order.
Call it thread-safe, or reach for Hashtable as the fix.
Treat treeify as permission to ship hashCode() { return 0; }.

Wrap-up

HashMap is the default Map: a power-of-two table of nodes, a spread hash, chains that treeify at eight when the table is already at least 64, and a doubling resize that rebins with one extra bit. One null key, null values, fail-fast iterators, no encounter order, no shared writers. Record keys keep equals / hashCode honest; a mutable key after put is how an entry disappears without remove.

When iteration must follow insert (or recency), that extra pointer chain is LinkedHashMap.

Next optional step in the series Keep encounter order, or turn access order into a bounded LRU. LinkedHashMap: Insertion Order, Access Order, and a Real LRU

HashMap:The Default Map and What the Table Actually Does

The default map

What to draw: a table of nodes

Why XOR shift: hash ^ (hash >>> 16)

Collisions stay a chain — until they do not

Treeify at 8, but only if capacity is at least 64

Resize doubles, then rebins

One null key, null values, fail-fast, not shared

Mutable keys lose the entry

Iteration is not a sequence

vs LinkedHashMap, TreeMap, IdentityHashMap

When not to use HashMap

Interview lens

Cheat sheet

Wrap-up

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup

The default map

What to draw: a table of nodes

Why XOR shift: hash ^ (hash >>> 16)

Collisions stay a chain — until they do not

Treeify at 8, but only if capacity is at least 64

Resize doubles, then rebins

One null key, null values, fail-fast, not shared

Mutable keys lose the entry

Iteration is not a sequence

vs LinkedHashMap, TreeMap, IdentityHashMap

When not to use HashMap

Interview lens

Cheat sheet

Wrap-up

Related posts

Pick the Collection:Nulls, Order, Threads, and the Hot Operation

Sequenced Collections:First, Last, and Reversed Without the Ceremony

Stream Gatherers:Custom Intermediate Ops Without Breaking the Pipeline

Java Streams:Filter, Map, and Collect Without the Nested Loop Soup