Collections Internals & Complexity — Interview Questions

How to use this lesson

Collections questions at this level probe internals and failure modes: what actually happens with nulls, bad keys, concurrent writes and resizing. Always pair the Big-O with the constant factors (cache locality, allocation), because that's where the real performance lives.

Q1. What's the difference between List, Set and Map, in behaviour and use?

Short answer:

• List: an ordered sequence with an index, allowing duplicates. Use it for sequences, and positional access (ArrayList by default).
• Set: no duplicates (by equals/hashCode, or by a comparator for sorted sets). Use it for membership and deduplication:
  • HashSet: O(1), unordered;
  • LinkedHashSet: insertion order;
  • TreeSet: sorted, O(log n);
  • EnumSet: bit-vector fast.
• Map: key → value associations with unique keys. Use it for lookup by key (HashMap, LinkedHashMap, TreeMap, EnumMap, ConcurrentHashMap). It isn't a Collection, but it offers keySet(), values() and entrySet() views.

Since Java 21, the sequenced collections interfaces (SequencedCollection, SequencedSet, SequencedMap) give ordered collections a uniform getFirst()/getLast()/reversed() API.

Learn it in depth → List, Set, and Map

Q2. What happens when you insert null keys or values into HashMap, TreeMap and Hashtable?

Short answer:

• HashMap: one null key (stored in bucket 0, with a hash of 0) and any number of null values. get(k) returning null is ambiguous (absent, or mapped to null), so use containsKey.
• TreeMap: a null key throws NullPointerException with natural ordering (it calls compareTo), unless the Comparator explicitly handles nulls (Comparator.nullsFirst(...)). null values are fine.
• Hashtable: no null keys or values. Both throw NullPointerException. The same goes for ConcurrentHashMap, and the immutable Map.of(...).

Q3. Why doesn't HashSet allow duplicates, even with user-defined objects?

Short answer: A HashSet is backed by a HashMap: elements are the keys, with a shared dummy value. add(e) calls map.put(e, PRESENT), which finds the bucket from hashCode(), and checks the existing entries with equals(). If an equal key exists, nothing is added (add returns false). So "duplicate" means equal by your equals/hashCode. If a class doesn't override them, identity is used, and two logically identical objects are both stored.

Q4. How does LinkedHashMap maintain insertion order?

Short answer: It extends HashMap, and each entry also sits in a doubly linked list (before/after pointers), in insertion order. Iteration walks the list, not the buckets, so it's predictable, and proportional to size rather than capacity. Re-inserting an existing key doesn't change its position.

With accessOrder = true, every get/put moves the entry to the tail. Combined with overriding removeEldestEntry, that gives an LRU cache. The costs are two extra references per entry, and slightly slower puts.

Q5. What natural order do TreeMap and TreeSet use?

Short answer: Without a Comparator, they order elements by the elements' Comparable.compareTo:

• numbers numerically;
• String lexicographically by UTF-16 code units (so uppercase comes before lowercase; use Collator or String.CASE_INSENSITIVE_ORDER for human ordering);
• enums by declaration order;
• LocalDate chronologically.

Both are red-black trees, with O(log n) operations, and they add navigation: floorKey, ceilingKey, headMap, tailMap, subMap, descendingMap.

Key points to cover:

• Uniqueness is decided by compareTo/compare returning 0, not by equals.

Q6. Can a TreeSet hold heterogeneous types? What happens if you try?

Short answer: Not with natural ordering. Adding elements of mutually incomparable types throws ClassCastException when compareTo tries to compare, for example, a String with an Integer. Even the first element is compared to itself (since Java 7), to fail fast on non-Comparable objects.

You can store mixed types with a custom Comparator that handles all of them (for example, ordering by class name, then by value), but that's rarely good design. Consider a common supertype or a sealed interface instead.

Q7. What data structures back ArrayList and LinkedList?

Short answer:

