Comparator в Java

Comparator в Java это интерфейс из пакета java.util, который задает правило сортировки объектов. В нем один абстрактный метод, compare(o1, o2): он возвращает отрицательное число, если первый объект должен идти раньше второго, положительное, если позже, и ноль, если для этого порядка объекты равны. Компаратор описывают отдельно от класса, поэтому одному и тому же типу можно задать сколько угодно разных порядков и передать нужный в Collections.sort, Arrays.sort, в конструктор TreeSet и TreeMap или в метод sorted() у стрима.

Кратко

• Comparator это внешнее правило сравнения. Метод compare(o1, o2) возвращает отрицательное число, ноль или положительное, и сортировка расставляет объекты по знаку результата.
• Comparable это внутреннее правило: класс сам реализует compareTo() и получает один естественный порядок на все случаи.
• К одному классу можно написать сколько угодно компараторов, а Comparable у него только один.
• Comparator помечен аннотацией @FunctionalInterface, поэтому с Java 8 его пишут лямбдой в одну строку.
• Готовые компараторы собирают статическими методами comparing(), naturalOrder() и reverseOrder(), а объединяют в цепочку default-методом thenComparing().
• Компаратор передают в Collections.sort, Arrays.sort, в конструктор TreeSet и TreeMap и в метод sorted() у стрима. Без него в TreeSet попадут только классы, реализующие Comparable.

Про 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;
    }
}

Добавим данный класс в любой онлайн-компилятор Java или просто в свою IDE. Не забудем также добавить импорты:

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 far as is reasonably practical, the hashCode method defined by class Object returns 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 описывает то, каким образом экземпляр класса нужно сравнивать с другими экземплярами. Например, строки сравниваются лексикографически, а числа сравниваются по значению.

Comparator и Comparable: в чем разница

Оба интерфейса про сравнение, но подходят к нему с разных сторон. Разница удобно видна рядом:

Comparator и Java 8: лямбда вместо анонимного класса

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();

naturalOrder() дает естественный порядок (числа по возрастанию, строки лексикографически), а reverseOrder() обратный ему. Оба вызываются у самого интерфейса, потому что оба статические. А вот reversed() и thenComparing(), про который речь пойдет ниже, это уже default-методы: их вызывают у готового компаратора. Есть и еще один метод, который сделает ваш код чище. Посмотрим на пример выше, где мы описывали наш компаратор. Что он делает? Он ведь довольно примитивный. Он просто берет объект и достает из него какое-то значение, которое 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 = messages.stream()
                .sorted(Comparator.comparing(msg -> msg.getId()))
                .collect(Collectors.toMap(msg -> msg.getId(), msg -> msg));

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

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

Код стал выглядеть несколько страшнее, но задача теперь решена правильно благодаря явному указанию реализации карты TreeMap. Подробнее про группировку и остальные сборщики написано в документации класса java.util.stream.Collectors: там перечислены и groupingBy, и partitioningBy, и все перегрузки toMap. Коллектор можно создать самим. Подробнее можно прочитать здесь: "Creating a custom collector in Java 8". И полезно прочитать обсуждение здесь: "Java 8 list to map with stream".

Что изменилось после Java 8

Статья писалась во времена восьмерки, и главное с тех пор не поменялось: Comparator это все тот же функциональный интерфейс с методом compare. А вот вокруг него набралось несколько удобств, из-за которых современный код выглядит короче.

Ссылка на метод вместо лямбды

Лямбда obj -> obj.getId() ничего не делает сама, она только вызывает чужой метод. Для такого случая есть ссылка на метод, и компаратор из примеров выше сжимается до одной строки:

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

Читается почти как предложение: сравнивать сообщения по getId.

Рекорды вместо классов-данных

Класс Message из начала статьи занимает восемнадцать строк, а хранит всего два поля: почти весь объем это конструктор, геттеры и toString. С Java 16 для такой задачи есть рекорды (JEP 395), и весь класс сворачивается вот во что:

public record Message(int id, String message) {
    public Message(String message) {
        this(new Random().nextInt(1000), message);
    }
}

Геттеры, equals, hashCode и toString рекорд напишет за вас. Две оговорки. Методы доступа он называет по именам полей, без приставки get, поэтому и компаратор будет ссылаться на Message::id, а не на Message::getId. А сгенерированный toString печатает в своем формате, Message[id=42, message=Hello, World!], так что авторский вариант с квадратными скобками пришлось бы дописать руками.

list.sort вместо Collections.sort

