«Руководство по реализации метода compareTo»

«1. Обзор

Как Java-разработчикам, нам часто приходится сортировать элементы, сгруппированные в коллекцию. Java позволяет нам реализовать различные алгоритмы сортировки с любым типом данных.

Например, мы можем сортировать строки в алфавитном порядке, в обратном алфавитном порядке или по длине.

В этом уроке мы рассмотрим интерфейс Comparable и его метод compareTo, который включает сортировку. Мы рассмотрим сортировку коллекций, содержащих объекты как из основных, так и из пользовательских классов.

Мы также упомянем правила правильной реализации compareTo, а также неверный шаблон, которого следует избегать.

2. Интерфейс Comparable

Интерфейс Comparable упорядочивает объекты каждого класса, который его реализует.

CompareTo — единственный метод, определяемый интерфейсом Comparable. Его часто называют методом естественного сравнения.

2.1. Реализация compareTo

Метод compareTo сравнивает текущий объект с объектом, отправленным в качестве параметра.

При его реализации нам нужно убедиться, что метод возвращает:

Положительное целое число, если текущий объект больше объекта параметра Отрицательное целое число, если текущий объект меньше объекта параметра Ноль, если текущий объект равен объекту-параметру

В математике мы называем это знаком или сигнум-функцией:

2.2. Пример реализации

Давайте посмотрим, как реализован метод compareTo в базовом классе Integer:

@Override
public int compareTo(Integer anotherInteger) {
    return compare(this.value, anotherInteger.value);
}

public static int compare (int x, int y) {
    return (x < y) ? -1 : ((x == y) ? 0 : 1);
}

2.3. Сломанный шаблон вычитания

Кто-то может возразить, что вместо этого мы можем использовать хитрое однострочное вычитание:

@Override
public int compareTo(BankAccount anotherAccount) {
    return this.balance - anotherAccount.balance;
}

Давайте рассмотрим пример, в котором мы ожидаем, что положительный баланс счета будет больше, чем отрицательный:

BankAccount accountOne = new BankAccount(1900000000);
BankAccount accountTwo = new BankAccount(-2000000000);
int comparison = accountOne.compareTo(accountTwo);
assertThat(comparison).isNegative();

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

Правильное решение — использовать сравнение вместо вычитания. Мы также можем повторно использовать правильную реализацию из основного класса Integer:

@Override
public int compareTo(BankAccount anotherAccount) {
    return Integer.compare(this.balance, anotherAccount.balance);
}

2.4. Правила реализации

Чтобы правильно реализовать метод compareTo, нам необходимо соблюдать следующие математические правила:

sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) (x. compareTo(y) \u003e 0 \u0026\u0026 y.compareTo(z) \u003e 0) подразумевает x.compareTo(z) \u003e 0 x.compareTo(y) == 0 подразумевает, что sgn(x.compareTo(z)) == sgn(y .compareTo(z))

Также настоятельно рекомендуется, хотя и не обязательно, чтобы реализация compareTo соответствовала реализации метода equals:

x.compareTo(e2) == 0 должно иметь то же логическое значение, что и x.equals(y)

Это гарантирует, что мы сможем безопасно использовать объекты в отсортированных наборах и отсортированных картах.

2.5. Непротиворечивость с equals

Давайте посмотрим, что может произойти, когда реализации compareTo и equals не согласованы.

В нашем примере метод compareTo проверяет забитые голы, а метод equals проверяет имя игрока:

@Override
public int compareTo(FootballPlayer anotherPlayer) {
    return this.goalsScored - anotherPlayer.goalsScored;
}

@Override
public boolean equals(Object object) {
    if (this == object)
        return true;
    if (object == null || getClass() != object.getClass())
        return false;
    FootballPlayer player = (FootballPlayer) object;
    return name.equals(player.name);
}

Это может привести к неожиданному поведению при использовании этого класса в отсортированных наборах или отсортированных картах: ~~ ~

FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 800);

TreeSet<FootballPlayer> set = new TreeSet<>();
set.add(messi);
set.add(ronaldo);

assertThat(set).hasSize(1);
assertThat(set).doesNotContain(ronaldo);

Отсортированный набор выполняет все сравнения элементов, используя метод compareTo, а не метод equals. Таким образом, два игрока кажутся эквивалентными с его точки зрения, и он не добавит второго игрока.

