Java HashMap Internals Interview Questions
Last updated 2026-11-19
"How does HashMap work internally?" is probably the single most repeated Java interview question, and interviewers keep digging until you run out of detail. A complete answer covers the table, the hash function, index calculation, collision handling, treeification, resizing and the equals/hashCode contract.
This page walks through these in the order an interviewer typically probes them, using the OpenJDK implementation from Java 8 onwards. The wider API is covered on the Java collections page.
| Default capacity | 16 buckets |
|---|---|
| Default load factor | 0.75, so resize after 12 entries |
| Treeify threshold | 8 nodes in a bucket and table size at least 64 |
The one-paragraph answer
HashMap keeps an array of buckets. put(key, value) computes hash(key), maps it to an index with (n - 1) & hash, and stores a node there. Nodes with the same index form a linked list, converted to a red-black tree when a bucket reaches 8 entries and the table has at least 64 slots. When the entry count exceeds capacity times load factor, the table doubles and entries are redistributed.
Java HashMap Internals Interview Questions: questions with worked answers
1 Describe the internal structure of a HashMap.
easyIt holds a Node<K,V>[] table whose length is always a power of two. Each Node stores the key, value, the cached hash and a next pointer. The table is allocated lazily on the first put, with default length 16, a load factor of 0.75 and therefore a threshold of 12. Fields such as size, modCount and threshold support resizing and fail-fast iteration.
2 How is the bucket index computed, and why does HashMap spread the hash?
mediumhash(key) is key.hashCode() XOR-ed with itself shifted right 16 bits, which mixes the high bits into the low bits. The index is (n - 1) & hash. Because n is a power of two, n - 1 is a mask of low bits, so only the low bits of the hash would matter without spreading, and keys whose hash codes differ only in the high bits (for example floats) would collide heavily.
javaint n = 16; int h1 = Integer.valueOf(1).hashCode(); // 1 int h17 = Integer.valueOf(17).hashCode(); // 17 System.out.println((n - 1) & h1); // 1 System.out.println((n - 1) & h17); // 1 -> same bucket as key 13 Why is the table size always a power of two?
mediumWith a power-of-two length, (n - 1) & hash replaces a slower modulo and always gives a valid index. It also makes resizing cheap: after doubling, each node either stays at its old index or moves to oldIndex + oldCapacity, decided by a single extra bit of the hash. new HashMap<>(100) rounds the capacity up to 128 through tableSizeFor.
4 Walk through put(key, value) step by step.
medium1. If the table is null or empty, resize() allocates it. 2. Compute the index. If the bucket is empty, place a new node. 3. Otherwise compare the first node by hash and then == or equals; if it matches, replace the value. 4. If the bucket is a tree, insert into the tree. 5. Otherwise walk the list; replace on a match or append at the tail, and convert the bucket to a tree if the list length reaches the threshold of 8. 6. Increment size and resize if it exceeds the threshold. put returns the old value or null.
5 How does get(key) work, and what is its complexity?
mediumIt hashes the key, finds the bucket, checks the first node and then walks the list or tree comparing the cached hash first and then equals. Average cost is O(1). With a poor hashCode that sends many keys to one bucket the cost is O(n) in a list, and O(log n) since Java 8 once the bucket is treeified.
6 What happens in a collision, and when is a bucket treeified or untreeified?
hardColliding keys are chained in a linked list. When a single bucket reaches 8 nodes (TREEIFY_THRESHOLD), the bucket becomes a red-black tree, but only if the table has at least 64 slots; otherwise HashMap resizes instead, since more buckets usually fixes the problem. When a resize or removal shrinks a tree bucket to 6 nodes or fewer (UNTREEIFY_THRESHOLD) it goes back to a list. The gap between 8 and 6 prevents flip-flopping.
7 Show two different strings with the same hashCode and explain what a HashMap does with them.
medium"Aa" and "BB" both have hashCode 2112, since 65*31+97 equals 66*31+66. They land in the same bucket, so the map compares the cached hash (equal), then calls equals (false) and keeps both nodes in the chain. Correctness is preserved by equals; only speed suffers.
javaMap<String,Integer> m = new HashMap<>(); m.put("Aa", 1); m.put("BB", 2); System.out.println("Aa".hashCode() == "BB".hashCode()); // true System.out.println(m.get("Aa") + " " + m.get("BB")); // 1 28 What happens during resize?
mediumWhen size exceeds threshold, resize() allocates a table of twice the length and moves the nodes. Since Java 8, each bucket is split into a low list that keeps its index and a high list that goes to index + oldCap, preserving relative order within each. Rehashing is not recomputed from scratch; the bit (hash & oldCap) decides. Resizing is O(n), so presizing a map avoids repeated copies.
9 How do you presize a HashMap to avoid resizing for 100 entries?
mediumYou need capacity at least 100 / 0.75 = 133.3, so ask for 134 or more, which rounds up to a 256 table. A common mistake is new HashMap<>(100), which becomes 128 buckets with threshold 96, so the 97th insertion resizes. Java 19 added HashMap.newHashMap(100) that does the arithmetic for you.
javaMap<Integer,String> m = HashMap.newHashMap(100); // Java 19+ // before 19: new HashMap<>((int) (100 / 0.75f) + 1)10 How are null keys handled?
mediumHashMap allows one null key. hash(null) returns 0, so it always sits in bucket 0, and lookups use == null instead of equals. Because get returns null both for a missing key and for a null value, use containsKey or getOrDefault when null values are possible.
11 Why must keys be immutable, and what if hashCode is bad or missing?
hardIf a key field used in hashCode changes after insertion, the entry is looked up in the wrong bucket and becomes effectively lost. If equals is overridden without hashCode, equal keys hash differently and the map stores duplicates. If hashCode returns a constant, all entries share one bucket: in Java 8 and later a tree bucket gives O(log n) only if the key is Comparable, otherwise lookups degrade towards O(n).
12 What is the iteration order of a HashMap? Predict this output.
mediumThere is no guaranteed order, and it can change after a resize. Small Integer keys appear sorted only by accident, because their hash is their value and the buckets are visited in index order. Never rely on it; use LinkedHashMap for insertion order or TreeMap for sorted order.
javaMap<Integer,String> m = new HashMap<>(); m.put(3, "c"); m.put(1, "a"); m.put(2, "b"); System.out.println(m); // {1=a, 2=b, 3=c} in practice m.put(17, "q"); System.out.println(m); // {1=a, 17=q, 2=b, 3=c} (17 shares bucket 1)13 How do HashMap, Hashtable, synchronizedMap and ConcurrentHashMap differ?
mediumHashMap is unsynchronised and allows nulls. Hashtable is a legacy class with every method synchronised on the whole table and no nulls. Collections.synchronizedMap wraps a map with a single lock and still needs manual locking for iteration. ConcurrentHashMap allows concurrent reads and fine-grained writes and offers atomic methods such as compute, merge and putIfAbsent. See Java concurrency utilities.
14 How does ConcurrentHashMap achieve thread safety in Java 8 and later?
hardThe old segment locking was removed. An insert into an empty bucket uses a compare-and-swap, and inserts into an occupied bucket synchronise on that bucket head node only, so different buckets update in parallel. Reads are mostly lock-free using volatile fields. Size is tracked with striped counters, and resizing is shared across threads that help transfer bins. Null keys and values are disallowed.
15 Is HashMap safe under concurrent modification? What went wrong historically?
hardNo. In Java 7 a concurrent resize could link nodes into a cycle and make get spin forever on one CPU. Java 8 fixed the cycle by preserving order during the split, but concurrent puts can still lose updates, corrupt size and throw ConcurrentModificationException during iteration. Use ConcurrentHashMap.
16 Implement an LRU cache with LinkedHashMap.
mediumLinkedHashMap with accessOrder true moves each accessed entry to the end, so the eldest entry is the least recently used. Override removeEldestEntry to evict once the size exceeds the limit. This is O(1) for get and put but not thread safe.
javaclass LRU<K,V> extends LinkedHashMap<K,V> { private final int cap; LRU(int cap) { super(16, 0.75f, true); this.cap = cap; } @Override protected boolean removeEldestEntry(Map.Entry<K,V> e) { return size() > cap; } } LRU<Integer,String> c = new LRU<>(2); c.put(1, "a"); c.put(2, "b"); c.get(1); c.put(3, "c"); System.out.println(c.keySet()); // [1, 3]17 How is HashSet related to HashMap?
easyA HashSet is a thin wrapper around a HashMap. Each element becomes a key and the value is a shared dummy object named PRESENT. add returns true when the underlying put returns null, which is why HashSet inherits all the hashing and equals rules above.
Frequently asked questions
What is the default capacity and load factor of HashMap?
Capacity 16 and load factor 0.75, so it resizes when the 13th entry is added. The table is created on the first put.
Why 8 for treeification?
With a good hash function bucket sizes follow a Poisson distribution, and a bucket of 8 is extremely rare. The tree is a safeguard against bad hash codes and denial-of-service collisions, not a common path.
Does HashMap keep insertion order?
No. LinkedHashMap does. TreeMap keeps keys sorted.
Can two keys with the same hashCode both be stored?
Yes. They go into the same bucket and equals tells them apart.
Related guides
More in Programming Language Interview Questions by Language
- Java Interfaces and Abstract Classes Interview Questions
- Java Interview Questions and Answers
- Java Multithreading Interview Questions
- Java OOPs Interview Questions
- Java String Interview Questions
- JavaScript Array Methods Interview Questions
- JavaScript Closures Interview Questions
- JavaScript Coding Interview Questions with Solutions
- JavaScript DOM Interview Questions
- JavaScript ES6 Interview Questions
- JavaScript Event Loop Interview Questions
- JavaScript Hoisting and Scope Interview Questions