HashMap Internals: How put() and get() Really Work

"How does HashMap work internally?" is one of the most-asked Java interview questions — at every level. A good answer walks through the data structure, what happens on put() and get(), collisions, resizing, and the equals/hashCode contract. Here is that answer, step by step (Java 8+ behaviour).

The structure: an array of buckets

A HashMap is backed by an array called the table. Each slot is a bucket that holds zero or more entries (Node<K,V>: hash, key, value, next).

• The default capacity is 16 buckets, and it is always a power of two.
• The load factor defaults to 0.75: when the number of entries exceeds capacity × 0.75 (12 for the default), the table resizes.
• A bucket holds a linked list of nodes — or, if it gets long, a red-black tree.

Step 1: computing the bucket index

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// index = (n - 1) & hash     where n = table length (a power of two)

Two details matter:

1. Hash spreading — h ^ (h >>> 16) mixes the high bits into the low bits. Because the index only uses the low bits ((n - 1) & hash), without spreading, keys whose hashCodes differ only in high bits would all collide.
2. Power-of-two sizing — (n - 1) & hash is a fast replacement for hash % n, and it only works when n is a power of two.

A null key always hashes to 0, so it lives in bucket 0. HashMap allows one null key and any number of null values.

Step 2: put(key, value)

1. Compute hash(key) and the bucket index.
2. If the bucket is empty, create a new node there.
3. Otherwise walk the bucket:
   • for each node, if node.hash == hash and (node.key == key or key.equals(node.key)), replace the value and return the old one;
   • if no match, append a new node (to the list's tail, or insert into the tree).
4. Increment size; if size > threshold, resize.
5. If a list bucket now has 8 or more nodes and the table has at least 64 buckets, convert that bucket to a red-black tree (treeification). With a smaller table, HashMap resizes instead.

Step 3: get(key)

1. Compute the hash and index.
2. Check the first node in the bucket (the common fast path).
3. Walk the list — or search the tree in O(log n) — comparing hash first, then equals().
4. Return the value, or null if not found.

That's why get() is O(1) on average: a good hash spreads keys across buckets, so each bucket holds very few entries. In the worst case (everything collides), Java 8+ degrades to O(log n) thanks to treeified buckets, instead of O(n) in older versions.

Resizing

When the threshold is exceeded, the table doubles. Every entry is moved to the new table — and because capacity is a power of two, each node either stays at the same index or moves to index + oldCapacity, decided by one extra bit of the hash. No full rehash is needed.

Resizing is O(n), so if you know the size in advance, pre-size the map:

// Java 19+: sizes the table so 1,000 entries fit without resizing
Map<String, User> users = HashMap.newHashMap(1_000);

(Before Java 19, use new HashMap<>((int) (expected / 0.75f) + 1).)

Why equals() and hashCode() must agree

The lookup is hash first, then equals. So:

• Equal objects must have equal hash codes. If you override equals() but not hashCode(), two "equal" keys usually land in different buckets — get() returns null for a key that is logically present.
• Unequal objects may share a hash code (a collision) — that only costs performance.

class User {
    String email;
    @Override public boolean equals(Object o) {
        return o instanceof User u && email.equals(u.email);
    }
    @Override public int hashCode() { return email.hashCode(); }   // must be consistent with equals
}
// Or simply: record User(String email) {}  — equals and hashCode are generated

Never mutate a key

If a key's fields change after insertion, its hash changes — but it stays in the old bucket. The entry becomes unreachable by get(), a quiet memory leak. Use immutable keys (String, Integer, records, enums).

HashMap is not thread-safe

Concurrent put() calls can lose updates or corrupt the structure. Use ConcurrentHashMap for shared maps — it locks per bucket (CAS for empty buckets, synchronized on the bucket's first node otherwise) and rejects null keys and values, so get() returning null unambiguously means "absent".

Summary

Follow-up questions this topic invites — and their answers

Q: Why is the treeify threshold 8? A: With a good hash function and load factor 0.75, bucket sizes follow a Poisson distribution; 8 entries in one bucket is extremely unlikely by chance. Treeification is a defence against poor or malicious hash codes, not a normal path. Buckets shrink back to lists at 6 entries.

Q: Does HashMap keep insertion order? A: No. Use LinkedHashMap for insertion (or access) order, and TreeMap for sorted keys.

Q: What happens with a mutable key used in a HashSet? A: The same problem — contains() and remove() can no longer find it. HashSet is backed by a HashMap.

Q: How is ConcurrentHashMap's size() computed? A: It sums per-cell counters (like LongAdder), so it's fast but only a moment-in-time estimate under concurrent updates.

Want more? The Collections chapter and our Java Interview Prep courses cover HashMap, TreeMap and ConcurrentHashMap questions at every level.