choosing a collection
a decision tree and a big-O cheat sheet.
- chapter
- chapter 06.12
- reading time
- 6 min read
start with the defaults: ArrayList, HashMap, HashSet, ArrayDeque. switch only when a question demands it: need order? LinkedHashMap / TreeMap. need the minimum? PriorityQueue. enum keys? EnumMap / EnumSet. shared between threads? the concurrent versions.
and almost never LinkedList, Vector, Stack or Hashtable.
the picture
you know how there's always a coworker who reaches for a TreeMap "because it's sorted" when nothing ever reads it in order? the collection you pick is a claim about how the data is used. pick by the questions you'll ask of it, not by the name that sounds most capable.
the questions, in the order that matters:
- values or key → value pairs? that's
CollectionvsMap. - will threads modify it concurrently? if yes, everything below has a different answer (see concurrent collections). wrapping in
Collections.synchronizedXworks for simple cases, but compound actions still need your own locking. - duplicates? no → a
Set. - what order do you need back? none → hash. insertion → linked hash. sorted or ranges → tree. by priority → heap.
- how do you take things out? by index →
ArrayList. from the ends →ArrayDeque. - does it change after you build it? no →
List.copyOf/Set.copyOf/Map.copyOf, and stop worrying about who modifies it.
the cheat sheet
| collection | get / lookup | add | remove | ordered by | inside |
|---|---|---|---|---|---|
ArrayList | get(i) O(1) | end: O(1)*, middle: O(n) | end: O(1), middle: O(n) | index | Object[] |
LinkedList | get(i) O(n) | ends: O(1) | ends: O(1) | index | nodes |
ArrayDeque | ends only, O(1) | ends: O(1)* | ends: O(1) | insertion | circular Object[] |
PriorityQueue | peek O(1) | O(log n) | poll O(log n) | priority (only the head) | heap in Object[] |
HashMap / HashSet | O(1) avg | O(1) avg* | O(1) avg | nothing | buckets |
LinkedHashMap / LinkedHashSet | O(1) avg | O(1) avg* | O(1) avg | insertion (or access) | buckets + list |
TreeMap / TreeSet | O(log n) | O(log n) | O(log n) | sorted | red-black tree |
EnumMap / EnumSet | O(1) | O(1) | O(1) | declaration | array / bits |
contains(x) on any list is O(n).
big-O hides constants, and the constants are mostly about memory: a flat array of references beats a web of node objects, because the CPU can prefetch an array and can't predict pointers. that's why ArrayList and ArrayDeque win so often even where the big-O ties.
what the big-O looks like in nanoseconds
rough numbers, same setup as the deque chapter: jdk 25.0.4 (temurin), apple M4 Pro, default G1 and heap, 100,000 Integers, System.nanoTime around whole loops after warmup rounds, median of 7, three runs agreeing within about 20%. not a JMH benchmark: treat these as orders of magnitude, not as the speed of your code.
get(key) on 100,000 entries.the gap that matters is the 400x between scanning and hashing, not the 3 to 5x between hashing and a tree. if you call list.contains inside a loop, that's the bug. if you're choosing between HashMap and TreeMap, choose by whether you need the order.
the ones to skip
| skip | why | use |
|---|---|---|
LinkedList | 24 bytes per element, O(n) indexing, cache-hostile | ArrayList or ArrayDeque |
Vector, Stack | every method synchronized, legacy since java 1.2 | ArrayList, ArrayDeque |
Hashtable | same story, and no nulls | HashMap or ConcurrentHashMap |
Collections.synchronizedList(...) for heavy concurrency | one lock for everything | the java.util.concurrent classes |
- defaults:
ArrayList,HashMap,HashSet,ArrayDeque. - need order? linked for insertion, tree for sorted, heap for "next best".
- enum keys or elements:
EnumMap,EnumSet. - threads modifying it: the
java.util.concurrentversions. - an O(n) call inside a loop beats any class choice for slowness. find it first.
- built once, never changed:
List.copyOfand friends.