Choosing the Right Collection: Performance and Trade-offs

Executive Summary

Choosing the right collection comes down to four questions: what is the access pattern, does order matter and in which of three senses, are the keys or elements enum-typed, and how big can the data get. ArrayList and HashMap remain the defaults because they win most real workloads. However, HashSet answers membership in O(1) where a List pays O(n), TreeSet and TreeMap deliver sorted order and range queries at O(log n), ArrayDeque serves both stacks and queues, and PriorityQueue serves urgency. Memory is the cost the Big-O tables hide: boxing primitives into collections costs roughly an order of magnitude more memory than arrays. Also, linked or tree structures pay a node object per element. Plain collections are not thread-safe; Part 5 swaps in the concurrent versions. Measure before optimizing beyond these tables, because the profiler, covered in Part 6, beats folklore in every argument it enters.

Choosing the Right Collection: Four Questions That Decide Everything

Every collection debate resolves into four questions, and the official framework overview organizes the same way. Ask them in order:

1. Access pattern: does the code read by position, look up by key, test membership, or process in order?
2. Ordering: does it need positional order, insertion order, or sorted order, or none at all?
3. Element types: are the elements or keys enums, which have their own specialized collections?
4. Scale and concurrency: how large does it grow, and does Part 5 put threads on the door?

The Master Table: Costs Across the Framework

One table prices the engines you have met. Numbers are the JDK’s documented behavior for typical sizes; the columns are the operations production actually runs:

So, read the table by workload, not by column. A hot membership loop wants the O(1) contains of HashSet or a HashMap key check. In contrast, a sorted report run once a day is often better served by sorting an ArrayList once than by paying TreeSet’s O(log n) on every operation; a work queue wants ArrayDeque’s constant ends. The collections overview trail documents the same contracts behind every entry.

The Decision Tree

 start: what does the code ask the data?
   |
   +-- "give me element at index i" ................. ArrayList
   |
   +-- "is X present?" (elements unique)
   |      +-- enum type? ............................ EnumSet
   |      +-- no order needed? ...................... HashSet
   |      +-- first-seen order? .................... LinkedHashSet
   |      +-- sorted iteration or ranges? ........... TreeSet
   |
   +-- "what is the value for key K?"
   |      +-- enum keys? ............................ EnumMap
   |      +-- sorted keys or range queries? ......... TreeMap
   |      +-- insertion order needed? ............... LinkedHashMap
   |      +-- none of those? ....................... HashMap
   |
   +-- "what do I handle next?"
          +-- FIFO or LIFO ......................... ArrayDeque
          +-- most urgent first? .................... PriorityQueue

 cross-cutting:
   fixed data at compile time ....... List.of, Set.of, Map.of
   threads share it .................. not these; Part 5 collections

That tree, plus the master table for tiebreaks, is the entire skill. The matrix below adds the “why” for the most common destinations:

Memory: The Cost the Tables Hide

However, Big-O describes time, and production incidents usually start in memory. The dominant factor is boxing: collections hold objects, so every primitive becomes a wrapper with a header and identity, while arrays from Part 1 store raw values:

// same million values, very different footprints
int[] primitive = new int[1_000_000];          // ~4 MB: 4 bytes each

List<Integer> boxed = new ArrayList<>();
for (int i = 0; i < 1_000_000; i++) {
    boxed.add(i);                             // ~20 MB or more:
}                                             // array slot + Integer object
                                              // per element, plus GC pressure

The exact ratio depends on the JVM and alignment. However, the rule holds: roughly five to six times the memory for boxed integers, and considerably more for linked structures, where every LinkedList or TreeMap element carries its own node object with pointers. Consequently, two production guidelines fall out directly. Hot paths over large primitive data use int[] or long[] arrays. Meanwhile, everything else uses collections without apology, because developer time is more expensive than memory until measured otherwise.

Ordering: Three Different Things Called “Ordered”

Reviews derail on one word more than any other: ordered. The framework offers three distinct guarantees, and code that asks for the wrong one reads correct and behaves wrong:

A report needing “the same order we received” wants insertion order, which ArrayList and the LinkedHash family provide. A leaderboard wants sorted order. A shopping cart wants positional. Half the collection bugs I have reviewed came from the author assuming one of these three while the implementation delivered another, most often by trusting HashSet iteration to be anything at all.

How Real Systems Do This

Mature codebases settle into a distribution worth knowing. Roughly 80 percent of fields are ArrayList or HashMap and are correct. After all, most data is positional or keyed, and the defaults win. Another 15 percent is specialized for a visible reason: EnumMap for day-of-week schedules, LinkedHashSet to keep first-seen order in dedup, TreeMap for time-range queries. The last 5 percent is exotic and profiler-mandated: primitive arrays, custom structures, or off-heap stores.

