Java Comparator Interface
Java Comparator interface is used to sort an array or List of objects based on custom sort order. The custom ordering of items is imposed by implementing Comparator’s compare() method in the objects.
1. When to Use Comparator Interface
Java Comparator interface imposes a total ordering on the objects which may not have a desired natural ordering.
For example, for a List of Employee objects, the natural order may be ordered by employee’s id. But in real-life applications, we may want to sort the list of employees by their first name, date of birth or simply any other such criteria. In such conditions, we need to use Comparator interface.
We can use the Comparator interface in the following situations.
- Sorting the array or list of objects, but NOT in natural order.
- Sorting the array or list of objects where we can not modify the source code to implement Comparable interface.
- Using group by sort on list or array of objects on multiple different fields.
2. Overriding compare() Method
To enable total ordering on objects, we need to create a class that implements the Comparator interface. Then we need to override its compare(T o1, T o2) method.
The compare() compares its two arguments for order. It returns a negative integer, zero, or a positive integer as the first argument is less than, equal to, or greater than the second.
The implementor must also ensure that the relation is transitive: ((compare(x, y)>0) && (compare(y, z)>0)) implies compare(x, z)>0 .
For a given Employee class, the order by employee name can be imposed by creating a Comparator like below.
import java.util.Comparator; public class NameSorter implements Comparator < @Override public int compare(Employee e1, Employee e2) < return e1.getName().compareToIgnoreCase( e2.getName() ); >>import java.time.LocalDate; public class Employee
3.1. Collections.sort() and Arrays.sort()
- Use Collections.sort(list, Comparator) method sort a list of objects in order imposed by provided comparator instance.
- Use Arrays.sort(array, Comparator) method sort an array of objects in order imposed by provided comparator instance.
This utility method accepts a function that extracts a sort key for the class. This is essentially a field on which the class objects will be sorted.
//Order by name Comparator.comparing(Employee::getName); //Order by name in reverse order Comparator.comparing(Employee::getName).reversed(); //Order by id field Comparator.comparing(Employee::getId); //Order by employee age Comparator.comparing(Employee::getDate);This utility method is used for group by sort. Using this method, we can chain multiple comparators to sort the list or array of objects on multiple fields.
It is very similar to SQL GROUP BY clause to order rows on different fields.
//Order by name and then by age Comparator.comparing(Employee::getName) .thenComparing(Employee::getDob); //Order by name -> date of birth -> id Comparator.comparing(Employee::getName) .thenComparing(Employee::getDob) .thenComparing(Employee::getId);Using the above syntax, we can create virtually any sorting logic.
This utility method returns a comparator that imposes the reverse of the natural ordering or total ordering on a collection of objects that implement the Comparable interface.
//Reverse of natural order as specified in //Comparable interface's compareTo() method Comparator.reversed(); //Reverse of order by name Comparator.comparing(Employee::getName).reversed();3.5. Other Collection Classes
Comparators can also be used to control the order of certain data structures (such as sorted sets or sorted maps) to provide an ordering that is not natural ordering.
SortedSet sortedUniqueEmployees = new TreeSet(new NameSorter());4. Java Comparator Examples
4.1. Sorting List of Custom Objects
Java example to sort a list of employees by name using Comparator.
ArrayList list = new ArrayList<>(); //Sort in reverse natural order Collections.sort(list, new NameSorter());4.2. Sort List in Reverse Order
Java example to sort a list of employees by name using Comparator in reverse order.
ArrayList list = new ArrayList<>(); Collections.sort(list, Comparator.comparing( Employee::getName ).reversed());Java example to sort a list of employees on multiple fields i.e. field by field.
ArrayList list = new ArrayList<>(); Comparator groupByComparator = Comparator.comparing(Employee::getName) .thenComparing(Employee::getDob) .thenComparing(Employee::getId); Collections.sort(list, groupByComparator);In this tutorial, we learned about Comparator interface of Java collection framework. It helps in imposing a total order on objects without any change to the source code of that class.
We learned to sort list and array of custom objects. We also learned to reverse sort and implement group by sort in Java.
Пишите компараторы правильно
В Java для введения порядка среди определённых объектов можно написать компаратор — класс, содержащий функцию compare , которая сравнивает два объекта. Альтернативой компаратору является естественный порядок объектов: объект реализует интерфейс Comparable , который содержит метод compareTo , позволяющий сравнить этот объект с другим. Сравнивающая функция должна вернуть 0, если объекты равны, отрицательное число (обычно -1), если первый объект меньше второго, и положительное число (обычно 1), если первый больше. Обычно реализация такой функции не представляет сложностей, но имеется один случай, о котором многие забывают.
Сравнение используется различными алгоритмами от сортировки и двоичного поиска до поддержания порядка в сортированных коллекциях вроде TreeMap . Эти алгоритмы завязаны на три важных свойства сравнивающей функции: рефлексивность (сравнение элемента с самим собой всегда даёт 0), антисимметричность (сравнение A с B и B с A должны дать разный знак) и транзитивность (если сравнение A с B и B с C выдаёт одинаковый знак, то и сравнение A с C должно выдать такой же). Если сравнивающая функция не удовлетворяет этим свойствам, алгоритм может выдать совершенно непредсказуемый результат. Причём скорее всего вы не получите никакого исключения, просто результат будет неверный.
Как обнаружилось, несоблюдение этих свойств — не такая уж редкая ситуация. Проблема возникает при сравнении вещественных чисел — float или double.
Предположим, у нас имеется класс с полем типа double, и мы хотим упорядочивать объекты этого класса в зависимости от значения поля. Нередко можно встретить такой код:
public class DoubleHolder implements Comparable < double d; public DoubleHolder(double d) < this.d = d; >@Override public int compareTo(DoubleHolder o) < return d >o.d ? 1 : d == o.d ? 0 : -1; > @Override public String toString() < return String.valueOf(d); >>У приведённого метода compareTo есть две проблемы. Первая — незначительная — он не различает +0.0 и -0.0: new DoubleHolder(-0.0).compareTo(new DoubleHolder(+0.0)) вернёт 0. Иногда это нестрашно, но в случае сортировки элементы с +0.0 и -0.0 расположатся в произвольном порядке, что будет смотреться некрасиво. Тем не менее, всё это мелочи по сравнению с NaN. Число NaN (как в типе double, так и во float) — это довольно специфичная вещь. Оно не больше, не меньше и не равно никакому другому числу. В результате мы сразу получаем нарушение свойств сравнения:
DoubleHolder nan = new DoubleHolder(Double.NaN); DoubleHolder zero = new DoubleHolder(0.0); System.out.println("nan.compareTo(nan): "+nan.compareTo(nan)); System.out.println("nan.compareTo(zero): "+nan.compareTo(zero)); System.out.println("zero.compareTo(nan): "+zero.compareTo(nan));nan.compareTo(nan): -1 nan.compareTo(zero): -1 zero.compareTo(nan): -1Ни рефлексивности, ни антисимметричности не наблюдается. Можно встретить и такую реализацию сравнения:
public int compareTo(DoubleHolder o) < return d >o.d ? 1 : d
Здесь все три предыдущих сравнения выдадут ноль, то есть как будто бы свойства соблюдаются. Но, конечно, радоваться рано:
DoubleHolder nan = new DoubleHolder(Double.NaN); DoubleHolder zero = new DoubleHolder(0.0); DoubleHolder one = new DoubleHolder(1.0); System.out.println("zero.compareTo(nan): "+zero.compareTo(nan)); System.out.println("nan.compareTo(one): "+nan.compareTo(one)); System.out.println("zero.compareTo(one): "+zero.compareTo(one)); zero.compareTo(nan): 0 nan.compareTo(one): 0 zero.compareTo(one): -1Здесь нарушается транзитивность: первый объект равен второму, второй равен третьему, но первый третьему не равен.
Чем же это грозит простому обывателю? Чтобы понять это, создадим простой список и попробуем его перемешать и посортировать несколько раз:
List data = new ArrayList<>(); for(int i=1; i data.add(new DoubleHolder(Double.NaN)); for(int i=0; i
[NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, NaN, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, NaN, 1.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 10.0, NaN, 9.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, NaN, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0][1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 8.0, 9.0, NaN, 7.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 9.0, 10.0, NaN, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN] [2.0, 6.0, NaN, 1.0, 3.0, 4.0, 5.0, 7.0, 8.0, 9.0, 10.0] [2.0, 4.0, NaN, 1.0, 3.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 3.0, NaN, 2.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0] [1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, 10.0, NaN]Примерно в половине случаев элемент с NaN прибивается к началу или концу сортируемого списка, а в других случаях начинает блуждать, портя порядок окружающих элементов.
С коллекциями, использующими DoubleHolder в качестве ключа, тоже ничего хорошего не произойдёт. Возьмём, к примеру, TreeSet . Со второй реализацией compareTo всё довольно просто: так как элемент, содержащий NaN, равен любому другому, то в непустое множество вставить его не получится, потому что оно решит, что такой элемент уже есть. Но берегитесь, если вы вставили NaN-элемент первым: после этого во множество не выйдет добавить ничего другого.
Первый вариант сравнивающей функции психоделичнее. Напишем, например, такой тест:
Set set = new TreeSet<>(); for(int i=0; i System.out.println(set);Мы вставили по пять элементов, содержащих NaN, и по пять элементов, содержащих каждую цифру от 1 до 9. В результате имеем следующее:
[NaN, NaN, 1.0, 2.0, 3.0, NaN, NaN, 1.0, 2.0, 3.0, 4.0, 5.0, 6.0, 7.0, 8.0, 9.0, NaN]Вполне ожидаемо увидеть пять раз NaN: ведь они не равны друг другу. Но из-за неправильных сравнений и некоторые другие элементы вставились по нескольку раз. Можете сами посмотреть, что случится с TreeMap. Заметьте, что один случайно попавший NaN может испортить всю коллекцию, причём это не всегда легко отладить: коллекция может долго существовать в некорректном состоянии и делать вид, что всё нормально.
Что любопытно, этой проблемы вообще не должно существовать. Ещё в JDK 1.4 появились специальные статические методы Float.compare и Double.compare, которые сделают всё за вас, корректно обработав специальные случаи. Надо лишь написать:
public int compareTo(DoubleHolder o)
Видимо, сказывается обманчивая простота алгоритма сравнения: порой программист считает, что проще написать самому, чем искать в документации стандартный способ сделать это.
Примеры неправильного сравнения double/float в различных открытых проектах: JTS, Batik, Hadoop, Hudson, ICU4J, Lucene. Трудно определить, в каких случаях это может привести к проблемам, но это тот случай, когда я бы исправлял безусловно: правильный и надёжный вариант обычно при этом ещё и короче неправильного.
Чтобы изменить ситуацию, я написал маленький детектор для FindBugs, который находит некорректно реализованные функции сравнения и предлагает использовать Float.compare/Double.compare.
Вообще для всех примитивных типов есть подобные методы. Если вам надо сравнить несколько полей по очереди, можно написать так:
public class MyObject implements Comparable < double d; int i; String s; char c; @Override public int compareTo(MyObject o) < int result; result = Double.compare(d, o.d); if(result != 0) return result; result = Integer.compare(i, o.i); if(result != 0) return result; result = s.compareTo(o.s); if(result != 0) return result; result = Character.compare(c, o.c); return result; >>Смотрится лучше, чем куча веток с больше и меньше. А если вы пользуетесь Guava или чем-то подобным, тогда так:
@Override public int compareTo(MyObject o)