Що таке Comparable та Comparator

Інтерфейси Comparable та Comparator використовуються в Java для порівняння та сортування об'єктів, але розв'язують це завдання на різних архітектурних рівнях:

🟢 Junior Level

1. У чому різниця: просте пояснення

Інтерфейси Comparable та Comparator використовуються в Java для порівняння та сортування об’єктів, але розв’язують це завдання на різних архітектурних рівнях:

Comparable («Порівнюваний сам по собі»): реалізується всередині самого класу сутності. Визначає його природний порядок сортування за замовчуванням (Natural Ordering).
Comparator («Зовнішній суддя / Порівнювач»): створюється як окремий клас або лямбда-вираз. Дозволяє реалізувати довільну кількість альтернативних стратегій сортування без модифікації вихідного класу.

// 1. Використання Comparable (природний порядок за ID)
class Employee implements Comparable<Employee> {
    private int id;
    private String name;

    public Employee(int id, String name) { this.id = id; this.name = name; }

    @Override
    public int compareTo(Employee other) {
        return Integer.compare(this.id, other.id); // Порівняння за числовим ID
    }
}

List<Employee> list = new ArrayList<>();
Collections.sort(list); // Сортує за natural order (через compareTo)

// 2. Використання Comparator (альтернативний порядок за ім'ям)
Comparator<Employee> byName = (e1, e2) -> e1.name.compareTo(e2.name);
list.sort(byName); // Сортує за ім'ям

2. Зведена таблиця відмінностей

Характеристика	`Comparable<T>`	`Comparator<T>`
Пакет	`java.lang`	`java.util`
Метод інтерфейсу	`int compareTo(T o)`	`int compare(T o1, T o2)`
Де реалізується	Усередині порівнюваного класу	В окремому класі, анонімному класі або лямбді
Кількість стратегій	Тільки одна (порядок за замовчуванням)	Необмежено багато
Модифікація класу	Вимагає доступу до вихідного коду	Не вимагає (працює зі сторонніми класами)
Виклик сортування	`Collections.sort(list)`	`list.sort(comparator)`

🟡 Middle Level

1. Функціональний API комбінаторів (Java 8+)

У Java 8 Comparator став функціональним інтерфейсом і отримав багатий набір статичних фабричних методів та комбінаторів, які дозволяють будувати складні багаторівневі правила сортування декларативно:

List<Employee> staff = getEmployees();

// Ланцюжок порівнянь: спочатку за прізвищем, потім за ім'ям, далі за спаданням зарплати:
Comparator<Employee> complexComparator = Comparator
    .comparing(Employee::getLastName)
    .thenComparing(Employee::getFirstName)
    .thenComparingDouble(Employee::getSalary).reversed();

staff.sort(complexComparator);

Безпечна обробка значень `null`:

// Розміщення null-значень на самому початку або наприкінці списку:
Comparator<Employee> safeComparator = Comparator.comparing(
    Employee::getName, 
    Comparator.nullsLast(String::compareTo)
);

2. Смертельна пастка: арифметичне віднімання чисел у компараторі

Один із найбільш небезпечних класичних багів у Java-коді — використання арифметичного віднімання замість методів порівняння:

// ❌ ГРУБА ПОМИЛКА (Integer Overflow / Underflow):
Comparator<User> badComparator = (u1, u2) -> u1.id - u2.id;

Чому це ламає алгоритм сортування: Якщо u1.id = -2_000_000_000, а u2.id = 1_000_000_000, операція віднімання поверне: -2_000_000_000 - 1_000_000_000 = -3_000_000_000. Значення виходить за межі діапазону 32-бітного знакового int (Integer.MIN_VALUE = -2_147_483_648), відбувається цілочисельне переповнення, і результат виразу стає додатним числом 1_294_967_296! Компаратор помилково стверджує, що $u1 > u2$, що призводить до хаотичного сортування.

[!TIP] Завжди використовуйте статичні методи порівняння примітивів: Integer.compare(a, b), Long.compare(a, b), Double.compare(a, b) або спеціалізовані методи Comparator.comparingInt(), Comparator.comparingLong().

🔴 Senior Level

1. Суворий математичний контракт та виняток Timsort

Сортування колекцій об’єктів у Java реалізовано на алгоритмі Timsort (високоефективний гібрид сортування вставками та сортування злиттям). Timsort спирається на аксіоми математичного відношення строгого порядку. Компаратор зобов’язаний дотримуватися наступних властивостей:

Антисиметричність: $\operatorname{sgn}(\operatorname{compare}(x, y)) == -\operatorname{sgn}(\operatorname{compare}(y, x))$.
Транзитивність: якщо $\operatorname{compare}(x, y) > 0$ і $\operatorname{compare}(y, z) > 0$, то обов’язково $\operatorname{compare}(x, z) > 0$.
Транзитивність еквівалентності: якщо $\operatorname{compare}(x, y) == 0$ і $\operatorname{compare}(y, z) == 0$, то $\operatorname{compare}(x, z) == 0$.

