The Collections Framework

The Collections Framework is a small set of interfaces, a larger set of implementations, and a table you should be able to reproduce from memory: for each access pattern, which structure, and at what cost. Everything else in this course is a deeper look at one row of that table. This lesson is the table, the skeleton the implementations share, the difference between a view and a copy, and the two places where the framework deliberately refuses to promise an order.

#The interfaces

Iterable
 └─ Collection
     ├─ List        ordered, indexed, duplicates allowed
     ├─ Set         no duplicates
     │   └─ SortedSet → NavigableSet   sorted
     └─ Queue       head-first access
         └─ Deque   both ends
Map                 key → value (not a Collection)
 └─ SortedMap → NavigableMap

Map is deliberately not a Collection — it is a mapping, not a bag of elements — but its keySet(), values() and entrySet() are live views that are. Java 21 added SequencedCollection and SequencedMap above List, Deque, LinkedHashSet and LinkedHashMap: getFirst(), getLast(), removeFirst(), reversed(), so "the last element" no longer needs list.get(list.size() - 1).

Declare variables and parameters as the interface. List<Order> orders, not ArrayList<Order> orders. The concrete type is chosen where the object is created and can change there without touching anything else.

#The table

The O(1) claims for hash structures assume a good hashCode. The contains cost of a list is the reason a List used for membership tests is a performance bug.

#Under the hood: the skeleton every implementation shares

Open ArrayList and its superclass chain is AbstractList → AbstractCollection. Those abstract classes are the framework's real design: AbstractCollection implements contains, toArray, addAll, removeAll and toString in terms of iterator() and size(); AbstractList adds indexOf, equals, hashCode, subList and an Iterator in terms of get(int). A new List needs get and size to be complete, which is how Arrays.asList is forty lines. It is also why a wrapper that overrides add and not addAll can be bypassed, as the inheritance lesson showed: AbstractCollection.addAll calls add per element.

Two more pieces of shared machinery matter in practice:

• modCount and fail-fast iterators. Every structural change increments an int modCount; an iterator records the value at creation and compares on each next(), throwing ConcurrentModificationException on a mismatch. It is a best-effort check for the single-threaded mistake of modifying inside a for-each, not a thread-safety mechanism.
• RandomAccess. A marker interface on ArrayList, Vector and CopyOnWriteArrayList and not on LinkedList. Collections.binarySearch, shuffle, reverse and Collections.sort check it and switch between index-based and iterator-based algorithms, which is why binary search on a LinkedList is not the disaster it could be.

The immutable factories are their own family. List.of returns one of two hidden classes (List12 for zero to two elements stored in fields, ListN for more), with no modCount, no spare capacity, and a null check on every element. Set.of and Map.of use an open-addressing table whose probe order is salted with a per-JVM-run random value, so their iteration order changes on every start. That is deliberate: the JDK authors knew code would come to rely on whatever order appeared in testing, and made the order unrepeatable so it never could.

#Immutable collections

List<String> names = List.of("a", "b");
Set<Integer> ids = Set.of(1, 2, 3);
Map<String, Integer> limits = Map.of("basic", 10, "pro", 100);
List<String> copy = List.copyOf(mutable);

These are unmodifiable — add throws UnsupportedOperationException — reject null, and Set.of/Map.of reject duplicate keys at creation. They are the right return type for "here is data" and the right way to hold constants. Collections.unmodifiableList(x) is different: it is a view over x, and changes to x show through.

#Views and copies

Many methods return views, not copies:

