Choosing the right collection

For this lesson, we'll focus on a decision guide you can use in interviews and production: key lookup, membership, uniqueness, index access, insertion order, sorted order, FIFO, LIFO, priority, reference identity and thread safety. We'll use the Module 3 defaults (ArrayList, HashMap, HashSet, ArrayDeque) and show exactly when to move off them.

01Picture it first: a routing table, not a family tree

Picture a call-routing menu. The first question is not "which class do you like?". It is "what must this code do most often?" After that, the answer narrows quickly: key lookup, membership, ordering, indexing, end operations, priority or concurrency.

Use this flowchart when an interviewer gives you a scenario. You can draw it in 45 seconds, then talk through trade-offs.

Fig. 1

A decision flowchart starts with the operation that must be fast and routes to HashMap for key lookup, HashSet or LinkedHashSet for membership and uniqueness, ArrayList for index access, ArrayDeque for FIFO or LIFO, PriorityQueue for priority, TreeMap or TreeSet for sorted navigation, and concurrent collections for shared mutation

The flowchart is deliberately biased toward defaults. Start with ArrayList, HashMap, HashSet and ArrayDeque. Move away only when the requirement says to.

02Start with the operation under the hood

Notice the pattern. Hash structures buy expected O(1) by giving up sorted order. Tree structures buy sorted navigation for O(log n). Linked variants add iteration order to hash tables for a few extra pointers per entry.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class FastOperations {
    record Book(String isbn, String title) {}

    public static void main(String[] args) {
        Map<String, Book> byIsbn = new HashMap<>();
        byIsbn.put("978-0134685991", new Book("978-0134685991", "Effective Java"));
        System.out.println(byIsbn.get("978-0134685991").title());

        Set<String> seenRequestIds = new HashSet<>();
        if (seenRequestIds.add("req-17")) {
            System.out.println("process once");
        }
    }
}

This is the cleanest interview answer: name the operation, name the interface, name the implementation, then give the cost. You do not need to recite every collection class.

03The default four, and when to leave them

ArrayList for lists

Use ArrayList when you need ordered data, index access or append-heavy collection building. A no-arg ArrayList allocates its backing array lazily and grows by about 1.5x, so appending is amortised O(1). Reads by index are O(1).

Move off ArrayList when the requirement is not really "a list". If you only need membership, use a set. If you remove from the front repeatedly, use ArrayDeque. If multiple threads read while rare writes update a listener list, consider CopyOnWriteArrayList, knowing that every write copies the array.

HashMap for key lookup

Use HashMap for a business key to value lookup: user ID to user, ISBN to book, SKU to stock count. It gives expected O(1) lookup and update with a good hashCode. We cover the internal table, load factor and tree bins in How HashMap works.

Move off HashMap when you need a guarantee it does not give. Insertion order means LinkedHashMap; sorted keys and range queries mean TreeMap; enum keys mean EnumMap; shared updates mean ConcurrentHashMap; reference identity means IdentityHashMap.

HashSet for membership and uniqueness

Use HashSet for "have I seen this?" and "keep one of each". Set.add returning false is a useful first-time-seen check. HashSet is backed by a HashMap, so the same equality and hashing caveats apply.

Move off HashSet when order is part of the output. First-seen order means LinkedHashSet; sorted unique values mean TreeSet; a fixed set of enum constants means EnumSet.

ArrayDeque for ends

Use ArrayDeque for stack and queue operations in one thread: addLast/removeFirst for FIFO, push/pop for LIFO. It is resizable-array backed, avoids per-node allocation, and does not carry the legacy Vector API that Stack inherits.

Move off ArrayDeque when the queue is a concurrency boundary. A producer-consumer problem with waiting on empty or full queues wants BlockingQueue, such as ArrayBlockingQueue for bounded capacity or LinkedBlockingQueue when configured with a bound. A priority scheduler wants PriorityQueue or PriorityBlockingQueue, not FIFO.

04Worked scenarios interviewers actually ask

These are phrased like scenario questions because that is how they show up. The nuance is where candidates win or lose points.

