Java Collections Interview Questions (Internals & Traps) — Freshers to Senior
A senior-level Java Collections interview guide: how HashMap put/get works internally, power-of-two capacity and hash spreading, load factor and resize, treeification, modCount and ConcurrentModificationException, ConcurrentHashMap concurrency, complexity tradeoffs, and predict-the-output traps.
Collections is where Java interviews get real. Anyone can say "HashMap stores key-value pairs" — the senior question is "what happens inside put() on a hash collision, when does it turn a bucket into a tree, and why is the capacity always a power of two?" This is a deep Collections interview guide: HashMap internals bucket-by-bucket, fail-fast vs fail-safe iteration and the modCount machinery behind ConcurrentModificationException, how ConcurrentHashMap achieves lock-free reads, the real complexity tradeoffs, and the null-key and mutable-key traps interviewers love.
HashMap internals — the marquee question
Q1. How does HashMap work internally (put & get)?
A HashMap is an array of buckets (Node<K,V>[] table). On put(k,v):
// 1. spread the hash to mix high bits into low bits static int hash(Object k){ int h; return k==null?0:(h=k.hashCode())^(h>>>16); } // 2. index into the table — power-of-2 size lets & replace % int i = (n - 1) & hash; // 3. empty bucket -> place node. Collision -> walk chain: // key equal (hash== && equals()) -> replace value // else append; if chain length >= 8 (& table>=64) -> treeify
get(k) recomputes the index, then compares by hash first (cheap) and equals() only on a hash match. This is why a key's hashCode() and equals() must be consistent — a broken pair means get can't find what put stored.
Q2. Why is capacity a power of 2, and why the h ^ (h >>> 16) trick?
Power-of-2 capacity lets the map use (n-1) & hash instead of the slower hash % n — a bitmask. But masking only keeps the low bits, so two hashes differing only in high bits would collide. The spread (h ^ (h >>> 16)) XORs the high 16 bits down into the low 16, so high-bit differences still affect the bucket. Cheap, and it dramatically cuts collisions.
Q3. What is the load factor, and what happens on resize?
Default load factor is 0.75 — a space/time tradeoff: when size > capacity * 0.75, the table doubles and every entry is rehashed into the bigger table (O(n) cost, amortised). 0.75 balances low collision probability against wasted space; too high → long chains, too low → wasted memory and frequent resizes.
Q4. Treeification — the Java 8 change.
Before Java 8, a bucket was a linked list, so a pathological all-collide case degraded get to O(n). Java 8 converts a bucket to a red-black tree when its chain length reaches 8 and the table has ≥64 slots, bounding worst-case lookup at O(log n). It untreeifies back to a list below 6. (A DoS-hardening measure against crafted hash collisions.)
Q5. Predict the output — mutable key in a HashMap.
Map<List<Integer>,String> m = new HashMap<>(); List<Integer> key = new ArrayList<>(List.of(1)); m.put(key, "v"); key.add(2); // mutating the key changes its hashCode! System.out.println(m.get(key)); // null — lands in a different bucket now
Never use a mutable object as a HashMap key. Its hashCode changes, so the entry becomes unreachable — a real, hard-to-find production bug.
Iterators — fail-fast vs fail-safe
Q6. What causes ConcurrentModificationException? Is it thrown only in multithreading?
No — it's most often single-threaded. Collections like ArrayList/HashMap keep a modCount that increments on structural change. The iterator snapshots it as expectedModCount; every next() checks modCount == expectedModCount and throws if they differ. So modifying a collection while iterating it (except via the iterator's own remove()) trips it.
// WRONG — throws ConcurrentModificationException for (String s : list) if (s.isBlank()) list.remove(s); // RIGHT — iterator.remove() keeps modCount in sync Iterator<String> it = list.iterator(); while (it.hasNext()) if (it.next().isBlank()) it.remove(); // OR Java 8+: list.removeIf(String::isBlank);
Q7. Fail-fast vs fail-safe iterators?
Fail-fast (ArrayList, HashMap) iterate the live collection and throw on concurrent structural change — no memory overhead, but not safe under concurrency. Fail-safe (CopyOnWriteArrayList, ConcurrentHashMap) iterate over a snapshot or tolerate concurrent writes without throwing — safe, but the iterator may not reflect the latest state and can cost memory (copy-on-write).
Concurrency: HashMap vs Hashtable vs ConcurrentHashMap
Q8. Compare the three.
| HashMap | Hashtable | ConcurrentHashMap | |
|---|---|---|---|
| Thread-safe | No | Yes (whole-map lock) | Yes (bin-level) |
| Locking | — | synchronized methods | CAS + synchronized on bin |
| null key/value | 1 null key, many null vals | None | None |
| Use | Single-thread default | Legacy — avoid | Concurrent default |
Q9. How does ConcurrentHashMap achieve concurrency without locking the whole map?
Java 7 split it into segments (default 16), each independently locked — up to 16 concurrent writers. Java 8 removed segments: it locks at the individual bucket (bin) level. An empty bin is filled with a lock-free CAS; a non-empty bin is updated under a synchronized block on the bin's head node. Reads are lock-free (bins/values are volatile), so get() never blocks. That's why it scales far better than Hashtable.
List, Set, Queue internals
Q10. ArrayList vs LinkedList — when does each win?
| Operation | ArrayList | LinkedList |
|---|---|---|
| get(i) / random access | O(1) | O(n) — walk nodes |
| add at end (amortised) | O(1)* | O(1) |
| add/remove at head | O(n) — shift | O(1) |
| memory | compact array | node overhead (prev/next) |
*ArrayList grows by ~1.5× when full (copy to a new array). In practice ArrayList wins almost always — cache locality makes its O(n) shifts faster than LinkedList's pointer chasing. Reach for LinkedList only for heavy head/tail insertion (as a Deque). Full comparison: ArrayList vs LinkedList.
Q11. How do HashSet and TreeSet work?
HashSet is a thin wrapper over a HashMap — elements are keys, values a dummy constant; so it inherits O(1) add/contains and no ordering. TreeSet/TreeMap use a red-black tree, giving sorted order and O(log n) operations, ordered by natural order or a Comparator. LinkedHashMap adds a doubly-linked list across entries to preserve insertion (or access) order — access-order mode makes it a ready-made LRU cache via removeEldestEntry.
Q12. Predict the output — null keys.
new HashMap<>().put(null, "ok"); // fine — null hashes to bucket 0 new Hashtable<>().put(null, "x"); // NullPointerException new TreeMap<>().put(null, "x"); // NPE — compareTo(null) fails new ConcurrentHashMap<>().put(null,"x"); // NPE — null banned (ambiguity w/ absent)
Q13. PriorityQueue — how is it ordered?
A PriorityQueue is a binary min-heap backed by an array: peek() is O(1) (the smallest/highest-priority element), offer()/poll() are O(log n). It is not fully sorted — only the head is guaranteed. Ordering follows natural order or a supplied Comparator.
Immutability & utility
Q14. Collections.unmodifiableList vs List.of — both immutable?
Collections.unmodifiableList(x) is an unmodifiable view — mutating the backing list still shows through. List.of(...) (Java 9) is a truly immutable, null-hostile copy with no backing reference to mutate. Prefer List.of/Map.of for real immutability.
Complexity cheat-sheet
| Structure | get/contains | add | Order |
|---|---|---|---|
| HashMap/HashSet | O(1) avg | O(1) avg | None |
| TreeMap/TreeSet | O(log n) | O(log n) | Sorted |
| LinkedHashMap | O(1) avg | O(1) avg | Insertion/access |
| ArrayList | O(1) index | O(1) amort. end | Insertion |
Go deeper by topic
- Core Java interview questions — the backbone set
- OOP interview questions — polymorphism, SOLID, abstract vs interface
- Multithreading interview questions — JMM, volatile, why ConcurrentHashMap is safe
- Streams interview questions — Collectors turn collections into results
- ArrayList vs LinkedList — the full deep-dive
What finally made collections click for me wasn't memorising the API — it was tracing one put() call all the way down: hash it, spread it, mask it into a bucket, walk the chain, treeify if it's too long, resize when the table fills. Once you can narrate that, every follow-up — "why power of two?", "why 0.75?", "when does it become a tree?" — is just a stop along a path you already know. Do the same for ConcurrentHashMap's bin-level locking and the modCount check behind fail-fast iteration, and you'll answer the whole family of questions from one mental model instead of ten flashcards. That's the difference between reciting collections and understanding them — and interviewers can tell instantly. You've got this.
Related
← OOP interview questions · Multithreading interview questions →