Як спричинити аварійний збій Timsort:

Якщо компаратор порушує базову антисиметричність або рефлексивність:

// ❌ ПОРУШЕННЯ АНТИСИМЕТРИЧНОСТІ:
// Для двох рівних елементів повертає -1 замість 0!
Comparator<Integer> broken = (a, b) -> a > b ? 1 : -1;

При запуску list.sort(broken) на наборі даних від 32 елементів алгоритм Timsort виявить математичну суперечність у межах відсортованих серій (Run boundaries) і викине виняток: java.lang.IllegalArgumentException: Comparison method violates its general contract!

2. Узгодженість із `equals()` та поведінка в `TreeSet` / `TreeMap`

Офіційна специфікація інтерфейсу Comparable наполегливо рекомендує дотримуватися узгодженості з методом equals:

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

Якщо цей контракт порушено, деревоподібні колекції (TreeSet, TreeMap) демонструють аномальну поведінку:

TreeSet та TreeMap ніколи не викликають equals(); вони визначають еквівалентність ключів виключно за умовою compareTo(a, b) == 0.
Якщо у двох різних об’єктів compareTo() == 0, другий об’єкт буде проігноровано деревом як дублікат, навіть якщо за бізнес-логікою equals() вони абсолютно різні.

3. Оптимізація GC: примітивні компаратори

Під час сортування великих колекцій (мільйони записів) використання узагальнених об’єктних методів спричиняє масовий автобоксинг:

// ❌ Боксинг: гетер повертає int, boxing загортає в Integer, Comparator розпаковує:
Comparator.comparing(User::getAge);

// ✅ Нуль алокацій: метод comparingInt працює безпосередньо з примітивними регістрами:
Comparator.comparingInt(User::getAge);

Використання comparingInt() або comparingLong() повністю усуває створення тимчасових об’єктів у Heap і прискорює сортування на 30–50%.

🎯 Шпаргалка для інтерв’ю

30-секундна відповідь (Elevator Pitch)

«Comparable задає природний порядок сортування класу за замовчуванням (Natural Order) через єдиний метод compareTo(T o) усередині самого класу. Comparator — це зовнішній функціональний інтерфейс compare(T o1, T o2), який дозволяє створювати довільну кількість стратегій сортування за допомогою лямбда-виразів та комбінаторів (comparing, thenComparing). При написанні компараторів суворо заборонено використовувати арифметичне віднімання чисел o1.id - o2.id через ризик цілочисельного переповнення — слід використовувати Integer.compare(). Порушення математичного контракту компаратора призведе до викидання IllegalArgumentException в алгоритмі Timsort».

3 каверзних запитання з інтерв’ю та відповіді

1. Чому компаратор `(a, b) -> a > b ? 1 : -1` викине `IllegalArgumentException` при сортуванні списку зі 100 елементів?

Відповідь: Цей компаратор грубо порушує властивість рефлексивності та антисиметричності: для двох рівних значень ($a == b$) він повертає -1 замість 0. Виникає парадокс: одночасно $a < b$ і $b < a$. Під час злиття підмасивів в алгоритмі Timsort стек серій упорядкування виявляє внутрішню суперечність і захищає колекцію викиданням java.lang.IllegalArgumentException: Comparison method violates its general contract!.

2. У чому різниця між `Collections.sort(list, comparator)` та `list.sort(comparator)` у Java 8+?

Відповідь: Починаючи з Java 8, метод Collections.sort() просто делегує виконання методу list.sort(). У класі ArrayList метод list.sort(c) сортує внутрішній масив elementData безпосередньо на місці (in-place) через Arrays.sort(). Це відчутно швидше за реалізацію Java 7, яка спочатку копіювала елементи в тимчасовий масив, сортувала його і потім перезаписувала список за допомогою ListIterator.

3. Що станеться, якщо додати об’єкт у `TreeSet`, якщо його клас НЕ реалізує `Comparable`, і компаратор у конструктор переданий не був?

Відповідь: При спробі додати елемент treeSet.add(e) у сучасних версіях Java (починаючи з Java 7) відбувається спроба явного приведення типу ((Comparable<? super K>) key).compareTo(...). Оскільки клас не реалізує інтерфейс, буде негайно викинуто виняток ClassCastException.

Типові помилки та Red Flags

❌ Використання арифметичного віднімання в compare: Призводить до переповнення числових типів та непередбачуваного порядку сортування.
❌ Повернення -1 замість 0 для рівних елементів: Порушує антисиметричність і ламає Timsort.
❌ Неузгодженість compareTo() та equals(): Спричиняє мовчазну втрату даних у TreeSet та TreeMap.
❌ Ігнорування значень null: Виклик o1.compareTo(o2) при o1 == null викине NullPointerException; слід використовувати Comparator.nullsFirst() або nullsLast().