Java Collections — Senior Interview Field Reference

The interview question underneath every other question in this guide: what is the actual data structure, and what does that structure guarantee?

Collection extends Iterable and is the root for List, Set, and Queue. Map deliberately does not extend Collection — it operates on key-value pairs, not single elements, so its API shape (get(key), put(key, value), entrySet()) doesn't fit the Collection contract. This is a favorite "do you actually understand the framework, or just the API" opener.

flowchart TD
  IT["Iterable"] --> COL["Collection"]
  COL --> LIST["List\n(ArrayList, LinkedList, Vector)"]
  COL --> SET["Set\n(HashSet, LinkedHashSet, TreeSet)"]
  COL --> QUEUE["Queue\n(PriorityQueue)"]
  QUEUE --> DEQUE["Deque\n(ArrayDeque, LinkedList)"]
  SET --> SORTEDSET["SortedSet"]
  SORTEDSET --> NAVSET["NavigableSet\n(TreeSet)"]
  MAP["Map — NOT a Collection"] --> SORTEDMAP["SortedMap"]
  SORTEDMAP --> NAVMAP["NavigableMap\n(TreeMap)"]
  MAP --> HASHMAP["HashMap, LinkedHashMap"]

Fail-fast vs. fail-safe iterators

Most non-concurrent collections (ArrayList, HashMap, HashSet…) track a modCount field, incremented on every structural modification. Their iterators capture modCount at creation and check it on every next()/remove() call — a mismatch throws ConcurrentModificationException (CME). This is a best-effort detection mechanism, not a guarantee: the JDK explicitly warns against relying on it for correctness.

Concurrent collections (ConcurrentHashMap, CopyOnWriteArrayList) use weakly consistent iterators instead — they never throw CME, but may or may not reflect mutations that happen during iteration. Trading a hard failure for possibly-stale data is a deliberate, and frequently interviewed, design choice.

Why "just use ArrayList" is the correct default almost every time, and what you give up with the alternatives.

ArrayListBacked by a plain Object[]

Starts as a shared empty array (no allocation until the first add()), then grows to a default capacity of 10. Growth after that is 1.5×, not doubling: newCapacity = oldCapacity + (oldCapacity >> 1). Each grow is a full System.arraycopy to a new backing array — amortized O(1) for add(end), but a real O(n) pause the moment it happens. get(index) is true O(1) (pointer arithmetic into a contiguous array); add/remove at an arbitrary index is O(n) because everything after the index has to shift.

LinkedListA doubly-linked list — and usually the wrong choice

LinkedList gives O(1) insert/remove once you're already at the node, but get(index) is O(n), and getting to an arbitrary position is itself O(n) (it does optimize by walking from whichever end is closer). Each element costs a separate heap-allocated node object with two pointers — far worse cache locality than a contiguous array. In practice, ArrayList or ArrayDeque (§07) beats LinkedList for nearly every real workload, including ones that sound like a textbook case for it. Its main remaining honest use is implementing Deque — and even there, ArrayDeque is usually faster.

CopyOnWriteArrayListCopy the whole array, every write

Every mutating call (add, set, remove) copies the entire backing array under a lock; reads and iteration need no locking at all and never throw CME because the iterator holds a private snapshot reference to the array at creation time. That snapshot can go stale immediately after a concurrent write — correct behavior for its intended niche (small, read-dominated, rarely-mutated collections like listener lists), and a performance disaster for anything write-heavy.

The single most interviewed data structure in the JDK. Interviewers are listening for treeification, hash spreading, and resize behavior — not just "O(1) average case."

Backed by Node<K,V>[] table — an array of buckets, default capacity 16, default load factor 0.75 (resize triggers once size > capacity × loadFactor). Capacity is always a power of two, which lets the bucket index be computed with a bitmask instead of a modulo: index = (n - 1) & hash.

Why the hash gets XOR-folded before use

Because indexing only uses the low bits of the hash (a bitmask against a small power-of-two capacity), a hashCode() with poor entropy in its low bits would collide far more than it should. HashMap spreads the high bits down into the low bits first: h ^ (h >>> 16).

