Skip to content
Tutorials Center
My learning

Topics

Lesson 94 of 201 ยท Collections

Choosing the Right Collection

Pick the right Java collection every time with a step-by-step decision guide, a Big-O table for common operations, memory notes and simple timing with System.nanoTime.

You now know a lot of collection classes: lists, sets, maps, queues, deques, sorted and linked variants, specialized and concurrent ones. Picking between them is a design decision that affects correctness (can there be duplicates? does order matter?) and performance (is contains instant or does it scan a million elements?). A wrong choice often works fine with ten test items and becomes painfully slow in production with a hundred thousand.

This lesson turns everything from the Collections chapter into a practical guide: a few questions that lead you to the right interface and class, a Big-O table for the operations you call most, notes on memory use, and a way to check your choice by measuring with System.nanoTime.

Start with the question your code asks

Choose the interface first, by asking what your code needs to do with the data. The implementation comes second.

  1. Do you look things up by a key? ("price of product SKU-77", "user with id 42") โ†’ a Map.
  2. Do you need uniqueness or fast "is it in there?" checks? ("has this email been seen?") โ†’ a Set.
  3. Do you process items in a particular order of arrival? First in, first out โ†’ Queue; last in, first out โ†’ Deque used as a stack; most important first โ†’ PriorityQueue.
  4. Otherwise, do you just keep items in order and access them by position? โ†’ a List.

Then pick the implementation by ordering and special needs:

You need Map Set List / Queue
No particular order (fastest) HashMap HashSet ArrayList
Insertion order LinkedHashMap LinkedHashSet ArrayList keeps it anyway
Sorted order, ranges, nearest key TreeMap TreeSet sort an ArrayList, or PriorityQueue
Keys are enum constants EnumMap EnumSet
Fixed data that never changes Map.of / Map.copyOf Set.of List.of
Both ends (queue, stack, sliding window) ArrayDeque
Shared between threads ConcurrentHashMap ConcurrentHashMap.newKeySet() CopyOnWriteArrayList, BlockingQueue

The everyday defaults: ArrayList, HashMap, HashSet and ArrayDeque. Start there unless you have a concrete reason not to, and declare variables with the interface type (List<String> names = new ArrayList<>();) so switching later is a one-line change.

Big-O for common operations

Big-O notation describes how the cost of an operation grows with the number of elements, n. O(1) means the cost stays about the same no matter how big the collection gets; O(log n) grows very slowly (a million elements need about 20 steps); O(n) grows in proportion to the size.

Class add get by index contains / get by key remove Notes
ArrayList O(1)* at end, O(n) in middle O(1) O(n) O(n) (shifts elements) *amortized: occasionally copies the array
LinkedList O(1) at ends O(n) O(n) O(1) at ends or via iterator poor cache locality
ArrayDeque O(1)* at either end โ€” O(n) O(1) at ends best queue and stack
HashMap / HashSet O(1) average โ€” O(1) average O(1) average needs good hashCode/equals
LinkedHashMap / LinkedHashSet O(1) average โ€” O(1) average O(1) average slightly more memory
TreeMap / TreeSet O(log n) โ€” O(log n) O(log n) sorted; floor, ceiling, ranges
PriorityQueue O(log n) โ€” O(n) O(log n) for poll peek is O(1)
EnumMap / EnumSet O(1) โ€” O(1) O(1) array or bit-vector inside
CopyOnWriteArrayList O(n) (copies) O(1) O(n) O(n) cheap, lock-free reads

Two caveats make this table honest:

  • "Average" depends on the hash function. A HashMap with a terrible hashCode (say, every key returns 1) puts everything in one bucket. Java 8+ turns large buckets into small trees, so even then lookups degrade to O(log n) instead of O(n), but you lose the speed you came for. How HashMap Works Inside explains why.
  • Big-O hides constant factors. LinkedList.addFirst and ArrayDeque.addFirst are both O(1), yet ArrayDeque is usually much faster because its elements sit next to each other in memory, which CPU caches love. For small collections (a few dozen items), a linear scan of an ArrayList can beat hashing.

See the difference: contains on a list versus a set

The most common performance bug with collections is calling contains on a big List inside a loop. Each call scans the list, so the loop does n ร— m work. A HashSet answers in constant time.

Java contains: ArrayList versus HashSet

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Both find the same 1,000 values (every second multiple of 37 is even), but the list version usually takes a sizable fraction of a second, while the set version finishes in well under a millisecond. The exact numbers change from run to run and machine to machine; the ratio is what matters. Multiply the list size by 10 and the list time grows about 10 times, while the set time barely moves.

If you need both the order of a list and fast membership checks, keep both: a list for order and a set for lookups, or a single LinkedHashSet if the items are unique.

See the difference: positional access on a LinkedList

LinkedList implements List, so get(i) compiles. But a linked list has no array to index into: it must walk from the nearer end, node by node. A classic index-based loop therefore becomes O(nยฒ):

Java Index loops on ArrayList versus LinkedList

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

The LinkedList index loop visits about 100 million nodes in total, while the for-each loop visits each node once. If you inherit code that receives "some List" and loops by index, iterate with for-each instead; it's fast for every implementation. The LinkedList lesson explains the few situations where a linked list is actually the right choice.

Ordering decides between the Hash, Linked and Tree variants

When performance is similar, order is usually what picks the class. The same input gives three different orders:

Java Same words, three orders

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