FIFO jobs: ArrayDeque, not LinkedList

import java.util.ArrayDeque;
import java.util.Deque;

public class FifoJobs {
    public static void main(String[] args) {
        Deque<String> jobs = new ArrayDeque<>();
        jobs.addLast("email");
        jobs.addLast("invoice");

        while (!jobs.isEmpty()) {
            System.out.println(jobs.removeFirst());
        }
    }
}

Use ArrayDeque. Many multiple-choice questions list LinkedList as the expected FIFO answer because it implements Queue, but in modern Java I want you to say the better default. LinkedList allocates a node per element and pointer-chases through memory; ArrayDeque keeps references in a circular array and is the usual in-memory queue choice.

If producers and consumers run on different threads and must wait, the answer changes to BlockingQueue. That is a different requirement, not a different opinion.

Fixed enum roles: EnumSet

If roles are a closed enum such as ADMIN, USER, AUDITOR and GUEST, use EnumSet<Role>. It is compact because it represents membership with bits based on enum ordinal, and it is type-safe because it cannot contain a role from another enum.

import java.util.EnumSet;

public class RolesExample {
    enum Role { ADMIN, USER, AUDITOR, GUEST }

    public static void main(String[] args) {
        EnumSet<Role> staff = EnumSet.of(Role.USER, Role.AUDITOR);
        System.out.println(staff.contains(Role.ADMIN)); // false
        staff.add(Role.ADMIN);
        System.out.println(staff); // [ADMIN, USER, AUDITOR]
    }
}

Use HashSet only when the values are not enum constants or the domain is open-ended. For enum-keyed maps, the sibling answer is EnumMap<Role, Permission>.

Sign-up order plus uniqueness: LinkedHashSet

If you need user IDs in the order they signed up and no duplicate IDs, use LinkedHashSet. ArrayList preserves order but permits duplicates. HashSet enforces uniqueness but does not promise iteration order.

import java.util.LinkedHashSet;
import java.util.Set;

public class SignupOrder {
    public static void main(String[] args) {
        Set<String> signups = new LinkedHashSet<>();
        signups.add("u3");
        signups.add("u1");
        signups.add("u3");
        signups.add("u2");
        System.out.println(signups); // [u3, u1, u2]
    }
}

This is also the right answer for "deduplicate while preserving first appearance". In Java 21, LinkedHashSet is a SequencedSet, so it also gives you first, last and reversed views.

Nearest higher or lower price: TreeMap through NavigableMap

For a stock or marketplace price ladder where you need the closest price above or below a target, use NavigableMap, usually implemented by TreeMap. HashMap can find an exact key, but it has no concept of nearest key.

import java.util.NavigableMap;
import java.util.TreeMap;

public class PriceLadder {
    public static void main(String[] args) {
        NavigableMap<Integer, String> byPrice = new TreeMap<>();
        byPrice.put(100, "basic");
        byPrice.put(150, "plus");
        byPrice.put(250, "pro");

        System.out.println(byPrice.floorEntry(180));   // 150=plus
        System.out.println(byPrice.ceilingEntry(180)); // 250=pro
    }
}

Say NavigableMap in the interface and TreeMap as the implementation. That tells the interviewer you know the operation (floorEntry, ceilingEntry) and the engine (red-black tree, O(log n)).

Reference-equality keys: IdentityHashMap

If two different objects that happen to be equals() must remain different keys, use IdentityHashMap. It compares keys with == and hashes them with System.identityHashCode, which is useful for object graph traversal, serialization handles, proxy maps and cycle detection.

import java.util.IdentityHashMap;
import java.util.Map;

public class IdentityKeys {
    public static void main(String[] args) {
        String a = new String("tenant");
        String b = new String("tenant");

        Map<String, Integer> counts = new IdentityHashMap<>();
        counts.put(a, 1);
        counts.put(b, 2);

        System.out.println(a.equals(b)); // true
        System.out.println(a == b);      // false
        System.out.println(counts.size()); // 2
    }
}

Do not use this for normal domain lookup. Most business keys want value equality, so HashMap is the right answer. IdentityHashMap is a specialist tool.