In fact, the 80 percent is not laziness; it is correct engineering. In my experience, the collections audit is the cheapest performance review that exists: read every List contains inside a loop, every HashMap growing without a bound, every HashSet keyed by classes without a proper equals. In three different codebases, one quarter of reviews, those three patterns were the only findings, and they were all one-line fixes.

Two doors open next. When Part 5 puts threads on your collections, the concurrent collections article replaces the engines with thread-safe versions, so the decisions in this article carry over intact. And when a collection-using service is slow despite correct choices, Part 6’s profiling article is the next step, because the answer is usually allocation rate or GC pressure, not the Big-O line you picked.

Decision Framework

The checklist version, for when requirements change under an existing choice:

1. Has the data outgrown the choice, or only folklore? Measure first; the interfaces lesson contracts rarely lie.
2. Is contains on a List running in a loop? Move to a Set-shaped structure, the most common one-line fix in Java.
3. Is sorted order needed continuously or once? Continuously: Tree types. Once: sort a List.
4. Are the keys enums? EnumMap, before any hash consideration.
5. Is the collection growing without a bound, like a cache? Add eviction or bounds now, not after the outage.
6. Will threads arrive? Plan the concurrent replacement, because the plain versions will not be upgraded retroactively under load.
7. Is primitive data large and hot? Arrays beat boxed collections until a profiler says otherwise.

When NOT to Use This

• Do not optimize a collection choice without a workload. For example, a TreeSet “for safety” on 30 elements adds ceremony and loses nothing; correctness and clarity outrank microseconds at small scale.
• Do not choose for concurrency prematurely. However, do not ignore a known requirement: plain collections under threads are a data race, and Part 5 has the exact replacements.
• Do not accept “we always use X here” as an answer. After all, the tables in this article cost nothing to consult, and habit is not a requirement.

Common Mistakes

• List contains inside a loop: the quadratic classic, and the first thing an experienced reviewer hunts for.
• Assuming HashSet or HashMap iteration order is stable: it is unspecified, can change between JDK versions, and breaks code that serializes or compares it.
• Boxing millions of primitives for a hot path: five times the memory plus garbage collector pressure, where an int[] is a drop-in.
• Paying TreeMap or TreeSet costs for a once-per-day sorted report that sort() would handle once.
• Using PriorityQueue as if it iterated sorted: only poll is ordered; the iterator walks the heap array.
• Choosing collections from folklore benchmarks rather than the workload, or worse, from a framework tutorial rather than the requirements.

Key Takeaways

• Four questions decide every collection: access pattern, which kind of order, enum-typed keys or elements, and scale plus concurrency.
• ArrayList and HashMap remain correct defaults for most data; specialization starts with a workload, not a preference.
• Set-shaped structures answer contains in O(1). In fact, the List contains loop is the most common and most fixable Java performance bug.
• Three kinds of ordered exist: positional, insertion, and sorted. In fact, naming the right one ends half of all collection debates.
• Boxing primitives costs roughly five to six times the memory; large hot data belongs in arrays.
• Enum keys and elements deserve EnumMap and EnumSet before any hash-based option.
• Thread-safety is a Part 5 question with a Part 5 answer; plan it, and swap the engines, not the design.

FAQ

Which Java collection should I use by default?

ArrayList for positional data, HashMap for keyed data, HashSet for uniqueness and membership, ArrayDeque for stacks and queues. Those four cover most production code, and the other implementations exist for visible, specific reasons.

Is ArrayList faster than LinkedList in Java?

In most real workloads, yes. LinkedList’s O(1) insertion needs an O(n) walk to the position and pays a node object per element; ArrayList’s compact array and O(1) random access win unless a profiler proves otherwise.

How much more memory do boxed collections use?

Roughly five to six times the raw array footprint for List<Integer> versus int[], because each element becomes a slot plus an Integer object. Linked and tree structures add a node per element on top of that.

When should I use TreeMap instead of sorting a List?

When sorted order and range queries are needed continuously, because TreeMap maintains them on every operation. For a one-off sorted report, collect into a List and sort it once.

Are Java collections thread-safe?

The plain versions are not. Sharing them across threads causes data races and lost updates; Part 5 introduces the concurrent collections, and the collection choice you make with this article carries over.

Conclusion

Choosing a collection is now a lookup instead of an opinion: one master table for cost, one tree for the decision, and three cross-cutting factors, memory, ordering kind, and concurrency, that the tables hide. The defaults are usually right, and the exceptions now announce themselves.

The next article asks the question underneath every List<String> and Map<String, Integer> you have written: how does the compiler enforce those element types? Generics make the collections you just learned safe, and the next article makes generics make sense.

Pick for the workload, not the habit. The tables are free, and the profiler is final.

Last updated on 2 September 2026.