Everything an interviewer can ask about HashMap internals — bucket structure, hashing, collisions, treeification, resizing, and the failure modes each one causes — answered before they ask it.
Published September 22, 2026
Most candidates know HashMap is "fast, O(1) average case." That sentence survives about one follow-up question. This lesson goes deep enough that it doesn't.
HashMap is backed by Node<K,V>[] table. Default initial capacity is 16, always a power of two. Default load factor is 0.75 — once size > capacity * loadFactor, it resizes.
Map<String, Integer> scores = new HashMap<>(); // capacity 16, resize threshold = 12
Why a power of two, specifically? Because bucket indexing uses a bitmask (capacity - 1), not modulo — see §2. A bitmask only produces a clean, evenly-distributed range of indices when capacity is a power of two; any other capacity would waste some bit patterns and bias toward lower buckets.
Why 0.75 and not, say, 0.9 or 0.5? It's the documented Java tradeoff between memory and lookup time. A higher load factor packs more entries per bucket before resizing (less wasted array space) but increases average chain length, so more .equals() comparisons per lookup. A lower load factor keeps chains short (faster lookups) but wastes array space and triggers resizes more often. 0.75 is empirically the sweet spot for general-purpose use — you can override it via new HashMap<>(capacity, loadFactor) if you know your access pattern skews one way.
Two steps, not one.
Step 1 — spread the hash:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
This XORs the high 16 bits down into the low 16 bits.
Step 2 — bitmask into the table:
index = (capacity - 1) & hash;
Why not just hash % capacity? Because & (bitwise AND) is a single fast CPU instruction, while % (modulo) is comparatively expensive — division-based. This optimization only works because capacity is a power of two, which is exactly why capacity is forced to stay a power of two (§1).
Why the spreading step, then? With small capacities (16 = 4 bits), the bitmask capacity - 1 only looks at the lowest 4 bits of the hash. A hashCode() implementation that varies mostly in its high bits (a common pattern) would have all that entropy discarded by the mask, and everything would pile into a handful of buckets regardless of how "good" the hashCode looked on paper. XOR-folding the high bits into the low bits recovers that entropy before the mask throws it away.
Each bucket starts life as a singly linked list of entries. On lookup, Java first compares hashCode() (cheap, an int comparison) and only calls .equals() when hash codes match. This two-step check is why the hashCode/equals contract isn't academic trivia:
If a.equals(b) is true, then a.hashCode() == b.hashCode() must also be true.
Violate it (e.g. override equals() but forget hashCode()) and two logically-equal keys can land in different buckets. map.put(a, x) followed by map.get(b) — where a.equals(b) — silently returns null. No exception, no warning, just a map that appears to have "lost" an entry. This is one of the most common real production HashMap bugs, and almost every interviewer who asks about HashMap will pivot here if you don't bring it up first.
If a single bucket's chain exceeds 8 entries (and the table has ≥64 buckets total), Java converts that bucket from a linked list to a red-black tree, dropping worst-case lookup in that bucket from O(n) to O(log n). If the bucket later shrinks to 6 entries (after removals), it reverts to a linked list.
Why 8 and not, say, 4? Documented in the JDK source: under a good hash distribution, the probability of any bucket reaching 8 entries is vanishingly small (Poisson distribution) — treeification is essentially never triggered by normal usage. It exists specifically as a defense against hash flooding — an attacker deliberately supplying keys engineered to collide (e.g. against a web server's HTTP parameter map) to force O(n) lookups and degrade the service. Without treeification, this is a viable denial-of-service vector; with it, worst-case degrades to O(log n) instead of O(n).
Why does it need 6, not 8, to revert (the 8/6 gap)? To avoid thrashing — if revert threshold equaled the treeify threshold, a bucket sitting right at the boundary could flip back and forth between list and tree representations on every insert/remove, which is wasted work. The gap creates hysteresis.
Once the load factor threshold is crossed, capacity doubles (16→32→64...) and every existing entry is rehashed into the new table, because the bucket-index formula depends on capacity.
new HashMap<>(16_384); // pre-size to avoid ~10 doubling-and-rehash passes during warmup
Why does "O(1) average case" survive resizing at all? Because resizing is amortized — one O(n) resize happens only after n/4 cheap O(1) inserts (roughly), so spread across all inserts, the average stays O(1). But a single put() call that happens to trigger the resize is genuinely O(n) — this matters in latency-sensitive code paths (e.g. a hot request handler), which is exactly why pre-sizing matters for known-size maps in production code, not just as a micro-optimization.
A key's hash code must not change while it's in the map. If it does — e.g. a mutable field used inside hashCode() gets modified after insertion — the entry is still sitting in its original bucket (based on the old hash), but get() computes the new hash and looks in a different bucket. The entry becomes permanently unreachable via get(), even though containsValue() (which does a linear scan) or iteration would still find it. This is a real production bug pattern, not a textbook gotcha — it's why keys should be immutable, and it's a stronger reason than "immutability is good practice."
Q: What's the actual time complexity, worst case? A: O(n) in the pathological case (one bucket holding every entry as a list) before Java 8's treeification; O(log n) worst case since Java 8, because that bucket becomes a red-black tree at 8 entries.
Q: Is HashMap thread-safe? What happens if two threads write concurrently?
A: No. Concurrent structural modification (resize in particular) can corrupt internal linked-list pointers, historically capable of producing an infinite loop during resize in pre-Java-8 implementations (a well-known production incident pattern). Use ConcurrentHashMap for concurrent access — never synchronize a plain HashMap externally as a first choice, since that just serializes all access and defeats the purpose.
Q: HashMap vs Hashtable vs ConcurrentHashMap — when would you use each?
A: Hashtable is legacy, synchronizes the entire map on every operation (coarse-grained lock), and is effectively obsolete. HashMap is unsynchronized, fastest for single-threaded or externally-synchronized use. ConcurrentHashMap uses fine-grained locking for high concurrent throughput without locking the whole map.
Q: What happens if you use a mutable object as a key?
A: See §6 — the entry can become unreachable via get() if the key's hash-relevant fields change after insertion.
Q: How would you handle a HashMap with millions of entries and frequent inserts? A: Pre-size the initial capacity to avoid repeated resize/rehash passes (§5), and choose a load factor appropriate to whether you're optimizing for memory or lookup speed (§1).
Q: What's the difference between HashMap, LinkedHashMap, and TreeMap?
A: HashMap gives no ordering guarantee. LinkedHashMap additionally maintains a doubly-linked list through entries, preserving insertion order (or access order, in LRU-cache mode) at the cost of extra memory per entry. TreeMap maintains full key ordering via a red-black tree (O(log n) operations instead of O(1) average) — reach for it only when you need sorted iteration or range queries (headMap/tailMap).
Write a mutable key class, insert it into a HashMap, mutate the field used in hashCode(), and call get() with an equal key. Watch it return null — then call containsValue() and watch it return true for the very entry get() couldn't find. That contradiction is the entire lesson in one repro.