3. Сортировка коллекций

Основное назначение интерфейса Comparable — обеспечить естественную сортировку элементов, сгруппированных в коллекции или массивы.

Мы можем отсортировать все объекты, которые реализуют Comparable, используя служебные методы Java Collections.sort или Arrays.sort.

3.1. Основные классы Java

Большинство основных классов Java, таких как String, Integer или Double, уже реализуют интерфейс Comparable.

Таким образом, сортировать их очень просто, поскольку мы можем повторно использовать их существующую естественную реализацию сортировки.

Сортировка чисел в их естественном порядке приведет к возрастанию:

int[] numbers = new int[] {5, 3, 9, 11, 1, 7};
Arrays.sort(numbers);
assertThat(numbers).containsExactly(1, 3, 5, 7, 9, 11);

С другой стороны, естественная сортировка строк приведет к алфавитному порядку:

String[] players = new String[] {"ronaldo",  "modric", "ramos", "messi"};
Arrays.sort(players);
assertThat(players).containsExactly("messi", "modric", "ramos", "ronaldo");

3.2. Пользовательские классы

«Напротив, для сортировки любых пользовательских классов нам необходимо вручную реализовать интерфейс Comparable.

Компилятор Java выдаст ошибку, если мы попытаемся отсортировать набор объектов, которые не реализуют Comparable.

Если мы попробуем то же самое с массивами, то при компиляции не будет сбоя. Однако это приведет к исключению времени выполнения приведения класса:

HandballPlayer duvnjak = new HandballPlayer("Duvnjak", 197);
HandballPlayer hansen = new HandballPlayer("Hansen", 196);
HandballPlayer[] players = new HandballPlayer[] {duvnjak, hansen};
assertThatExceptionOfType(ClassCastException.class).isThrownBy(() -> Arrays.sort(players));

3.3. TreeMap и TreeSet

TreeMap и TreeSet — это две реализации Java Collections Framework, которые помогают нам с автоматической сортировкой их элементов.

Мы можем использовать объекты, реализующие интерфейс Comparable, в отсортированной карте или как элементы в отсортированном наборе.

Давайте рассмотрим пример пользовательского класса, который сравнивает игроков по количеству забитых ими голов:

@Override
public int compareTo(FootballPlayer anotherPlayer) {
    return Integer.compare(this.goalsScored, anotherPlayer.goalsScored);
}

В нашем примере ключи автоматически сортируются на основе критериев, определенных в реализации compareTo: ~~ ~

FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 900);
FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer modric = new FootballPlayer("modric", 100);

Map<FootballPlayer, String> players = new TreeMap<>();
players.put(ronaldo, "forward");
players.put(messi, "forward");
players.put(modric, "midfielder");

assertThat(players.keySet()).containsExactly(modric, messi, ronaldo);

4. Альтернативный компаратор

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

Интерфейс Comparator позволяет использовать несколько различных стратегий сравнения, не связанных с сортируемыми объектами:

FootballPlayer ronaldo = new FootballPlayer("Ronaldo", 900);
FootballPlayer messi = new FootballPlayer("Messi", 800);
FootballPlayer modric = new FootballPlayer("Modric", 100);

List<FootballPlayer> players = Arrays.asList(ronaldo, messi, modric);
Comparator<FootballPlayer> nameComparator = Comparator.comparing(FootballPlayer::getName);
Collections.sort(players, nameComparator);

assertThat(players).containsExactly(messi, modric, ronaldo);

Обычно это также хороший выбор, когда мы не хотим или не можем изменять исходный код объекта. объекты, которые мы хотим отсортировать.

5. Заключение

В этой статье мы рассмотрели, как мы можем использовать интерфейс Comparable для определения естественного алгоритма сортировки для наших классов Java. Мы рассмотрели общий сломанный шаблон и определили, как правильно реализовать метод compareTo.

Мы также исследовали коллекции сортировки, которые содержат как базовые, так и пользовательские классы. Далее мы рассмотрели реализацию метода compareTo в классах, используемых в отсортированных множествах и отсортированных картах.

Наконец, мы рассмотрели несколько вариантов использования, когда вместо этого следует использовать интерфейс Comparator.

Как всегда, исходный код доступен на GitHub.