• map.keySet(), map.values(), map.entrySet() — live; removing from the view removes from the map.
• list.subList(from, to) — live; structural changes to the parent invalidate it (the sublist checks the parent's modCount and throws).
• Arrays.asList(array) — fixed-size, backed by the array; set writes through, add throws.
• Collections.unmodifiableX(c) — read-only window onto c.

If you need a snapshot, copy: new ArrayList<>(view) or List.copyOf(view).

#Walkthrough: the test that failed one Tuesday in four

A service builds Set<String> roles = Set.of("admin", "editor", "viewer") and renders them into a comma-separated header. A test asserted the header equalled "admin,editor,viewer". It passed for weeks, then started failing on roughly a quarter of CI runs with "viewer,admin,editor".

1. Set.of picks its probe sequence from a salt computed once per JVM start (ImmutableCollections.SALT32L, seeded from System.nanoTime()). Iteration order is whatever the salted table produces, and it differs run to run.
2. The test happened to pass while the CI image started JVMs in a way that produced the same salt often; an image update changed that, and the test became honest about a bug it had been hiding.
3. The bug was not the test: it was a header whose order the product silently depended on, and a HashSet would have had the same problem across JVM versions instead of across runs.
4. Fix: new TreeSet<>(roles) or roles.stream().sorted() at the point of rendering, because "comma-separated in a stable order" is an ordering requirement, and a Set is the type that promises none.

The framework's rule: a Set or Map that does not say "ordered" or "sorted" in its name has no iteration order you may rely on, and the immutable factories enforce it by changing the order under you.

#Iteration and modification

for (Order o : orders) {
    if (o.isCancelled()) orders.remove(o);   // ConcurrentModificationException
}

Every standard collection's iterator is fail-fast: it remembers a modification count and throws when the collection changes underneath it. Options, in order of preference:

orders.removeIf(Order::isCancelled);                       // clearest
for (Iterator<Order> it = orders.iterator(); it.hasNext();) {
    if (it.next().isCancelled()) it.remove();              // the iterator's own remove is allowed
}

The exception is best-effort, not a guarantee, and does not fire for concurrent modification from another thread reliably — that is what the concurrent collections are for. One shape hides: removing the second-to-last element inside a for-each does not throw, because hasNext() returns false before the check runs, and the last element is silently skipped.

#Equality and ordering

HashSet, HashMap use hashCode and equals. TreeSet, TreeMap use compareTo or a Comparator and never call equals. List.contains, indexOf, remove(Object) use equals. A type with a broken equals/hashCode pair misbehaves in the first family and not the second, which is why "it works in a list but not in a set" is a hashCode bug.

#Utility methods worth knowing

Collections.sort, List.sort(comparator), Collections.shuffle, Collections.frequency, Collections.nCopies, Collections.emptyList(), Map.getOrDefault, Map.computeIfAbsent, Map.merge. The last two replace most if (!map.containsKey(k)) map.put(k, new ArrayList<>()) code:

Map<String, List<Order>> byCustomer = new HashMap<>();
byCustomer.computeIfAbsent(o.customerId(), k -> new ArrayList<>()).add(o);
 
Map<String, Integer> counts = new HashMap<>();
counts.merge(word, 1, Integer::sum);

#Try it yourself

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : list) if (x == 3) list.remove(x);
System.out.println(list);
List<Integer> list2 = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : list2) if (x == 2) list2.remove(x);
System.out.println(list2);

Map<String, Integer> m = new HashMap<>(Map.of("a", 1, "b", 2));
Set<String> keys = m.keySet();
List<String> snapshot = new ArrayList<>(keys);
m.remove("a");
keys.remove("b");
System.out.println(keys + " " + snapshot + " " + m);

#Misconceptions

• "Set.of keeps the order I gave it." It keeps an order salted per JVM run, so that nothing can depend on it. LinkedHashSet keeps insertion order; List.of keeps yours.
• "unmodifiableList makes the data immutable." It makes the view read-only. The original owner still has the mutable list.
• "ConcurrentModificationException means two threads." It almost always means the same thread modifying inside a for-each, and it is best-effort even then.
• "keySet() is a copy of the keys." It is a live view: removals go through in both directions.
• "Any collection with contains is fine for membership." List.contains is a linear scan. Membership is a Set.

#Going deeper

• AbstractCollection and AbstractList source and Javadoc: the skeletal implementations, and the "self-use" documentation that tells you which methods call which.
• java.util.ImmutableCollections source, for SALT32L and the deliberately randomised Set.of order.
• JEP 431, Sequenced Collections (Java 21).
• ArrayList.Itr.checkForComodification() and the hasNext() that skips it on the last element.
• Effective Java, item 64 (refer to objects by their interfaces) and item 15.