What contract must the supplier, accumulator, and combiner of a collect() satisfy for a correct parallel result, and what goes wrong if it is violated?

## The contract `collect(supplier, accumulator, combiner)` — and equally a `Collector` — must satisfy a small algebra so it can be run **in parallel** correctly. Three requirements: ### 1. Identity / supplier freshness The **supplier** must return a **new, empty** container on every call. In parallel, it is called once per chunk; if it returned a shared or pre-populated container, chunks would corrupt each other or double-count. (`ArrayList::new` is fine; `() -> sharedList` is a bug.) ### 2. Accumulator/combiner consistency (the key one) Let `A(container, element)` be accumulation and `C(c1, c2)` be combining. The contract: for any partition of the elements, **combining the per-partition accumulations must equal accumulating all elements into one container**. Concretely, if you accumulate elements `[1,2]` into `c1` and `[3,4]` into `c2`, then `C(c1, c2)` must equal accumulating `[1,2,3,4]` into a single container. This is an **associativity + consistency** requirement: the accumulator and combiner must implement the *same* logical operation. The classic violation: an accumulator that does extra work the combiner forgets. Example — building a sorted, deduplicated list where the accumulator inserts-in-order-and-dedups but the combiner does a plain `addAll`. Sequentially the combiner is never called, so it looks perfect. In parallel, `addAll` concatenates two sorted-deduped halves into an unsorted, possibly-duplicated whole. Wrong answer, only in parallel. ### 3. Non-interference and statelessness The functions must be **non-interfering**: they must not modify the **stream source** during the operation (e.g. don't `remove` from the backing list inside the accumulator) — that risks `ConcurrentModificationException` or undefined results. They should also avoid relying on **mutable shared state** outside the per-chunk container; the only legitimate shared mutable state is a **CONCURRENT** collector's single thread-safe container, whose accumulator is explicitly safe for concurrent calls. ## Why violations hide The combiner is **only invoked for parallel streams**. So a buggy combiner is completely dormant in sequential execution and in unit tests that use small or sequential streams. It awakens only when: - the stream is `.parallel()`/`parallelStream()`, **and** - the source is large enough to actually split (small streams may not split), **and** - the spliterator chooses split points that exercise the combiner. That makes these bugs **nondeterministic and environment-dependent** — they may pass on a 2-core machine and fail on a 32-core one, or pass for 100 elements and fail for 100,000. ## Correct example ```java // Correct: accumulator and combiner implement the same 'append' semantics List<Integer> xs = stream.collect( ArrayList::new, List::add, // accumulate: append one List::addAll); // combine: append all — consistent with append ``` ## Incorrect example ```java // BUG: accumulator dedups, combiner does not -> parallel produces duplicates Set<Integer> uniques = stream.collect( HashSet::new, HashSet::add, // ok, Set dedups on add (a, b) -> { a.addAll(b); return; }); // ok here because Set still dedups on addAll // (Sets stay correct; the trap appears when the *container* doesn't enforce the invariant, // e.g. a plain List that the accumulator manually keeps sorted but addAll does not.) ``` ## How to stay safe - Prefer **standard Collectors** — their accumulator/combiner pairs are proven consistent. - If hand-writing, make the accumulator and combiner two views of the **same** operation; test the combiner explicitly (call it directly) rather than trusting a sequential run. - Never mutate the source; never share a non-thread-safe container unless the collector is CONCURRENT. - Test with a **parallel** stream over a **large** input to actually exercise the combiner.