Почему Stream.findFirst() не гарантирует порядок без sorted()?

Сегодня разберем очень забавный вопрос:
— Есть огромный параллельный стрим (`parallelStream`) из миллиона элементов. Делаем `filter()`, а затем `findFirst()`. Гарантирует ли JDK, что мы получим самый первый элемент из исходного списка?

Обычно сразу звучит ответ: «Да, конечно! Это же терминальный оператор первого типа!»

Интервьюер улыбается и нажимает кнопку Run на заготовленном коде. Кандидат получает случайный элемент из середины списка. Оффер он не получил.

Давайте разберем этот капкан раз и навсегда. Поехали.

Как работает Stream Pipeline под капотом

Когда вы собираете цепочку операций (source -> intermediate -> terminal), внутри строится граф. Но самое интересное начинается в момент выполнения терминала.

Для оптимизации производительности Java использует механизм Sink-ов (сливов). Каждый промежуточный узел — это обертка над Sink предыдущего узла. Когда мы запускаем обход, данные начинают проваливаться сквозь эту трубу.

1. filter(predicate): Это stateless-операция. Она просто берет каждый пришедший элемент, применяет предикат и либо пропускает его дальше по трубе, либо выбрасывает. Она ничего не знает о своих соседях.
2. findFirst(): Это short-circuiting терминал. Его задача — как можно быстрее сказать «хватит». Получив первый подходящий элемент, он выстреливает сигнал прерывания вверх по стеку вызовов через метод cancellationRequested().

Последовательный vs Параллельный поток

Sequential stream:
Здесь все прозаично. Источник данных выдает элементы строго один за другим: 1, 2, 3... Труба одна. Элемент 1 входит в фильтр, проходит его, падает в findFirst. Сигнал остановки идет назад к источнику. Все счастливы, мы получили именно единицу.

Parallel stream (и вот тут ловушка):
Чтобы задействовать ваши 8 ядер процессора, фреймворк разбивает источник на независимые корзины (spliterator) и создает несколько труб одновременно.
- Поток А обрабатывает диапазон [0..249_999]
- Поток Б обрабатывает диапазон [250_000..499_999]
- ...и так далее.

Они работают абсолютно асинхронно. Если поток Б находит подходящий элемент на своей позиции 300_000 раньше, чем поток А успеет дочистить свой диапазон до элемента на позиции 10, то результат гонки непредсказуем. Кто первым нашел и передал значение в сборщик.

findFirst() в параллельном режиме ищет не «первый по индексу», а «первый доступный от любого сплиттера».

Так откуда берется иллюзия порядка?

Многие привыкли, что стримы ведут себя упорядоченно. И это правда, но только если соблюдено одно из условий:
1. Вы используете sequential stream.
2. Ваш источник сам по себе упорядочен (ArrayList, массив, IntStream.range), НО при этом операция перед поиском должна сохранять порядок. Например, map() сохраняет упорядоченность, поэтому в последовательном потоке list.stream().map(...).findFirst() даст логически первый элемент.
3. В параллельном потоке вы принудительно вставили sorted(). Эта операция является stateful. Чтобы отсортировать данные, ей нужно собрать их все (или значительную часть) в кучу, выстроить очередь приоритетов и только потом начать выдавать наружу. Вот после нее findFirst() действительно выдаст минимальный (самый первый) элемент всей выборки, потому что физически не может выдать второй, пока не сформирован первый.

Важный нюанс про производительность:

Никогда не делайте parallelStream().sorted().findFirst(). Сортировка огромного датасета ради поиска одного минимального значения убьет всю выгоду многопоточности и сожрет память на куче. Для этой задачи используйте обычное дерево или специализированный коллектор вроде reducing(Integer::min).