flowchart LR
  H["key.hashCode()"] --> S["h ^ (h >>> 16)\n(spread high bits into low bits)"]
  S --> IDX["index = (n - 1) & hash"]
  IDX --> B0["Bucket 0: empty"]
  IDX --> B1["Bucket 1: Node -> Node -> Node"]
  IDX --> B2["Bucket 2: Red-Black Tree\n(8+ collisions, capacity >= 64)"]

// java.util.HashMap, condensed
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

// bucket index — capacity n is always a power of two,
// so (n - 1) & hash replaces the slower modulo n
int index = (n - 1) & hash(key);

Collision handling: linked list, then red-black tree

Each bucket starts as a linked list of colliding nodes. Since Java 8, a bucket that accumulates TREEIFY_THRESHOLD = 8 nodes converts to a red-black tree — but only if the table capacity is also at least MIN_TREEIFY_CAPACITY = 64; below that, HashMap resizes instead, since a small table with one overloaded bucket usually just needs more buckets. Treeified bins revert to a list once they shrink to UNTREEIFY_THRESHOLD = 6 nodes during a split. This defends against a real attack class — an adversary feeding keys engineered to collide can otherwise degrade every lookup to O(n); treeification caps the worst case at O(log n).

Resize: doubling, not a full rehash from scratch

When the map resizes, capacity doubles and the table is rebuilt — but Java 8+ avoids recomputing every hash. Because capacity is always a power of two, doubling adds exactly one new bit to the mask; each old bucket splits into a "low" list (same index in the new table) and a "high" list (old index + old capacity), decided by that single new bit. This also preserves relative order within each split — the earlier (Java 7) resize algorithm rebuilt buckets by prepending, which could silently reverse order and, notoriously, form a cycle if two threads resized the same map concurrently (the classic "HashMap spins CPU to 100% forever" production bug). Java 8's split-based resize doesn't create that cycle — but concurrent mutation of a plain HashMap is still undefined behavior, just a different failure mode.

flowchart TD
  A["size > threshold\n(capacity * loadFactor)"] --> B["Double capacity\nnewCap = oldCap << 1"]
  B --> C["For each old bucket,\nsplit using the new high bit"]
  C --> D["lo list: same index\nin the new table"]
  C --> E["hi list: index + oldCapacity"]
  D --> F["Order preserved within each split\n(Java 8+, no rehash-cycle risk)"]
  E --> F

// Default capacity 16 — this resizes (and fully rehashes) 4 times
// on the way to holding 10,000 entries.
Map<String, Long> counts = new HashMap<>();

// Size for the known load up front — zero resizes.
Map<String, Long> counts = new HashMap<>((int) (10_000 / 0.75f) + 1);

The contract every hash-based collection depends on, and what happens the instant you violate it.

The contract: if a.equals(b) is true, a.hashCode() == b.hashCode() must also be true. The reverse isn't required — two unequal objects are allowed to share a hash code (a collision), which is exactly why buckets hold more than one entry. Break the forward direction and hash-based lookup silently stops working, with no exception anywhere near the bug.

The classic version: mutating a field used in hashCode() after insertion

A HashMap/HashSet computes an object's bucket once, at insertion time, from its hash code at that moment. If a field that feeds hashCode() changes afterward, the object is still physically sitting in its original bucket — but any future lookup recomputes the hash and looks in a different bucket. The object isn't gone; it's unreachable by key.

Set<Point> points = new HashSet<>();
Point p = new Point(1, 1);
points.add(p);

p.x = 99;                    // mutate a field used in hashCode()

points.contains(p);          // false! looks in the NEW bucket — object sits in the OLD one
points.remove(p);            // false too, same reason — p is now unremovable except via iterator
for (Point q : points) {
    System.out.println(q);   // p is still there — just permanently "lost" to lookups
}

IdentityHashMap is the deliberate escape hatch: it uses reference identity (==, effectively System.identityHashCode) instead of equals()/hashCode(), which is exactly right for cycle detection or identity-keyed memoization — and exactly wrong as a general-purpose map, since it silently breaks the usual "equal objects are interchangeable as keys" assumption.

HashMap's bucket array, threaded with a doubly-linked list for predictable iteration order — and the basis of the single most common "design a cache" interview question.