05Order is not one thing

The word "ordered" is overloaded. In interviews, make the interviewer choose the kind of order.

A PriorityQueue is the easiest trap. It is not a sorted list. peek() and poll() see the highest-priority item according to the comparator, but iterating the queue walks the heap array in heap order, not sorted order.

06Thread safety changes the answer

Thread safety is not a decoration you add at the end. It changes the collection and sometimes the whole algorithm.

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

public class SharedCounters {
    public static void main(String[] args) {
        ConcurrentMap<String, Integer> hits = new ConcurrentHashMap<>();
        hits.merge("/home", 1, Integer::sum);
        hits.merge("/home", 1, Integer::sum);
        System.out.println(hits.get("/home")); // 2
    }
}

The broken version is get, add one, then put. That is three operations and two threads can interleave. Use merge, compute or putIfAbsent when the compound action is per key.

07More scenario answers in one table

Use this table as interview practice. Each answer starts with the collection, then the reason and the caveat.

One subtle row is the playlist. LinkedList only wins when you already hold the node position as a ListIterator, then insertion or removal there is O(1). If you start from an index each time, it still walks O(n), and ArrayList often wins in practice because shifting a contiguous array is cache-friendly.

08Advanced: asking better requirement questions

When a prompt says "fast", ask "fast for which operation?" A collection cannot optimize everything at once. Hash tables optimize equality lookup. Trees optimize ordered navigation. Arrays optimize index access and compact iteration. Queues optimize removal policy.

Here are the follow-up questions I ask before committing:

1. Do I need exact lookup or nearest lookup? Exact goes hash. Nearest goes tree.
2. Is order part of correctness or only presentation? Presentation can sort a copy at the edge.
3. Can duplicates exist? If not, use a set or a map key.
4. Is equality value-based, enum-based or reference-based? That selects HashMap, EnumMap or IdentityHashMap.
5. Who mutates it? One thread, many threads, or nobody after construction.
6. Is the size bounded? Unbounded maps and queues become memory bugs.
7. Do I need to remove arbitrary elements or only ends/top? That separates list, deque and heap.

A compact chooser in code

You can encode the reasoning as comments next to your fields. It sounds small, but it prevents future maintainers from "simplifying" the collection into the wrong one.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.NavigableMap;
import java.util.TreeMap;

public class OrderBookState {
    private final Map<String, Integer> quantityBySku = new HashMap<>();
    private final LinkedHashSet<String> signupOrder = new LinkedHashSet<>();
    private final NavigableMap<Integer, String> priceBands = new TreeMap<>();
    private final Deque<String> retryQueue = new ArrayDeque<>();

    void recordSignup(String userId) {
        signupOrder.add(userId); // unique, first-seen order
    }

    String nearestHigherBand(int price) {
        Map.Entry<Integer, String> entry = priceBands.ceilingEntry(price);
        return entry == null ? null : entry.getValue();
    }
}

The field type communicates the contract. NavigableMap says callers may rely on navigation. LinkedHashSet says both uniqueness and insertion order matter. That is better than declaring everything as concrete types by habit.

When the default is wrong

The default four are strong, but they are not magic.

09How to say it in the interview

When I ask "which collection would you use?", I'm listening for a decision process. A strong candidate starts with the dominant operation, names the interface, names the implementation, gives the complexity, and then states the condition that would change the answer.

Start with the hot operation
key lookup       -> HashMap
membership       -> HashSet
index access     -> ArrayList
FIFO / LIFO      -> ArrayDeque
insertion order  -> LinkedHashMap / LinkedHashSet
access order     -> LinkedHashMap(..., true)
sorted / nearest -> TreeMap / TreeSet (Navigable*)
priority removal -> PriorityQueue, poll is ordered, iteration is not
enum domain      -> EnumSet / EnumMap
reference keys   -> IdentityHashMap
shared updates   -> ConcurrentHashMap, BlockingQueue, COW list or explicit lock
defaults: ArrayList, HashMap, HashSet, ArrayDeque
move only when a requirement forces it