• ArrayList: a resizable Object[] (default capacity 10 on first add), which grows by about 50% by copying. It has O(1) random access, amortised O(1) appends, O(n) middle inserts and removes (System.arraycopy), and excellent cache locality.
• LinkedList: a doubly linked list of Node objects (item, next, prev). It has O(1) insert and remove at a known node or at the ends, but O(n) get(i) (it walks from the nearer end), 24–32 bytes of overhead per element, and poor locality. It also implements Deque.

Q8. Why isn't HashMap synchronised, and what goes wrong in multithreaded use?

Short answer: It's designed for single-threaded speed: most maps are confined to one thread, and locking every call would cost everyone. Unsynchronised concurrent writes can cause:

• lost updates: two puts into the same bucket, where one overwrites the other's link;
• corrupted internal state during resize, when two threads transfer the table at once. In Java 7 and earlier, concurrent resize could create a cycle in a bucket's list, so get spun forever at 100% CPU. Java 8 changed the transfer to preserve order, which removed the cycle, but data loss and inconsistent size() remain;
• visibility problems: readers see stale or partially constructed entries;
• ConcurrentModificationException for iterators.

Fix: ConcurrentHashMap, confinement, or immutable maps published safely. Collections.synchronizedMap works, but serialises all access.

Q9. Can a Set contain two objects with the same hashCode but different equals()?

Short answer: Yes. Equal hash codes just put them in the same bucket. The set checks equals, finds them unequal, and stores both. That's a normal collision. Performance degrades if many elements collide (bucket chains, then trees), but correctness holds. The reverse (equal by equals, different hashCode) breaks the contract: you get "duplicates" in different buckets, and failed lookups.

Q10. Explain HashMap insertion and lookup with custom keys.

Short answer:

1. put(key, v) computes hash = key.hashCode() ^ (h >>> 16) (spreading the high bits), and the bucket index is hash & (n - 1).
2. It walks the bucket (a list, or a tree if treeified), comparing the stored hash first, then ==, then equals.
3. If a match is found, it replaces the value. Otherwise it appends a new node.
4. If the size exceeds capacity × load factor (0.75), it resizes.

get(key) repeats the same hash and equals walk. So custom keys must:

• override equals and hashCode consistently;
• use immutable fields (a changed key lands in the wrong bucket, and becomes unfindable);
• have a well-distributed hash;
• ideally be Comparable, which makes treeified buckets efficient.

Records satisfy the first three automatically.

Learn it in depth → HashMap Deep Dive

Q11. How can you use a custom object in a TreeMap without implementing Comparable?

Short answer: Pass a Comparator to the constructor. The map then uses compare(a, b) for all ordering and uniqueness:

TreeMap<Employee, Double> bonuses = new TreeMap<>(
        Comparator.comparing(Employee::department)
                  .thenComparing(Employee::lastName)
                  .thenComparing(Employee::id));        // a final tie-breaker, so distinct employees never compare as 0

Without either a comparator or Comparable, the first put throws ClassCastException.

Q12. How does contains() differ across List, Set and Map?

Short answer:

• List.contains(o): a linear scan with equals. O(n).
• HashSet.contains(o): a hash lookup (hash, then equals). O(1) on average.
• TreeSet.contains(o): a tree search using compareTo/compare. O(log n), and it can disagree with equals if the ordering is inconsistent with equals.
• Map.containsKey(k): the same as the corresponding set. containsValue(v) is O(n), because values aren't indexed.

Common trap: calling list.contains() inside a loop is O(n²). Convert to a HashSet first.

Q13. What happens if you modify an object after it's been inserted into a HashSet?

Short answer: If the modification changes fields used by hashCode/equals, the object stays in the bucket computed from its old hash. Then:

• contains(obj) usually returns false (it looks in the new bucket);
• remove(obj) fails, so the object is effectively leaked in the set;
• adding it again can create a duplicate.

Rule: elements of hash-based sets and keys of hash maps must be immutable, at least in the fields used by equals/hashCode. If you must change one, remove, modify, then re-add it.

Q14. What's the best collection for fast lookups with a predictable iteration order?