Еще в Java 8 метод сортировки появился у самого списка, так что вызов из раздела выше можно записать короче:

messages.sort(comparator);

Разница тут чисто стилистическая. Документация Collections.sort прямо говорит, что старый метод просто перекладывает работу на новый: «This implementation defers to the List.sort(Comparator) method using the specified list and comparator».

reversed() у SortedSet и SortedMap

JEP 431, вышедший в Java 21, добавил в коллекции интерфейсы SequencedCollection, SequencedSet и SequencedMap, а вместе с ними метод reversed(). Он есть и у SortedSet, и у SortedMap, так что перевернуть порядок теперь можно прямо у коллекции:

SortedSet<Message> sorted = new TreeSet<>(comparator);
SortedSet<Message> backwards = sorted.reversed();

Важно, что reversed() отдает не копию, а представление поверх той же коллекции: добавили элемент в одну, он появился и в другой.

Грабли

Comparator и Comparable это хорошо. Но с ними связан один нюанс, про который стоит помнить. Когда класс выполняет сортировку, то он рассчитывает, что можно привести Ваш класс к Comparable. Если это не так - в момент выполнения вы получите ошибку. Посмотрим на пример:

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

Кажется, что ничего плохого тут нет. Но на самом деле на нашем примере он упадет с ошибкой: java.lang.ClassCastException: class Message cannot be cast to class java.lang.Comparable (Message is in unnamed module of loader 'app'; java.lang.Comparable is in module java.base of loader 'bootstrap') А все потому, что он пытался отсортировать элементы (Он ведь SortedSet). И не смог. Длинный хвост в скобках появился в Java 9: сообщение теперь договаривает, из каких модулей и какими загрузчиками взяты оба класса. Следует не забыть про это при работе с SortedMap и SortedSet.

Дополнительно

Рекомендуется к просмотру: Юрий Ткач : HashSet и TreeSet - Collections #1 - Advanced Java

Вопросы и ответы

Чем Comparator отличается от Comparable?

Comparable это интерфейс из пакета java.lang, который класс реализует сам: он определяет метод compareTo(other) и задает своему типу один естественный порядок. Comparator это интерфейс из java.util, он живет отдельно от класса и определяет метод compare(o1, o2). Естественный порядок у класса может быть только один, а компараторов к одному и тому же классу пишут сколько угодно: по id, по длине текста, по дате. И только компаратор выручает, когда исходники класса менять нельзя.

Что должен возвращать метод compare?

Целое число, причем важен только его знак. Отрицательное значение означает, что первый аргумент меньше второго и должен идти раньше, положительное, что первый больше и идет позже, ноль, что для этого порядка объекты равны. Конкретная величина роли не играет: и -1, и -1000 значат для сортировки одно и то же.

Как отсортировать объекты сразу по нескольким полям?

Компараторы объединяются в цепочку методом thenComparing(). Сначала пишут главный критерий, потом дополнительный: Comparator.comparing(Message::getId).thenComparing(msg -> msg.getMessage().length()). Второй компаратор включается только там, где первый вернул ноль, то есть посчитал объекты равными. Звеньев в цепочке может быть сколько угодно.

Как отсортировать в обратном порядке?

Есть два способа. У готового компаратора вызвать default-метод reversed(). Или взять статический Comparator.reverseOrder(), если объекты уже реализуют Comparable и нужен просто перевернутый естественный порядок. Писать отдельный компаратор с переставленными аргументами не нужно.

Почему TreeSet падает с ClassCastException?

TreeSet и TreeMap хранят элементы упорядоченно, поэтому им обязательно нужно правило сравнения. Если в конструктор не передали компаратор, коллекция пытается привести элемент к Comparable. Класс, который этот интерфейс не реализует, приведение не переживет, и ошибка прилетит уже на первом добавлении. Лечится двумя способами: реализовать Comparable в самом классе или передать Comparator в конструктор коллекции.

Почему Collections.sort работает не со всеми коллекциями?

Метод Collections.sort принимает List, а не любую коллекцию. Сортировка меняет элементы местами, а для этого нужен доступ по индексу, которого у Set и Map нет. Для упорядоченного хранения в них есть отдельные реализации, TreeSet и TreeMap. С Java 8 метод sort() есть и у самого списка, а Collections.sort просто вызывает его.

Читайте также

• Метод compareTo
• Коротко о главном: Java Collections Framework
• HashSet в Java
• Ответы на самые популярные вопросы об интерфейсе Map