Comparator в Java

Про Comparator і порівняння в Java не писав лише лінивий. Я не лінивий — тож прошу любити і шанувати ще одну варіацію. Сподіваюся, вона буде не зайвою. І так, дана стаття відповідає на запитання: "Чи зможеш ти написати на згадку компаратор?" Сподіваюся, після прочитання цієї статті кожен зможе написати компаратор з пам'яті.

Вступ Java, як відомо, є об'єктно-орієнтованою мовою. Як наслідок - в Java прийнято оперувати об'єктами. Але рано чи пізно постає завдання порівняння об'єктів за якимось принципом. Отже, дано: У нас є деяке повідомлення, описане класом Message:

public static class Message {
    private String message;
    private int id;

    public Message(String message) {
        this.message = message;
        this.id = new Random().nextInt(1000);
    }
    public String getMessage() {
        return message;
    }
    public Integer getId() {
        return id;
    }
    public String toString() {
        return "[" + id + "] " + message;
    }
}

Додамо цей клас у Tutorialspoint java compiler . Не забудемо також додати імпорти:

import java.util.Random;
import java.util.ArrayList;
import java.util.List;

У main методі створимо кілька повідомлень:

public static void main(String[] args){
    List<Message> messages = new ArrayList();
    messages.add(new Message("Hello, World!"));
    messages.add(new Message("Hello, Sun!"));
    System.out.println(messages);
}

Давайте подумаємо, що нам робити, якщо ми хочемо їх порівняти? Наприклад, ми хочемо впорядкувати за id. А щоб створити порядок, потрібно якось порівняти об'єкти, щоб зрозуміти, який об'єкт попередній (тобто менший), а який наступний (тобто більший). Почнемо з такого класу, як java.lang.Object . Як ми знаємо, всі класи успадковуються неявним чином цього класу Object. І це логічно, т.к. насправді це висловлює сенс концепції: " Усе є об'єкт " і надає загальне поведінка всім класів. І цей клас визначає, що кожен клас має два методи: → hashCode Метод hashCode повертає деяке числове (int) уявлення об'єкта як екземпляра класу. Що це означає? Це означає, що якщо ви створабо два різні екземпляри класу, то так як екземпляри різні, то і hashCode у них мають бути різними. Так сказано й в описі до методу: "Як дуже вірно є практично практичний, у hashCode метод defined by class Object does return distinct integers for distinct objects" Тобто якщо це два різних instance, то у них повинні бути різні hashCode. Тобто для нашого порівняння цей метод не підійде. → equals Метод equals відповідає питанням " чи рівні об'єкти " і повертає boolean. Цей метод за замовчуванням має код:

public boolean equals(Object obj) {
    return (this == obj);
}

Тобто, не перевизначаючи даний метод у об'єкта, цей метод по суті говорить, чи збігаються посилання на об'єкт чи ні. Для наших повідомлень це не підійде, адже нас не цікавлять посилання на об'єкт, нас цікавить id повідомлення. І навіть якби ми перевизначабо метод equals, то максимум, що ми б отримали: "Вони рівні" або "Вони не рівні". А для визначення порядку нам цього замало.

Comparator і Comparable в Java

Що ж нам личить? Якщо ми в перекладачі перекладемо слово "порівняти" на англійську, то отримаємо переклад "compare". Відмінно, значить, нам потрібен той, хто порівнюватиме. Якщо порівнювати це compare, то той, хто порівнює – Comparator. Відкриємо Java Api і знайдемо там Comparator . Є такий інтерфейс - java.util.Comparator java.util.Comparator і java.lang.Comparable Як видно, існує такий інтерфейс. Клас, який його реалізує свідчить, що "Я реалізую функцію порівняння об'єктів". Єдине, що треба справді запам'ятати – це контракт компаратора, який виражається в наступному:


Comparator возвращает int по следующей схеме: 

