Разбор Comparable и Comparator с примерами.

Comparable<T> — интерфейс с единственным методом int compareTo(T o). Реализовав его, класс объявляет, что у его экземпляров есть естественный порядок, и бесплатно получает работу с Arrays.sort(), Collections.sort(), TreeSet, TreeMap, binarySearch, Collections.max/min и сортировкой стримов.

Контракт требует антисимметричности, транзитивности и согласованности равных. Настоятельно рекомендуется (но не требуется) согласованность с equals. Метод возвращает знак, а не конкретные -1/0/1.

Что даёт реализация `Comparable`

Одна строка implements Comparable<T> подключает класс ко всей инфраструктуре сортировки JDK:

public class WordList {
    public static void main(String[] args) {
        Set<String> s = new TreeSet<>();
        Collections.addAll(s, args);
        System.out.println(s);   // отсортировано и без дубликатов
    }
}

Работает потому, что String реализует Comparable. Практически все value-классы в JDK и все enum'ы (через Enum, порядок = порядок объявления констант) его реализуют.

Контракт `compareTo`

Возвращает отрицательное число, ноль или положительное — если объект меньше, равен или больше аргумента. Бросает ClassCastException, если типы несравнимы.

Обозначим sgn(x) как функцию знака: -1, 0 или 1.

Обязательные условия

1. Антисимметричность

sgn(x.compareTo(y)) == -sgn(y.compareTo(x))

Следствие: x.compareTo(y) бросает исключение тогда и только тогда, когда его бросает y.compareTo(x).

2. Транзитивность

x.compareTo(y) > 0 && y.compareTo(z) > 0  ⟹  x.compareTo(z) > 0

3. Согласованность равных

x.compareTo(y) == 0  ⟹  sgn(x.compareTo(z)) == sgn(y.compareTo(z))  для любого z

Если два объекта равны с точки зрения порядка, они должны одинаково сравниваться со всеми остальными.

Настоятельная рекомендация (не требование)

(x.compareTo(y) == 0) == x.equals(y)

Согласованность с `equals` — ключевой момент

Нарушать её можно, но тогда класс обязан быть задокументирован. Стандартная формулировка из JDK:

Внимание: данный класс имеет естественный порядок, несогласованный с equals.

Почему это критично

Коллекции делятся на две группы по тому, что они используют для определения "одинаковости":

Коллекция	Использует
`HashSet`, `HashMap`, `ArrayList.contains`	`equals`
`TreeSet`, `TreeMap`, `Collections.binarySearch`	`compareTo`

Если эти два механизма расходятся, один и тот же набор элементов даст разные результаты в разных коллекциях.

Канонический пример — `BigDecimal`

BigDecimal a = new BigDecimal("1.0");
BigDecimal b = new BigDecimal("1.00");

a.equals(b);        // false — equals учитывает scale
a.compareTo(b);     // 0 — compareTo сравнивает только числовое значение

Set<BigDecimal> hashSet = new HashSet<>();
hashSet.add(a);
hashSet.add(b);
hashSet.size();     // 2 — два разных элемента по equals

Set<BigDecimal> treeSet = new TreeSet<>();
treeSet.add(a);
treeSet.add(b);
treeSet.size();     // 1 — второй элемент "равен" первому по compareTo

Формально TreeSet не нарушает контракт Set — он документирован как работающий по compareTo. Но для читателя кода это сюрприз.

`compareTo` возвращает знак, а не -1/0/1

Контракт гарантирует только знак результата. Конкретное значение — деталь реализации.

"a".compareTo("d");   // -3, а не -1 ('a'=97, 'd'=100)

String.compareTo() возвращает разницу кодов символов. Отсюда практическое правило:

// СЛОМАНО — упадёт на String и многих других классах
if (a.compareTo(b) == -1) { ... }

// ПРАВИЛЬНО
if (a.compareTo(b) < 0) { ... }

Обратная сторона: ваша реализация тоже не обязана возвращать -1/0/1 — достаточно правильного знака. Поэтому Integer.compare(x, y) — корректный кирпичик, хотя внутри может вернуть что угодно.

Сам контракт записан через sgn(...) именно поэтому: -3 и 3 — корректная антисимметричная пара.

Ограничение наследования

Нельзя расширить инстанцируемый класс новым компонентом сравнения, сохранив контракт. Добавили поле в подкласс и учли его в compareTo — сломали антисимметричность при сравнении экземпляра подкласса с экземпляром родителя.

Это ровно та же проблема, что у equals (Item 10).

Решение — композиция вместо наследования. Не наследуйтесь: храните экземпляр родителя как поле и добавьте view-метод, который его возвращает. Тогда вы вольны определить любой compareTo на новом классе, не нарушая контракт исходного.

Как писать `compareTo`

1. Никогда не используйте вычитание

// СЛОМАНО — переполнение
static Comparator<Integer> bad = (a, b) -> a - b;

При a = Integer.MAX_VALUE, b = -1 результат переполнится и станет отрицательным — порядок инвертируется. Трюк также некорректен для чисел с плавающей точкой (NaN, -0.0).

2. Используйте статические `compare`-методы

Начиная с Java 7 у всех боксированных примитивов есть безопасный compare:

Integer.compare(x, y)
Long.compare(x, y)
Double.compare(x, y)     // корректно обрабатывает NaN и -0.0
Boolean.compare(x, y)    // false < true

Для класса с несколькими полями сравниваем от самого значимого к наименее, останавливаясь на первом различии:

