Pick the Right Collection

The Big Picture

Choosing the right collection is a performance decision.

• Ask: ordering? uniqueness? key-value? thread-safety?
• ArrayList: default for lists
• HashSet: fast uniqueness checks
• HashMap: fast key-value lookups

Different implementations optimize different operations.

How It Works

Each collection trades off speed, order, and uniqueness.

• ArrayList: get(i) O(1), append amortized O(1), front/middle insert/remove O(n)
• HashSet/HashMap: O(1) average, no order
• TreeSet/TreeMap: O(log n), sorted
• LinkedHashMap: insertion order + O(1)
• ArrayDeque: O(1) for queue/stack patterns

In the Java Landscape

Decision tree for common cases:

• Ordered + fast access? ArrayList
• Unique + fast check? HashSet
• Sorted + unique? TreeSet
• Key-value, fastest lookup? HashMap
• Key-value + sorted keys? TreeMap
• FIFO queue? ArrayDeque

Pitfalls and Best Practices

• Profile before optimizing - ArrayList is usually fine
• Don't default to LinkedList - slower than expected
• Use Set for contains() checks, not List
• Size collections when you know capacity
• Thread safety? Use java.util.concurrent types