LinkedHashMap maintains either insertion order (default) or access order (constructor flag) via an auxiliary doubly-linked list running through the same entries the underlying HashMap already stores. The cost is a small, constant per-entry overhead for the two extra pointers — asymptotic complexity for get/put is unchanged from HashMap.

In access-order mode, every get() moves the touched entry to the tail of the list. Override the protected removeEldestEntry() hook and you have a working LRU cache in about ten lines — this is the expected answer to "implement an LRU cache" at the senior level, and interviewers will follow up asking you to make it thread-safe (wrap access in a lock, or reach for Caffeine in real production code).

flowchart LR
  P["put(key, value)"] --> LL["Append to access-order\ndoubly-linked list"]
  LL --> CHK["afterNodeInsertion()\ncalls removeEldestEntry()"]
  CHK -- "size() > MAX_ENTRIES" --> EVICT["Remove list head\n(least recently used)"]
  CHK -- "false" --> DONE["No eviction"]
  G["get(key)"] --> MOVE["accessOrder=true:\nmove node to tail"]

class LruCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxEntries;

    LruCache(int maxEntries) {
        super(16, 0.75f, true);   // accessOrder = true
        this.maxEntries = maxEntries;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxEntries;
    }
}

Trade O(1) average-case lookup for O(log n) guaranteed, and get sorted order plus range queries in exchange.

TreeMap is backed by a red-black tree — a self-balancing binary search tree that guarantees O(log n) for get, put, remove, and containsKey, worst case, not just average case. Keys need either a natural ordering (Comparable) or an explicit Comparator supplied at construction; comparing two mutually incompatible types throws ClassCastException at the point of insertion, not at compile time.

The payoff for giving up constant-time lookup is the NavigableMap/NavigableSet API: floorKey/ceilingKey/higherKey/lowerKey for nearest-match queries, firstKey/lastKey, and headMap/tailMap/subMap range views — mutations through those views write back to the original map. HashMap has no equivalent; if a question needs "give me everything between X and Y" or "the next key after this one," that's a TreeMap question in disguise.

The producer-consumer and scheduling half of the framework — where BlockingQueue questions live.

Queue ships two parallel method families: offer/poll/peek return a sentinel (false/null) on failure, while add/remove/element throw. Knowing which pair you're using — and why a library method picked one over the other — comes up constantly in code review as much as interviews.

ArrayDequeThe default for both stacks and queues

A resizable circular array, O(1) amortized push/pop/offer/poll at both ends, better cache locality and lower per-element overhead than LinkedList. It deliberately disallows null elements — null is used internally as the "empty slot" sentinel. Prefer it over LinkedList, Stack, and Vector for essentially every stack/queue use case.

PriorityQueueA binary heap, not a sorted list

Array-backed binary min-heap: O(log n) offer/poll, O(1) peek at the minimum. Iterating a PriorityQueue does not yield sorted order — only the root is guaranteed to be the minimum; the rest of the backing array just satisfies the heap invariant. Only repeated poll() produces sorted output. This exact gap is a favorite trick question.

PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 3));

pq.forEach(System.out::println);              // 1, 5, 3 — raw heap-array order
while (!pq.isEmpty()) System.out.println(pq.poll());   // 1, 3, 5 — poll() IS sorted

BlockingQueue family

sequenceDiagram
  participant P as Producer thread
  participant Q as BlockingQueue
  participant C as Consumer thread

  P->>Q: put(item) — blocks if full
  C->>Q: take() — blocks if empty
  Q-->>C: item
  Note over P,C: ArrayBlockingQueue: one lock, two conditions (notFull/notEmpty)\nLinkedBlockingQueue: two locks (putLock/takeLock) for higher throughput

Where "just synchronize it" and "use the concurrent version" actually diverge — the question behind every ConcurrentHashMap deep-dive.

ConcurrentHashMapLock-free reads, per-bin locking on write

Java 8 rewrote ConcurrentHashMap away from the earlier 16-way segment locking toward much finer granularity: inserting into an empty bin uses a CAS (no lock at all), and inserting into a bin that already has a node briefly synchronizeds on just that bin's first node — every other bin in the table stays fully available. get() takes no lock whatsoever; Node.val and Node.next are volatile, so reads are always visibility-safe without synchronization. Bins treeify under the same TREEIFY_THRESHOLD/MIN_TREEIFY_CAPACITY rules as HashMap (§03).