Short answer: LinkedHashMap/LinkedHashSet: O(1) average lookups, plus insertion order (or access order). If you need sorted order with range queries, use TreeMap/TreeSet (O(log n)). For enum keys, EnumMap/EnumSet (array-backed, and ordered by declaration). For concurrent access with sorted order, ConcurrentSkipListMap. For immutable data, Map.of/Set.of are fast, but their iteration order is deliberately unspecified, and randomised per JVM run.

Q15. What's the time complexity of contains() in ArrayList, HashSet and TreeSet?

Short answer:

• ArrayList: O(n) (a linear equals scan).
• HashSet: O(1) on average. The worst case is O(log n) within a treeified bucket (Java 8+), or O(n) if keys aren't comparable and all collide.
• TreeSet: O(log n) (a red-black tree search).

Constant factors matter too: for tiny collections (fewer than about 10 elements), a scan of an ArrayList can beat hashing.

Q16. How does HashMap resizing work, and what does it cost?

Short answer: When size > capacity × loadFactor (the default is 16 × 0.75 = 12), HashMap doubles the table (capacities are always powers of two) and redistributes the entries. Because the capacity doubles, each entry either stays at index i or moves to i + oldCapacity, decided by one extra hash bit. Java 8 splits each bucket into a "lo" and a "hi" list, preserving order, without rehashing every key.

The costs:

• O(n) work, and a latency spike, on the triggering put.
• Garbage from the old table.
• Repeated resizes while growing: doubling means only log(n) resizes, but each copies everything.
• Mitigation: pre-size it when you know the expected size: HashMap.newHashMap(expected) (Java 19+), or new HashMap<>((int) (expected / 0.75f) + 1).

Key points to cover:

• Buckets treeify into red-black trees when a chain exceeds 8 nodes and the table has at least 64 buckets. Otherwise the table resizes instead. They untreeify below 6.
• HashMap never shrinks.

Q17. What's the worst-case time complexity of HashMap.get(), and why?

Short answer: O(log n) in Java 8+, when many keys collide into one treeified bucket. Lookup inside a tree is logarithmic, and it works best when the keys are Comparable (otherwise it falls back to hash and identity tie-breaks, and may have to search both subtrees). Before Java 8, or with small tables where treeification doesn't apply, the worst case is O(n): a long linked chain. The average case is O(1), given a good hash and a load factor of 0.75.

Treeification was added partly to defend against hash-flooding DoS attacks, where an attacker sends many colliding keys (for example, HTTP parameter names).

Q18. When is LinkedList really better than ArrayList for frequent insertions and removals?

Short answer: Less often than textbooks say. LinkedList wins only when you insert or remove at a position you already hold (through a ListIterator) or at both ends. Even then, ArrayDeque is usually faster for head and tail operations.

• For middle inserts by index, LinkedList must first walk O(n) to the position.
• ArrayList pays an O(n) shift, but uses System.arraycopy, which is extremely fast and cache-friendly.

In benchmarks, ArrayList beats LinkedList for most real workloads, including many middle insertions of moderate size. Choose LinkedList only after measuring. Its memory overhead (about 40 bytes per node) also means more GC pressure.

Follow-up questions this topic invites — and their answers

Q: What's the default initial capacity of HashMap, and when is the table allocated? A: 16, with a load factor of 0.75. The table is allocated lazily, on the first put. new HashMap<>(n) rounds the capacity up to the next power of two.

Q: Why is HashMap's capacity always a power of two? A: So the bucket index can be computed with a fast bit mask (hash & (n - 1)) instead of %, and so resizing can split buckets into lo and hi halves using one bit. The hash spreading (h ^ h >>> 16) compensates for the mask only using the low bits.

Q: How do EnumMap and EnumSet work, and why are they fast? A: EnumSet is a bit vector (a single long for up to 64 constants). EnumMap is an array indexed by ordinal(). There's no hashing, operations are compact and fast, and they iterate in declaration order.

Q: What is IdentityHashMap for? A: A map that compares keys with == and System.identityHashCode, instead of equals and hashCode. It's used for graph traversal with visited sets, serialisation and deep-copy bookkeeping, and proxies, where object identity matters.