Collections Framework
Choosing the Right Collection
A decision guide: match the collection to the questions your code asks. Default to
ArrayList, HashMap, HashSet, ArrayDeque — and deviate only for ordering, navigation, priorities, enums, or concurrency.- Ask: duplicates? ordering? key-lookup? both-ends access? priority? concurrent?
- Defaults:
ArrayList/HashMap/HashSet/ArrayDeque - Need sorted iteration or nearest-key queries →
TreeMap/TreeSet - Need insertion order remembered →
LinkedHashMap/LinkedHashSet - Enum keys/elements →
EnumMap/EnumSet, always - Multithreaded → Concurrent Collections, never
synchronizedXwrappers by reflex
| You need… | Reach for | Why |
|---|---|---|
| Indexed access, a sequence | ArrayList | contiguous, cache-friendly, O(1) get — see Lists |
| Stack or FIFO queue | ArrayDeque | circular array; beats Stack & LinkedList — Queues Deques |
| Dedup, don't care about order | HashSet | O(1) contains — see Sets |
| Dedup, keep insertion order | LinkedHashSet | hash speed + stable iteration order |
| Key → value lookup | HashMap | O(1) get/put — see Maps |
| Sorted iteration, range/nearest-key queries | TreeMap / TreeSet | red-black tree, NavigableXxx API — Sorted Collections |
| Deterministic iteration order, no sorting needed | LinkedHashMap / LinkedHashSet | linked entries preserve insertion order |
| LRU cache | LinkedHashMap in access-order mode + removeEldestEntry | access reorders to most-recent; the hook evicts the eldest past capacity |
| Priority / always-process-min | PriorityQueue | binary heap, poll is O(log n) |
| Enum keys / elements | EnumMap / EnumSet | array/bit-vector speed (EJ 36–37) — Enums |
| Shared across threads | ConcurrentHashMap, CopyOnWriteArrayList, blocking queues | see Concurrent Collections |
The performance literature's framing: choose by access pattern first, asymptotics second, constants third. An O(1) structure with terrible cache behavior can lose to an O(n) scan for small n — and most collections are small. Measure before optimizing (Performance Methodology); but don't write the accidental O(n²) either.
// Known size → presize (avoids regrowth copies and rehashing):
List<Row> rows = new ArrayList<>(rowCount);
Map<String, User> byId = HashMap.newHashMap(userCount); // Java 19+
// Fixed reference data → immutable factories:
static final Set<String> VOWELS = Set.of("a", "e", "i", "o", "u");