All three remove the duplicates. HashSet gives an order that depends on hash codes and table size: it may look sorted for some inputs, but it can change when the set grows or between Java versions, so never rely on it. Choose LinkedHashSet when the order things arrived in matters (showing a user's recent searches without duplicates), and TreeSet or TreeMap when you need sorting, ranges or "nearest" queries like ceiling and floor (TreeMap and TreeSet).

If you only need a sorted result once, it's often simpler and faster to fill an ArrayList and call sort at the end than to keep a TreeSet sorted after every insertion.

Memory: what the boxes cost

Collections hold references to objects, never primitives. A List<Integer> stores a reference to an Integer object for every number, and each of those objects has a header. On a typical 64-bit JVM with compressed references, the approximate costs are:

Storage Approximate bytes per element
int[] 4
ArrayList<Integer> 4 (reference) + 16 (Integer object) = about 20, plus spare capacity
LinkedList<Integer> 24 (node) + 16 (Integer) = about 40
HashSet<Integer> / HashMap entry about 32 (entry) + 4 (table slot) + the key and value objects
TreeMap entry about 40 + the key and value objects

Small Integer values from -128 to 127 are cached and shared (Wrapper Classes and Autoboxing), but in general a million boxed integers in a HashSet take dozens of megabytes, compared with 4 MB in an int[]. Some practical consequences:

  • For large amounts of numeric data, prefer primitive arrays or IntStream processing; sort with Arrays.sort(int[]).
  • Use BitSet for sets of small non-negative integers and EnumSet/EnumMap for enum keys; both are tiny and fast (EnumMap, EnumSet, IdentityHashMap, WeakHashMap and BitSet).
  • If you know the final size of an ArrayList or HashMap, give it up front (new ArrayList<>(10_000), HashMap.newHashMap(10_000) since Java 19) to avoid repeated resizing.
  • Immutable collections from List.of and Map.of are compact and safe to share (Immutable Collections and Utility Methods).

Measuring with System.nanoTime, carefully

System.nanoTime() returns a high-resolution timestamp meant for measuring elapsed time (don't use currentTimeMillis for that; it can jump when the system clock is adjusted). The pattern is simple: take a timestamp, do the work, subtract. But the JVM makes naive measurements misleading:

  • Warm-up. Code starts interpreted and is compiled by the JIT after it runs often. The first iterations are slow; measure after a warm-up phase, or repeat the measurement several times and look at later rounds.
  • Dead-code elimination. If the result of your loop is never used, the JIT may remove the loop entirely. Always use the result (print it, or add it to a sum you print).
  • Noise. Garbage collection, other processes and CPU frequency changes add jitter. Compare large differences (10ร— or more), not 5%.
Java Warm-up changes the numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with IO.readln() or a Scanner), it gets the next line from this box.

Usually the first round is clearly the slowest, and later rounds settle once the JIT has compiled the hot loop. For serious benchmarks, use JMH (the Java Microbenchmark Harness), which handles warm-up, forks and statistics for you. The Java Performance Tips lesson shows how.

Common scenarios

Task Good choice Why
A list of items to display or process in order ArrayList fast iteration and indexing
Count how often each word appears HashMap<String, Integer> with merge O(1) updates by key
Remove duplicates, keep first-seen order LinkedHashSet uniqueness plus insertion order
Leaderboard sorted by score TreeMap or sort a list once sorted iteration, ranges
Task queue, BFS over a graph ArrayDeque as Queue O(1) at both ends
Undo history ArrayDeque as Deque (stack) push/pop at the top
Always process the most urgent job PriorityQueue with a Comparator O(log n) insert and remove-min
Settings keyed by an enum EnumMap compact, ordered by declaration
Cache with eviction of the oldest entry LinkedHashMap with removeEldestEntry built-in access order
Counters updated by many threads ConcurrentHashMap with merge atomic, scalable

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Your code checks thousands of times whether an ID is in a collection of 200,000 IDs. Which collection fits best?

    HashSet.contains is O(1) on average. A list scans its elements on every call, which is O(n) per lookup.
  2. 2. Which loop is slow on a LinkedList with 100,000 elements?

    get(i) on a linked list walks node by node from an end, so the index loop does O(nยฒ) work. The other three walk the chain once.
  3. 3. You need unique tags shown in the order users first entered them. Which set?

    LinkedHashSet keeps insertion order and ignores later duplicates. TreeSet would sort them; HashSet promises no order.
  4. 4. Why should you print or otherwise use the result of a loop you time with System.nanoTime?

    If a computation's result is never used, the JIT compiler may eliminate it, and you'd measure an empty loop.
  5. 5. Roughly how does a TreeMap lookup scale as the map grows from 1,000 to 1,000,000 entries?

    TreeMap operations are O(log n). log2 of 1,000 is about 10 and log2 of 1,000,000 is about 20, so a thousand times more data costs only about twice the steps.

Summary

  • Choose the interface by the question your code asks: lookup by key โ†’ Map, uniqueness โ†’ Set, arrival order โ†’ Queue/Deque, position โ†’ List.
  • Then choose the implementation by order: Hash (none), Linked (insertion), Tree (sorted). Use Enum, immutable or concurrent variants for those special needs.
  • Defaults: ArrayList, HashMap, HashSet, ArrayDeque, declared through their interfaces.
  • Know the costs: contains on a list is O(n), on a hash set O(1); get(i) on a LinkedList is O(n); tree operations are O(log n).
  • Boxed elements cost far more memory than primitives; use primitive arrays, BitSet or EnumSet for large or special data.
  • Measure with System.nanoTime, warm up, use the results and compare big differences; use JMH for real benchmarks.

Next: Generics, where you'll learn how the <T> in List<T> works and how to write your own type-safe classes and methods.