--- title: 'Collections Framework' source: 'https://academia.sh/en/courses/java-standard-library/collections-framework' course: 'The Standard Library and Streams' language: en updated: '2026-08-17T18:09:41+00:00' license: 'CC BY-SA 4.0' --- # Collections Framework The same three implementations are run side by side for four separate families, and seven of fifteen observations come out as interface guarantees, eight as the chosen class's implementation behavior alone. The bounding measurement bounds this very distinction: on a four-element source, PriorityQueue's iteration order matches its exit order by coincidence, and once a fifth element is added the distinction becomes visible again. Throughout the Object-Oriented Java course, one decision was always given by the language. The visibility level decided which member would be seen, `final` decided which variable could never be rebound, a checked exception decided which failure would stand in the signature. The closing lesson measured that none of the three contracts — precondition, postcondition, invariant — eliminates a flaw, they only move where it sits; but the decision was still inside the language, and the compiler could read it from the source every time. This lesson starts by calling a written library, and the decision is now outside the language. `List`, `Set`, `Queue`, `Map` are each an interface, and an interface is a promise; but who makes that promise is not read from a single place. An observed behavior can belong to one of three sources — the interface itself, the chosen class, or a rule the caller follows — and the three cannot be told apart in any way by the call's syntax. `ArrayList` and `LinkedList` both accept the same `add(0)` call, both answer the same `get(0)` call; which behavior stays the same across both, which changes when the class changes, cannot be seen from the source text. This lesson's and this course's question is: who gives the guarantee for an observation you are holding. ## Three Implementations, One Question The question's answer cannot be found with a single implementation — someone watching one class alone confuses its behavior with the interface's promise. The measurement therefore lines up **three** implementations that speak the same interface and asks all three the same question: if the answer is the same across all three, the observation comes from the interface; if the three diverge, the observation belongs to the implementation. - **CO1** — The `Guarantee` class below is not specific to any family. `ask` only compares the answers it gathers; being a list, set, queue, or map does not change the criterion. - **CO2** — If an implementation throws an exception during the call, its answer is counted as `"error"` and compared in the same column as the other two answers; the exception does not open a separate branch. ```java // Guarantee.java — who gives a behavior's guarantee: the interface, or the implementation import java.util.*; import java.util.function.*; public class Guarantee { static int byInterface = 0; static int byImplementation = 0; final List names = new ArrayList<>(); final List> suppliers = new ArrayList<>(); Guarantee add(String name, Supplier supplier) { names.add(name); suppliers.add(supplier); return this; } void header(String family) { StringBuilder sb = new StringBuilder(String.format("%-36s", family)); for (String name : names) sb.append(String.format("%-15s", name)); sb.append("guarantee giver"); System.out.println(sb); } void ask(String question, Function observe) { List answers = new ArrayList<>(); for (Supplier u : suppliers) { String y; try { y = observe.apply(u.get()); } catch (RuntimeException e) { y = "error"; } answers.add(y); } boolean shared = new HashSet<>(answers).size() == 1; if (shared) byInterface++; else byImplementation++; StringBuilder sb = new StringBuilder(String.format("%-36s", question)); for (String y : answers) sb.append(String.format("%-15s", y)); sb.append(shared ? "interface" : "implementation"); System.out.println(sb); } static void summary() { System.out.printf("observations: %d interface guarantees, %d implementation behaviors%n", byInterface, byImplementation); } } ``` `add` adds one implementation to a family; every family calls it three times. `ask` puts one question to all three implementations at once and runs a single counter: if the answer set drops to a single element (`new HashSet<>(answers).size() == 1`), the question is written into the interface column; if it does not drop, into the implementation column. The rule is mechanical and has no subject — it does not know which family is being asked, it only counts answers. ## Four Families, Fifteen Observations - **CO3** — The source list `SOURCE` is five fixed elements and stays unchanged across all four families; it is written into the map in the same order too. - **CO4** — All fifteen counted rows come from a single run of the same program; `summary` gives that run's total, counting no other row. ```java // Framework.java — separates the four families' observable promises import java.util.*; public class Framework { static final List SOURCE = List.of("zulu", "delta", "alfa", "carli", "bravo"); static Map fill(Map m) { for (int i = 0; i < SOURCE.size(); i++) m.put(SOURCE.get(i), i); return m; } @SuppressWarnings("unchecked") public static void main(String[] args) { Guarantee list = new Guarantee() .add("ArrayList", () -> new ArrayList<>(SOURCE)) .add("LinkedList", () -> new LinkedList<>(SOURCE)) .add("List.of", () -> List.copyOf(SOURCE)); list.header("list"); list.ask("is insertion order preserved", o -> String.valueOf(new ArrayList<>((List) o).equals(SOURCE))); list.ask("is indexed access available", o -> ((List) o).get(1)); list.ask("does equality look at content", o -> String.valueOf(o.equals(new ArrayList<>(SOURCE)))); list.ask("can an element be added", o -> { try { ((List) o).add("extra"); return "yes"; } catch (RuntimeException e) { return "no"; } }); list.ask("can a null value be held", o -> { try { ((List) o).add(null); return "yes"; } catch (RuntimeException e) { return "no"; } }); System.out.println(); Guarantee set = new Guarantee() .add("HashSet", () -> new HashSet<>(SOURCE)) .add("LinkedHashSet", () -> new LinkedHashSet<>(SOURCE)) .add("TreeSet", () -> new TreeSet<>(SOURCE)); set.header("set"); set.ask("is a duplicate element accepted", o -> { Set s = (Set) o; s.add("alfa"); return String.valueOf(s.size()); }); set.ask("is iteration order insertion order", o -> String.valueOf(new ArrayList<>((Set) o).equals(SOURCE))); set.ask("is a null value accepted", o -> { try { ((Set) o).add(null); return "yes"; } catch (RuntimeException e) { return "no"; } }); System.out.println(); Guarantee queue = new Guarantee() .add("ArrayDeque", () -> new ArrayDeque<>(SOURCE)) .add("LinkedList", () -> new LinkedList<>(SOURCE)) .add("PriorityQueue", () -> new PriorityQueue<>(SOURCE)); queue.header("queue"); queue.ask("element coming out first", o -> ((Queue) o).poll()); queue.ask("what is returned when empty", o -> { Queue q = (Queue) o; while (q.poll() != null) { } return String.valueOf(q.poll()); }); queue.ask("is iteration order exit order", o -> { Queue q = (Queue) o; List iteration = new ArrayList<>(q); List exit = new ArrayList<>(); String s; while ((s = q.poll()) != null) exit.add(s); return String.valueOf(iteration.equals(exit)); }); System.out.println(); Guarantee map = new Guarantee() .add("HashMap", () -> fill(new HashMap<>())) .add("LinkedHashMap", () -> fill(new LinkedHashMap<>())) .add("TreeMap", () -> fill(new TreeMap<>())); map.header("map"); map.ask("is the key unique", o -> { Map m = (Map) o; m.put("alfa", 99); return String.valueOf(m.size()); }); map.ask("is the key view live", o -> { Map m = (Map) o; Set g = m.keySet(); m.put("extra", 5); return String.valueOf(g.contains("extra")); }); map.ask("is iteration order insertion order", o -> String.valueOf(new ArrayList<>(((Map) o).keySet()) .equals(SOURCE))); map.ask("is a null key accepted", o -> { try { ((Map) o).put(null, 0); return "yes"; } catch (RuntimeException e) { return "no"; } }); System.out.println(); Guarantee.summary(); } } ``` ``` list ArrayList LinkedList List.of guarantee giver is insertion order preserved true true true interface is indexed access available delta delta delta interface does equality look at content true true true interface can an element be added yes yes no implementation can a null value be held yes yes no implementation set HashSet LinkedHashSet TreeSet guarantee giver is a duplicate element accepted 5 5 5 interface is iteration order insertion order false true false implementation is a null value accepted yes yes no implementation queue ArrayDeque LinkedList PriorityQueue guarantee giver element coming out first zulu zulu alfa implementation what is returned when empty null null null interface is iteration order exit order true true false implementation map HashMap LinkedHashMap TreeMap guarantee giver is the key unique 5 5 5 interface is the key view live true true true interface is iteration order insertion order false true false implementation is a null key accepted yes yes no implementation observations: 7 interface guarantees, 8 implementation behaviors ``` **Seven** of the fifteen rows gathered in the interface column, **eight** in the implementation column. The split is not arbitrary, and a line can be drawn cutting the table in two: **what is held** stands in the interface, **how and in what order it is held** is left to the implementation. That a list preserves insertion order, gives back what it holds by index, and that its equality looks at content — all three are the same across the three classes. That adding the same element a second time will not grow a set, that pulling from an empty queue gives `null` — these are the same too. By contrast, which order a set or map is walked in, which element comes out of the front of a queue, and whether a container accepts a null value diverge row by row. **Most** of a behavior list drawn by watching a single class — just `HashMap`, just `PriorityQueue` — is not the promise the interface gives. ## Optional Operation: The Interface's Own Reservation Two rows in the table deserve a separate reading: "can an element be added" and "can a null value be held" were both marked `implementation`, because the container `List.of` produces rejects both, `ArrayList` and `LinkedList` accept both. But the `Collection` interface's own definition calls the `add` method an **optional operation**: the interface defines the method, and at the same time says an implementation may reject it. This splits the guarantee question in two — whether the call **will succeed** is one question, what happens **when it fails** is a separate question. The first's answer, in the table above, depended on the implementation; the second is measured below. - **CO5** — All four container kinds share the same trial: try adding a single element, if rejected write the exception's class name, if accepted write `"succeeded"`. ```java // Rejection.java — do all rejecting implementations throw the same exception import java.util.*; public class Rejection { static String attempt(Runnable action) { try { action.run(); return "succeeded"; } catch (RuntimeException e) { return e.getClass().getSimpleName(); } } public static void main(String[] args) { List mutableList = new ArrayList<>(List.of("a")); List fixedList = List.of("a"); Set fixedSet = Set.of("a"); Map fixedMap = Map.of("a", 1); System.out.println("ArrayList.add : " + attempt(() -> mutableList.add("b"))); System.out.println("List.of(...).add : " + attempt(() -> fixedList.add("b"))); System.out.println("Set.of(...).add : " + attempt(() -> fixedSet.add("b"))); System.out.println("Map.of(...).put : " + attempt(() -> fixedMap.put("b", 2))); } } ``` ``` ArrayList.add : succeeded List.of(...).add : UnsupportedOperationException Set.of(...).add : UnsupportedOperationException Map.of(...).put : UnsupportedOperationException ``` Three separate container kinds, three separate packages, give the same rejection with the same class. If this row entered the table above, it would be marked `interface` because of the shared answer — yet the rejection **itself** never happens at all for `ArrayList`, it only happens for the three fixed containers. The contradiction stays only apparent, because two separate questions are getting mixed up. The answer to "is the addition accepted" depends on the implementation, and was counted that way in the previous table. The answer to "which exception falls if it is not accepted" is bound to a single class named in the `Collection` interface's javadoc, and does not change across the three packages. The interface does not guarantee a behavior here, it guarantees **the form of a rejection**: every implementation that rejects, rejects with the same name, the same unchecked exception class. This is why the phrase "optional operation" means not "the operation does not exist" but "the operation may exist, or fall with its name." ## The Bounding Measurement: Agreement Is Weak Evidence The framework's rule is a simple inference: if the three answers are the same, it is the interface. This is an **inference**, it does not look at documentation — and the inference itself can be wrong. The queue table's third row (`is iteration order exit order`) gave `false` for `PriorityQueue`; for `ArrayDeque` and `LinkedList`, `true`. This row's divergence with the five-element source was already seen. What happens if the same question is asked of a smaller, four-element source? - **CO6** — The four-element source is five-element `SOURCE` with its first element (`zulu`) removed; once the fifth element is added back, the source returns to being byte-for-byte `SOURCE` again. ```java // Coincidence.java — observed agreement is not proof of a guarantee import java.util.*; public class Coincidence { static final List SOURCE = List.of("zulu", "delta", "alfa", "carli", "bravo"); static boolean iterationEqualsExit(List source) { PriorityQueue pq = new PriorityQueue<>(source); List iteration = new ArrayList<>(pq); List exit = new ArrayList<>(); String s; while ((s = pq.poll()) != null) exit.add(s); return iteration.equals(exit); } public static void main(String[] args) { List fourElements = SOURCE.subList(1, 5); System.out.println("four-element source : " + fourElements); System.out.println("is iteration order exit order : " + iterationEqualsExit(fourElements)); List fiveElements = new ArrayList<>(fourElements); fiveElements.add(0, "zulu"); System.out.println("source once fifth element added: " + fiveElements); System.out.println("is iteration order exit order : " + iterationEqualsExit(fiveElements)); } } ``` ``` four-element source : [delta, alfa, carli, bravo] is iteration order exit order : true source once fifth element added: [zulu, delta, alfa, carli, bravo] is iteration order exit order : false ``` With the four-element source, `PriorityQueue`'s iteration order matches its exit order **exactly** — by the inference's own rule, this would count as an interface guarantee. But once the fifth element is added and the source becomes `SOURCE` itself again, the same question gives `false`: the result already seen in the queue table. The only difference is the elements themselves; the queue interface never promised anything about iteration order, neither at four elements nor at five. The match that appeared in the four-element case was not a promise the library gave, it was those five names coincidentally lining up with the heap's layout. This is how to read the criterion built through the lesson in reverse: **agreement observed weakly supports a guarantee, divergence observed proves the absence of a guarantee for certain.** Three implementations giving the same answer could be an interface's promise, or it could equally well be a coincidence born from the data set's smallness; the only way to tell them apart is to change the data set and ask the same question again. Divergence's evidentiary power is higher than this, because no coincidence can force three separate classes into three separate answers — a diverging row always shows a real implementation difference. ## Summary - Who gives a behavior's guarantee cannot be seen from the call's syntax; three implementations have to be run side by side and their answers compared. If the answer is the same across all three, the observation comes from the interface; if it diverges, it comes from the chosen class. - Of fifteen questions asked across four families (list, set, queue, map), **seven** came out as interface guarantees, **eight** as implementation behavior. What is held stands in the interface; how and in what order it is held is left to the implementation. - The `Collection` interface defines methods like `add` as optional operations: whether they are accepted depends on the implementation, but which exception falls when rejected stays the same across three separate packages — not the rejection itself, but the rejection's **form**, is the interface's promise. - Bounding measurement: on a four-element source, `PriorityQueue`'s iteration order matches its exit order by coincidence; once a fifth element is added, the distinction becomes visible again. Observed agreement is not proof of a guarantee; observed divergence proves the absence of one for certain. - The `Gauge` core (the class-file information reader) is not used in this lesson; the measurement rests only on run-time observation, because the question asked concerns the promise the library gives, not the compiler. ## Next Step This lesson measured four families as a whole and counted how many of each family's promises come from the interface. But the distinction between "list," "set," and "queue" itself was never questioned — all three are collections, all three can accept the same workload. The next lesson gives the same data to all three interfaces at once and measures **which promise each one gives and which information each one silently drops**; it is there that `LinkedList` being both a list and a queue is seen to give the same call two separate meanings.