public int compareTo(PhoneNumber pn) {
    int result = Short.compare(areaCode, pn.areaCode);
    if (result == 0) {
        result = Short.compare(prefix, pn.prefix);
        if (result == 0) {
            result = Short.compare(lineNum, pn.lineNum);
        }
    }
    return result;
}

Порядок полей определяет семантику сортировки — это часть публичного контракта класса, документируйте его.

3. Comparator construction methods (Java 8+)

Читабельнее, ценой некоторой производительности:

private static final Comparator<PhoneNumber> COMPARATOR =
    Comparator.comparingInt((PhoneNumber pn) -> pn.areaCode)
              .thenComparingInt(pn -> pn.prefix)
              .thenComparingInt(pn -> pn.lineNum);

@Override
public int compareTo(PhoneNumber pn) {
    return COMPARATOR.compare(this, pn);
}

Два момента, которые спрашивают:

Явный тип в первой лямбде — (PhoneNumber pn). Вывод типов Java не справляется без этой подсказки, потому что в момент разбора comparingInt целевой тип ещё неизвестен. В последующих thenComparingInt тип уже выведен, аннотация не нужна.
Компаратор в статическом финальном поле — чтобы цепочка строилась один раз, а не на каждый вызов compareTo.

`Comparable` против `Comparator`

	`Comparable`	`Comparator`
Где живёт	Внутри класса	Снаружи
Метод	`compareTo(T o)`	`compare(T a, T b)`
Сколько порядков	Ровно один	Сколько угодно
Функциональный интерфейс	Формально да, но не для лямбд	Да, типичный кандидат
Когда использовать	Есть очевидный естественный порядок	Альтернативные / контекстные сортировки

Правило выбора: если естественный порядок неочевиден — не реализуйте Comparable. У Person порядок "по имени" ничем не обоснованнее "по возрасту"; лучше дать именованные компараторы:

public static final Comparator<Person> BY_NAME = Comparator.comparing(Person::getName);
public static final Comparator<Person> BY_AGE  = Comparator.comparingInt(Person::getAge);

Comparator также нужен, когда:

класс чужой и вы не можете его изменить;
нужен порядок, противоречащий естественному;
порядок зависит от контекста (локаль, настройки пользователя).

Практические заметки

Проверка типа не нужна. В отличие от equals(Object), compareTo(T) типизирован дженериком — компилятор проверяет тип за вас. Явный instanceof в начале метода не требуется. Если аргумент неподходящего типа всё же придёт (сырые типы), ClassCastException — корректное поведение.

null не обрабатывается. compareTo(null) должен бросить NullPointerException — это следует из того, что метод обращается к полям аргумента. Явная проверка не нужна.

Поля-объекты сравнивайте делегированием к их compareTo, а не собственной логикой.

Обратный порядок — через Comparator.reverseOrder() или cmp.reversed(). Не инвертируйте знак вручную (-compareTo(...)): на Integer.MIN_VALUE унарный минус даёт тот же Integer.MIN_VALUE, и знак не поменяется.

Совместимость с сортировкой. Arrays.sort и Collections.sort используют TimSort, который проверяет транзитивность и может бросить IllegalArgumentException: Comparison method violates its general contract! на некорректной реализации. Это частая ошибка в проде — обычно из-за вычитания с переполнением.

Типичные вопросы на интервью

Что такое естественный порядок? Порядок, определённый самим классом через compareTo. Используется по умолчанию в Arrays.sort, TreeSet, TreeMap и других, если явно не передан Comparator.

Чем Comparable отличается от Comparator? Кратко: один встроенный порядок против произвольного количества внешних.

Обязательно ли compareTo согласовывать с equals? Нет, но настоятельно рекомендуется. Иначе класс ведёт себя по-разному в хеш- и древовидных коллекциях, и это нужно документировать. Пример нарушения — BigDecimal.

Почему a - b в компараторе — ошибка? Переполнение целых. Integer.MAX_VALUE - (-1) даст отрицательное число, порядок инвертируется. Используйте Integer.compare.

Что вернёт compareTo? Отрицательное, ноль или положительное. Конкретное значение не гарантировано — сравнивайте только с нулём.

Может ли compareTo бросить исключение? Да: ClassCastException при несравнимом типе, NullPointerException при null. Оба — корректное поведение по контракту.

Что будет, если compareTo нарушает транзитивность? Сортировка может дать неверный результат или бросить IllegalArgumentException (TimSort детектирует часть нарушений). TreeMap может потерять элементы.

Реализуют ли enum'ы Comparable? Да, через java.lang.Enum. Порядок — по ordinal(), то есть по порядку объявления констант. Метод final, переопределить нельзя.

Можно ли расширить класс, добавив поле в compareTo? Корректно — нет, ломается антисимметричность. Используйте композицию.

Чек-лист "пишу `compareTo`"

implements Comparable<МойКласс> — с параметром типа, не сырой
Сравнение полей от самого значимого к наименее
Используются Integer.compare / Double.compare и аналоги, а не вычитание
Возвращается знак; нигде не сравниваю результат с -1 или 1
Проверена антисимметричность и транзитивность
Решено, согласован ли порядок с equals; если нет — задокументировано
Порядок полей описан в javadoc
Нет instanceof и проверок на null — дженерик и NPE справляются сами
Если класс наследуемый — обдумано ограничение из раздела 6

Что даёт реализация Comparable

Контракт compareTo

Обязательные условия

Настоятельная рекомендация (не требование)

Согласованность с equals — ключевой момент

Почему это критично

Канонический пример — BigDecimal

compareTo возвращает знак, а не -1/0/1