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 у них должны быть разными. Так сказано и в описании к методу: "As much as is reasonably practical, the hashCode method 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. На самом деле, эта аннотация для информации и означает, что данный интерфейс является функциональным. Это значит, что в этом интерфейсе есть всего 1 абстрактный метод без реализации. Что это нам даёт? Мы можем написать код компаратора теперь вот так:

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. Подробнее про различные группирования можно прочитать здесь:

• Java 8 Stream collect grouping
• Java 8 – Stream Collectors groupingBy examples

Коллектор можно создать самим. Подробнее можно прочитать здесь: "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). И не смог. Cледует не забыть про это при работе с SortedMap и SortedSet. Дополнительно Рекомендуется к просмотру: Юрий Ткач : HashSet и TreeSet - Collections #1 - Advanced Java