отрицательный int (первый об'єкт отрицательный, то есть меньше)
положительный int (первый об'єкт положительный, хороший, то есть больший)
ноль = об'єкты равны

Тепер напишемо компаратора. Нам буде потрібно імпорт java.util.Comparator . Після імпорту додамо в main метод: Comparator<Message> comparator = new Comparator<Message>(); Звісно, це відпрацює, т.к. Comparator це інтерфейс. Тому після круглих дужок додамо фігурні { }. У цих дужках напишемо метод:

public int compare(Message o1, Message o2) {
    return o1.getId().compareTo(o2.getId());
}

Написання цього не треба навіть пам'ятати. Компаратор - це той, хто виконує порівняння, тобто робить compare. Щоб відповісти на питання, в якому порядку йдуть об'єкти, що порівнюються, ми повертаємо int. Ось і все, власне. Легко і просто. Як ми бачимо з прикладу, крім Comparator'а є ще один інтерфейс - java.lang.Comparable , реалізуючи який ми повинні визначити метод compareTo . Цей інтерфейс говорить, що "Клас, який реалізує інтерфейс, дозволяє порівнювати екземпляри класу". Наприклад, у Integer реалізація compareTo виглядає так:

(x < y) ? -1 : ((x == y) ? 0 : 1)

Як запам'ятати всі ці інтерфейси? А навіщо? Все йде від англійської. Compare - порівнювати, той хто порівнює - Comparator (як реєстратор, наприклад. Тобто той, хто реєструє), а прикметник "Comparable, що порівнюється". Ну а "порівняти з" перекладається не тільки як compare with, але і як compare to. Все просто. Мова Java писали адже англомовні люди і в назві всього Java вони керувалися просто англійською і в іменуванні була якась логіка. А метод compareTo описує те, як екземпляр класу потрібно порівнювати з іншими екземплярами. Наприклад, рядки порівнюються лексиграфічно , а числа порівнюються за значенням.

Java 8 внесла приємні зміни. Якщо придивитися до інтерфейсу Comparator, то ми побачимо, що над ним стоїть інструкція @FunctionalInterface. Насправді, ця інструкція для інформації і означає, що цей інтерфейс є функціональним. Це означає, що в цьому інтерфейсі є лише один абстрактний метод без реалізації. Що нам це дає? Ми можемо написати код компаратора тепер так:

Comparator<Message> comparator = (o1, o2) -> o1.getId().compareTo(o2.getId());

У дужках – те, як ми назвемо змінні. Java сама побачить, що т.к. Метод то лише один, то відомо які вхідні параметри необхідні, скільки, яких типів. Далі ми говоримо стрілочкою, що хочемо їх передати ось у цю ділянку коду. Крім того, завдяки Java 8 з'явабося default методи в інтерфейсах – це такі методи, які за умовчанням з'являються (за замовчуванням – by default), коли ми реалізуємо інтерфейс. В інтерфейсі Comparator таких кілька.

Comparator moreImportant = Comparator.reverseOrder();
Comparator lessImportant = Comparator.naturalOrder();

Є ще один метод, який зробить ваш код чистішим. Подивимося приклад вище, де ми описували наш компаратор. Що він робить? Адже він досить примітивний. Він просто бере об'єкт і дістає з нього якесь значення, яке є comparable. Наприклад, Integer реалізує comparable, тому ми змогли виконати compareTo на значеннях ID повідомлення. Цю просту функцію компаратора можна записати і так:

Comparator<Message> comparator = Comparator.comparing(obj -> obj.getId());

Тобто дослівно "У нас є Comparator, який порівнює так: бере об'єкти, дістає з них Comparable за допомогою методу getId(), порівнює через compareTo". І жодних страшних конструкцій більше. Ну і насамкінець, хочеться ще відзначити одну особливість. Компаратори можна поєднувати в ланцюжок. Наприклад:

Comparator<Message> comparator = Comparator.comparing(obj -> obj.getId());
comparator = comparator.thenComparing(obj -> obj.getMessage().length());

Застосування

Оголошення компаратора виявилося досить логічним, чи не так? Тепер треба подивитися, як його використовувати і в яких місцях. → Collections.sort (java.util.Collections) Звичайно, ми можемо сортувати колекції таким чином. Але не всі, а лише списки. І немає нічого незвичайного, т.к. саме список передбачає доступ до елемента за індексом. І це дозволяє елемент номер два поміняти місцями з елементом номер три. Тому й сортування таким чином є лише для списків:

Comparator<Message> comparator = Comparator.comparing(obj -> obj.getId());
Collections.sort(messages, comparator);

→ Arrays.sort (java.util.Arrays) Масиви також зручно сортувати. Знову, з тієї ж причини доступу до елементів за індексом. → Спадкоємці java.util.SortedSet та java.util.SortedMap Як ми пам'ятаємо, Set і Map не гарантують порядок зберігання записів. АЛЕ ми маємо спеціальні реалізації, які гарантують порядок. І якщо елементи колекції не реалізують java.lang.Comparable, ми в конструктор таких колекцій можемо передати Comparator:

Set<Message> msgSet = new TreeSet(comparator);

→ Stream API У Stream Api, які з'явабося в Java 8, компаратор дозволяє спрощувати роботу над елементами стриму. Наприклад, нам потрібна послідовність випадкових чисел від 0 до 999 включно:

Supplier<Integer> randomizer = () -> new Random().nextInt(1000);
Stream.generate(randomizer)
    .limit(10)
    .sorted(Comparator.naturalOrder())
    .forEach(e -> System.out.println(e));

Ми могли б і зупинитися, але є завдання цікавіше. Наприклад, потрібно підготувати Map, де ключ – id повідомлення. При цьому ми хочемо відсортувати ці ключі, щоб ключі йшли по порядку, від меншого до більшого. Почнемо з такого коду:

Map<Integer, Message> collected = Arrays.stream(messages)
                .sorted(Comparator.comparing(msg -> msg.getId()))
                .collect(Collectors.toMap(msg -> msg.getId(), msg -> msg));

Нам повернуть тут насправді HashMap. А як ми знаємо, вона не гарантує будь-який порядок. Тому наші відсортовані за ID запис просто втратабо порядок. Не добре. Прийде змінити трохи наш колектор:

Map<Integer, Message> collected = Arrays.stream(messages)
                .sorted(Comparator.comparing(msg -> msg.getId()))
                .collect(Collectors.toMap(msg -> msg.getId(), msg -> msg, (oldValue, newValue) -> oldValue, TreeMap::new));

Код став виглядати дещо страшнішим, але завдання тепер вирішено правильно завдяки явній вказівці реалізації карти TreeMap. Докладніше про різні групування можна прочитати тут:

Колектор можна створити самим. Докладніше можна прочитати тут: "Creating a custom collector in Java 8" . І корисно прочитати обговорення тут: "Java 8 list to map with stream" .

Граблі Comparator та Comparable це добре. Але з ними пов'язаний один аспект, про який варто пам'ятати. Коли клас виконує сортування, він розраховує, що можна привести Ваш клас до Comparable. Якщо це не так – у момент виконання ви отримаєте помилку. Подивимося на приклад:

SortedSet<Message> msg = new TreeSet<>();
msg.add(new Message(2, "Developer".getBytes()));

Здається, що нічого поганого тут немає. Але насправді на нашому прикладі він впаде з помилкою: java.lang.ClassCastException: Message cannot be cast to java.lang.Comparable А все тому, що він намагався відсортувати елементи (Адже SortedSet). І не зміг. Слід не забути про це під час роботи з SortedMap та SortedSet. Додатково Рекомендується до перегляду: Юрій Ткач: HashSet та TreeSet - Collections #1 - Advanced Java