How HashMap works

For this lesson, we'll focus on the core HashMap path you should be able to draw in an interview: Node<K,V>[] table, lazy allocation, hash() spreading, power-of-two indexing, putVal, getNode, the equals/hashCode contract, initialization choices and the everyday helper methods. Interviewers love this one because it is small enough for a whiteboard and subtle enough to expose memorised answers.

01Picture it first: mailboxes and envelopes

Picture an apartment wall with numbered mailboxes. The HashMap table is the wall, each bucket is one mailbox, and each Node is an envelope inside that mailbox. A good hash spreads envelopes across mailboxes, but the final check is still the name on the envelope: equals.

The important model is array first, chain second. We jump to one bucket in O(1), then handle whatever is inside that bucket.

Fig. 1

A HashMap bucket array with bucket 0 holding the null key, bucket 3 holding one node, bucket 6 holding a chain of three nodes, and each node storing hash, key, value and next

Notice the shape. The table slot does not store your value directly; it stores the head Node. Each node caches the spread hash so later lookups, resizes and equality checks do not have to call hashCode() again.

Conceptually, a node is this small:

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

That final K key does not make the key object immutable. It only means the node points to the same key reference for its lifetime. If that key's fields change and its hashCode() changes, the node stays in the old bucket and future lookups go to the new bucket. That's the famous mutable-key bug.

02HashMap under the hood: table, hash and index

A no-argument new HashMap<>() starts light. The object is created, but the bucket table is not. On the first put, resize() allocates the default table length of 16 and sets the resize threshold to 16 * 0.75 = 12.

Map<String, Integer> counts = new HashMap<>();

counts.put("paid", 7);      // first put allocates 16 buckets
counts.put(null, 1);        // null key gets hash 0, bucket 0
counts.put("PAID", 2);

System.out.println(counts.get("paid")); // 7
System.out.println(counts.get(null));   // 1

Notice three things:

• HashMap allows one null key and many null values.
• The null key is not special storage outside the table. It is a normal node with hash 0, found in bucket 0.
• A missing key and a key mapped to null both make get return null, so use containsKey when that distinction matters.

Step 1: spread the hash

JDK 21's hash helper is short:

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

With 16 buckets, only 4 low bits choose the index. That is a problem if two keys differ mostly in the high bits, because (n - 1) & hash would ignore those high bits. h ^ (h >>> 16) folds some high-bit information into the low bits with one shift and one XOR. It is not cryptography. It is a cheap guardrail against common poor distributions.

Step 2: use a power-of-two mask

HashMap keeps table lengths as powers of two: 16, 32, 64 and so on, up to 1 << 30. That makes bucket selection:

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

For a table length of 16, table.length - 1 is binary 1111, so the mask keeps the low 4 bits. This behaves like hash % 16 for non-negative values, but it is one bitwise operation and does not produce a negative index. The trade-off is that low bits matter a lot, which is why spreading happens first.

Many candidates say, "it uses modulo". I would be more precise: it uses a bit mask because the capacity is a power of two. That sentence usually earns the follow-up instead of ending the conversation.

03The put() flow: what putVal does

Here is the path I draw on a whiteboard. The method names in the JDK are put and putVal, but you do not need to recite the source line by line. You need to tell the story in the right order.

Fig. 2

The put flow spreads the hash, allocates the table if needed, masks to a bucket, inserts into an empty bucket, replaces a matching key, or handles a tree bin or list before checking resize

Map<String, Integer> scores = new HashMap<>();
scores.put("Aa", 10);
scores.put("BB", 20);

System.out.println(scores.size());       // 2
System.out.println(scores.get("Aa"));    // 10
System.out.println(scores.get("BB"));    // 20

A collision is not a lost value. Both keys land in the same bucket, but they are not equal, so the bucket stores two nodes. The hash gets you to a small search area; equals tells you whether a node is the one you asked for.

putVal is roughly this:

1. Spread the key hash, using 0 for null.
2. If the table is empty, allocate it through resize().
3. Compute i = (n - 1) & hash.
4. If table[i] is empty, create a new node there.
5. Otherwise compare the first node: same cached hash, and keys are == or equals.
6. If it matches, replace the value and return the old value.
7. If it is a tree bin, delegate to the tree path. We'll cover that in the next lesson.
8. Otherwise walk the linked list. A matching key updates; reaching the end appends a new node.
9. A new mapping increments size and modCount; if size passes threshold, resize.

Two details are worth saying out loud. First, updating an existing key does not increase size. Second, since Java 8, new list nodes are appended at the tail, not inserted at the head, which also removed one cause of the old Java 7 resize cycle bug.

04The get() flow: hash, bucket, compare

get is the same mental path without mutation. It spreads the hash, masks to a bucket, checks the first node, and then either walks the list or searches the tree bin.

record UserId(String tenant, long id) { }

Map<UserId, String> names = new HashMap<>();
UserId key = new UserId("acme", 42);
names.put(key, "Mina");

System.out.println(names.get(new UserId("acme", 42))); // Mina

This works because records implement value-based equals and hashCode from their components. The lookup key is a different object, so == is false, but the cached hash matches and equals returns true. That's exactly what map keys are for.

The comparison order is important:

if (first.hash == hash &&
        ((k = first.key) == key || (key != null && key.equals(k)))) {
    return first;
}