Итерация и порядок в коллекциях

Comparable, Comparator и сборка компараторов

Comparable - естественный порядок, зашитый в сам класс через compareTo. У числа, строки, даты он один и очевиден. Comparator - внешний порядок, и таких может быть сколько угодно: по возрасту, по имени, по дате регистрации.

Современные компараторы собирают комбинаторами: comparing по ключу, дальше thenComparing для разрешения равенства. Есть и явная политика для пустых значений через nullsFirst и nullsLast - вместо NPE (NullPointerException) в середине сортировки.

// Про reversed я проверил обе формы на одном наборе. comparing(age).reversed().thenComparing(name) даёт возраст по убыванию, а имена внутри по алфавиту. А comparing(age).thenComparing(name).reversed() разворачивает ВСЮ цепочку: и возраст, и имена идут по убыванию. Разница в одной точке, а результат разный.

Comparable

естественный порядок внутри класса, он один

reversed

разворачивает всю цепочку до себя, а не последний ключ

Контракт сравнения: что ловится, а что нет

Контракт требует трёх вещей: антисимметрии, транзитивности и стабильности между вызовами. Сортировка в JDK - это TimSort, и он контракт ПРОВЕРЯЕТ. Я скормил ему нетранзитивный компаратор (считает «почти равными» числа, отличающиеся меньше чем на десять) и получил ровно то самое: Comparison method violates its general contract! Компаратор, который никогда не возвращает ноль, ловится так же.

А теперь неприятное. Тот же TimSort на компараторе через вычитание НЕ упал. Сто тысяч чисел отсортировались молча. Проверил результат на маленьком наборе - он просто неправильный: вычитанием получилось [1500000000, -1500000000, 0, 2000000000, -2000000000], а через Integer.compare нормальное [-2000000000, -1500000000, 0, 1500000000, 2000000000].

// Вывод для практики жёсткий: исключение про контракт - это подарок, оно хотя бы кричит. Переполнение при вычитании обычно не кричит вовсе и отдаёт молча перепутанный порядок. Сравнивать числа надо через Integer.compare или Long.compare, всегда.

Comparator<Integer> bad = (x, y) -> x - y;
bad.compare(-2_000_000_000, 2_000_000_000); // +294967296, знак врёт
// правильно: Integer.compare(x, y)

TimSort

сортировка JDK, проверяет контракт компаратора

молчаливое переполнение

вычитание врёт знаком, исключения при этом нет

Стабильность и два лагеря итераторов

TimSort стабилен: элементы, равные по компаратору, сохраняют исходный взаимный порядок. Проверил на четырёх людях - отсортировал сначала по имени, потом по возрасту, и внутри каждого возраста имена остались по алфавиту. Отсюда практический приём: многоключевую сортировку можно делать последовательными проходами, от менее важного ключа к более важному.

Итераторы обычных коллекций работают на опережение: счётчик модификаций ловит изменение во время обхода и бросает исключение. Но это детектор, а не гарантия - я показывал в теме про списки, что удаление предпоследнего элемента проходит молча.

// Другой лагерь - итераторы, которые не падают вовсе. CopyOnWriteArrayList обходит снимок, сделанный в момент создания итератора, ConcurrentHashMap даёт слабо согласованный обход. Исключений нет, но и свежести данных никто не обещает: увидишь состояние где-то между началом и концом обхода.

стабильная сортировка

равные элементы не меняют взаимный порядок

обход снимка

итератор работает по копии, исключений нет

Как отвечать: «Comparable или Comparator - когда что берёшь?»

Comparable беру, когда у класса есть один естественный бесспорный порядок: числа, даты, версии. Он зашивается в сам класс через compareTo. Comparator - для всех остальных случаев: внешних порядков бывает много, и им не место внутри доменного класса. Сортировку пользователей по возрасту или по имени я собираю комбинаторами comparing и thenComparing прямо на месте использования. Дальше три вещи из практики. Первая: сравнивать числа вычитанием нельзя, оно переполняется - я проверял, для минус двух и плюс двух миллиардов результат выходит положительным, то есть знак врёт; правильный способ Integer.compare. Вторая: метод reversed разворачивает всю цепочку до себя, а не последний ключ, и это регулярно ловят на код-ревью. Третья: compareTo стоит согласовывать с equals, потому что TreeSet считает дубликатом всё, что даёт ноль при сравнении, и один и тот же набор в HashSet и TreeSet может дать разное число элементов.

Сильный ответ: чёткий критерий выбора - один бесспорный порядок против многих внешних, плюс три подвоха с последствиями. Каждый подвох назван вместе с правильным решением, а не брошен упоминанием.

На чём валят

• −Пишут компаратор через вычитание. Переполнение врёт знаком, и сортировка молча даёт неправильный порядок - исключения при этом может и не быть.
• −Ловят «violates its general contract» в try и идут дальше. Чинить надо компаратор: сообщение означает, что он несогласован.
• −Ставят reversed в конце цепочки thenComparing. Разворачивается вся цепочка, а не последний ключ.
• −Не согласуют compareTo с equals. TreeSet съедает неравные объекты как дубликаты, живой пример - BigDecimal.
• −Считают детектор изменения на обходе гарантией. Он лучше, чем ничего, но пропуски бывают.