flowchart TD
  A["putVal(key, value)"] --> B{"Bin empty?"}
  B -- yes --> C["CAS install new node\n(no lock needed)"]
  B -- no --> D["synchronized on\nthe bin's first node only"]
  D --> E["Traverse / append / replace\nwithin this bin"]
  E --> F{"Bin size >= 8 and\ntable capacity >= 64?"}
  F -- yes --> G["Treeify this bin"]
  F -- no --> H["Stay as linked list"]

size() is not an exact atomic snapshot — under concurrent writes it's a best-effort estimate assembled from striped counters (conceptually similar to LongAdder), traded deliberately for not having to serialize every write through a single counter. Like HashMap, null keys and null values are both disallowed — a null return from get() would otherwise be ambiguous between "absent" and "present but null" with no way to atomically disambiguate under concurrent access.

ConcurrentHashMap<String, List<String>> index = new ConcurrentHashMap<>();

// atomic "get or create" — no external locking, no lost-update race
index.computeIfAbsent(key, k -> new CopyOnWriteArrayList<>()).add(value);

ConcurrentSkipListMap / ConcurrentSkipListSet

The concurrent answer to "I need TreeMap, but from multiple threads." Backed by a skip list — a probabilistically balanced, lock-free-for-reads structure with fine-grained locking on writes — giving O(log n) operations and sorted iteration under concurrent access. TreeMap itself has no thread-safe counterpart; Collections.synchronizedSortedMap(new TreeMap<>()) works but serializes every access behind one lock.

The tables interviewers are quizzing you against, in one place.

List implementations

Map implementations

Set implementations

"Unmodifiable" and "immutable" are not the same word in the JDK, and the gap between them is a real bug class.

Collections.unmodifiableList/Map/Set return a view, not a copy — they only block mutation attempts made through the wrapper. The underlying collection is completely unprotected, and any change to it is immediately visible through the "unmodifiable" view.

List<String> mutable = new ArrayList<>(List.of("a", "b"));
List<String> view = Collections.unmodifiableList(mutable);

mutable.add("c");            // allowed — mutating the ORIGINAL list
view.get(2);                 // "c" — the "unmodifiable" view just changed underneath you
view.add("d");                // throws UnsupportedOperationException

List.of/Map.of/Set.of (Java 9+) are genuinely immutable: fixed at creation, reject null elements with an NPE, and throw UnsupportedOperationException on any mutation attempt with no backing collection to reach around. Map.of only has direct overloads up to 10 entries; beyond that, use Map.ofEntries. Collectors.toUnmodifiableList/Set/Map (Java 10+) give you the same guarantee coming out of a stream — don't rely on the plain Collectors.toList() result being mutable or immutable, since the JDK doesn't specify which, only that it currently happens to return an ArrayList.

Every trap from the sections above, grouped by category. Skim before a system-design or coding-round interview.

List<String> fixed = Arrays.asList("a", "b", "c");
fixed.set(0, "z");            // OK — writes through to the backing array
fixed.add("d");                // throws UnsupportedOperationException — fixed-size

List<Integer> nums = new ArrayList<>(List.of(10, 20, 30));
nums.remove(1);                        // removes by INDEX -> [10, 30]
nums.remove(Integer.valueOf(1));       // removes by VALUE -> no-op, 1 isn't in the list

Primary sources worth reading directly for anything this page compresses.

• Effective Java, 3rd Edition — Items 10–11 (equals/hashCode), 17 (immutability), 28 (lists vs. arrays), 52 (interfaces over implementations), 78–84 (concurrency)Joshua Bloch
• java.util.HashMap source & class-level Javadoc (treeification, resize, hash spreading)OpenJDK
• java.util.concurrent.ConcurrentHashMap source & class-level JavadocOpenJDK
• JEP 180: Handle Frequent HashMap Collisions with Balanced TreesOpenJDK
• The Java Tutorials — Collections Framework OverviewOracle