Collections Overview

Learning goals

By the end of this chapter you should be able to:

• Navigate the Collection and Map hierarchies and name the core interfaces
• Decide when to use List, Set, Queue, or Map for a given problem
• Declare collections against interfaces, not concrete classes
• Recognize ordered vs sorted vs insertion-order — three different ideas

The Java Collections Framework is the standard toolkit for grouping values in memory: lists, sets, queues, and maps. This chapter is the decision map before you dive into each structure in detail.

Two hierarchies

Java splits “many values” into two trees:

Iterable
  └── Collection
        ├── List      (ordered, duplicates OK)
        ├── Set       (no duplicate equals-elements)
        └── Queue     (FIFO / priority / deque variants)

Map (separate — keys to values, not a Collection)

Collection holds elements. Map holds entries keyed uniquely. You cannot assign a Map to a Collection reference.

List — ordered sequence

Use a List when order matters and duplicates are allowed.

List<String> tasks = new ArrayList<>();
tasks.add("deploy");
tasks.add("deploy");   // duplicate OK
String first = tasks.get(0);

Default mutable implementation: ArrayList. Indexed access is fast; middle insertions shift elements.

Immutable snapshots:

List<String> frozen = List.of("a", "b", "c");
List<String> copy = List.copyOf(someMutableList);

Set — unique membership

Use a Set when you care about presence, not how many times or in what order (unless you pick an ordered set).

Set<String> seen = new HashSet<>();
seen.add("user-42");
seen.add("user-42");   // ignored — set unchanged
boolean loggedIn = seen.contains("user-42");

HashSet — average O(1) add/contains, undefined iteration order.

LinkedHashSet — insertion-order iteration.

TreeSet — sorted order, O(log n), needs Comparable or Comparator.

Queue and Deque — processing order

Use a Queue when elements are processed in a defined order (usually FIFO).

Queue<String> fifo = new ArrayDeque<>();
fifo.offer("job-1");
fifo.offer("job-2");
String next = fifo.poll();  // "job-1"

Deque adds both-end operations — stack (push/pop) or double-ended queue.

PriorityQueue is not FIFO — always returns the smallest (or comparator-first) element.

Map — key to value

Use a Map when you look up values by a key and each key appears once.

Map<String, Integer> scores = new HashMap<>();
scores.put("alice", 95);
scores.putIfAbsent("bob", 80);
int alice = scores.get("alice");

HashMap — default mutable map, one null key allowed.

LinkedHashMap — predictable iteration or LRU-style access order.

TreeMap — sorted keys, navigable ranges.

ConcurrentHashMap — thread-safe without locking the entire map.

Decision guide

When two structures fit, prefer the simpler contract: a Set over a Map with dummy values.

Program to interfaces

// Good — swap ArrayList for LinkedList in one place
List<User> users = new ArrayList<>();

// Avoid unless you need Deque-specific methods
ArrayDeque<Task> tasks = new ArrayDeque<>();

Return List, Set, Map from public methods. Hide concrete types unless callers need implementation-specific performance (rare).

equals, hashCode, and comparators

HashSet and HashMap require consistent equals and hashCode on keys/elements.

record User(String id, String name) {
    @Override public boolean equals(Object o) { /* id only */ }
    @Override public int hashCode() { return Objects.hash(id); }
}

TreeSet / TreeMap need Comparable or a Comparator — equality follows comparison, not equals.

Breaking these contracts causes “lost” entries and impossible-to-debug set/map behavior.

Common mistakes

1. Using List.contains for frequent lookups — O(n); use Set or Map key set.
2. Confusing sorted with insertion-ordered — HashSet is neither; TreeSet is sorted.
3. Mutating keys while inside a HashMap — if hashCode changes, the entry is stranded.
4. Returning internal mutable collections — callers can break your invariants; return copies or unmodifiable views.
5. Choosing Vector / Hashtable — legacy synchronized types; use ArrayList + ConcurrentHashMap patterns instead.

Practice checkpoint

1. Track unique visitor IDs per day with fast membership checks — which type? Answer: Set<String> (HashSet or ConcurrentHashMap-backed set if concurrent).

2. Rank leaderboard top 10 by score, repeatedly poll highest — which type? Answer: PriorityQueue (or TreeMap if you also need lookup by name).

3. Cache config key → value with LRU eviction — which map? Answer: access-order LinkedHashMap with size cap, or Caffeine/similar in production.

4. Why declare Map<K,V> m = new HashMap<>() not HashMap on the left? Answer: flexibility to change implementation; clearer contract to callers.

Interview angles

• Complexity: ArrayList get O(1), add end amortized O(1), middle insert O(n); HashMap average O(1).
• Fail-fast iterators: structural modification during iteration (except via iterator remove) → ConcurrentModificationException.
• Null policy: HashMap allows one null key; ConcurrentHashMap allows no nulls.
• Immutable factories: List.of rejects null elements; fixed size.

Next: /java/learn/collections/lists/