Object Ordering
If the List consists of String elements, it will be sorted into alphabetical order. If it consists of Date elements, it will be sorted into chronological order. How does this happen? String and Date both implement the Comparable interface. Comparable implementations provide a natural ordering for a class, which allows objects of that class to be sorted automatically. The following table summarizes some of the more important Java platform classes that implement Comparable .
| Class | Natural Ordering |
|---|---|
| Byte | Signed numerical |
| Character | Unsigned numerical |
| Long | Signed numerical |
| Integer | Signed numerical |
| Short | Signed numerical |
| Double | Signed numerical |
| Float | Signed numerical |
| BigInteger | Signed numerical |
| BigDecimal | Signed numerical |
| Boolean | Boolean.FALSE < Boolean.TRUE |
| File | System-dependent lexicographic on path name |
| String | Lexicographic |
| Date | Chronological |
| CollationKey | Locale-specific lexicographic |
If you try to sort a list, the elements of which do not implement Comparable , Collections.sort(list) will throw a ClassCastException . Similarly, Collections.sort(list, comparator) will throw a ClassCastException if you try to sort a list whose elements cannot be compared to one another using the comparator . Elements that can be compared to one another are called mutually comparable. Although elements of different types may be mutually comparable, none of the classes listed here permit interclass comparison.
This is all you really need to know about the Comparable interface if you just want to sort lists of comparable elements or to create sorted collections of them. The next section will be of interest to you if you want to implement your own Comparable type.
Writing Your Own Comparable Types
The Comparable interface consists of the following method.
The compareTo method compares the receiving object with the specified object and returns a negative integer, 0, or a positive integer depending on whether the receiving object is less than, equal to, or greater than the specified object. If the specified object cannot be compared to the receiving object, the method throws a ClassCastException .
To keep the preceding example short, the class is somewhat limited: It doesn't support middle names, it demands both a first and a last name, and it is not internationalized in any way. Nonetheless, it illustrates the following important points:
- Name objects are immutable. All other things being equal, immutable types are the way to go, especially for objects that will be used as elements in Set s or as keys in Map s. These collections will break if you modify their elements or keys while they're in the collection.
- The constructor checks its arguments for null . This ensures that all Name objects are well formed so that none of the other methods will ever throw a NullPointerException .
- The hashCode method is redefined. This is essential for any class that redefines the equals method. (Equal objects must have equal hash codes.)
- The equals method returns false if the specified object is null or of an inappropriate type. The compareTo method throws a runtime exception under these circumstances. Both of these behaviors are required by the general contracts of the respective methods.
- The toString method has been redefined so it prints the Name in human-readable form. This is always a good idea, especially for objects that are going to get put into collections. The various collection types' toString methods depend on the toString methods of their elements, keys, and values.
Since this section is about element ordering, let's talk a bit more about Name 's compareTo method. It implements the standard name-ordering algorithm, where last names take precedence over first names. This is exactly what you want in a natural ordering. It would be very confusing indeed if the natural ordering were unnatural!
Take a look at how compareTo is implemented, because it's quite typical. First, you compare the most significant part of the object (in this case, the last name). Often, you can just use the natural ordering of the part's type. In this case, the part is a String and the natural (lexicographic) ordering is exactly what's called for. If the comparison results in anything other than zero, which represents equality, you're done: You just return the result. If the most significant parts are equal, you go on to compare the next most-significant parts. In this case, there are only two parts — first name and last name. If there were more parts, you'd proceed in the obvious fashion, comparing parts until you found two that weren't equal or you were comparing the least-significant parts, at which point you'd return the result of the comparison.
If you run this program, here's what it prints.
There are four restrictions on the behavior of the compareTo method, which we won't go into now because they're fairly technical and boring and are better left in the API documentation. It's really important that all classes that implement Comparable obey these restrictions, so read the documentation for Comparable if you're writing a class that implements it. Attempting to sort a list of objects that violate the restrictions has undefined behavior. Technically speaking, these restrictions ensure that the natural ordering is a total order on the objects of a class that implements it; this is necessary to ensure that sorting is well defined.
Comparators
What if you want to sort some objects in an order other than their natural ordering? Or what if you want to sort some objects that don't implement Comparable ? To do either of these things, you'll need to provide a Comparator — an object that encapsulates an ordering. Like the Comparable interface, the Comparator interface consists of a single method.
The compare method compares its two arguments, returning a negative integer, 0, or a positive integer depending on whether the first argument is less than, equal to, or greater than the second. If either of the arguments has an inappropriate type for the Comparator , the compare method throws a ClassCastException .
Much of what was said about Comparable applies to Comparator as well. Writing a compare method is nearly identical to writing a compareTo method, except that the former gets both objects passed in as arguments. The compare method has to obey the same four technical restrictions as Comparable 's compareTo method for the same reason — a Comparator must induce a total order on the objects it compares.
Suppose you have a class called Employee , as follows.
Let's assume that the natural ordering of Employee instances is Name ordering (as defined in the previous example) on employee name. Unfortunately, the boss has asked for a list of employees in order of seniority. This means we have to do some work, but not much. The following program will produce the required list.
The Comparator in the program is reasonably straightforward. It relies on the natural ordering of Date applied to the values returned by the hireDate accessor method. Note that the Comparator passes the hire date of its second argument to its first rather than vice versa. The reason is that the employee who was hired most recently is the least senior; sorting in the order of hire date would put the list in reverse seniority order. Another technique people sometimes use to achieve this effect is to maintain the argument order but to negate the result of the comparison.
You should always use the former technique in favor of the latter because the latter is not guaranteed to work. The reason for this is that the compareTo method can return any negative int if its argument is less than the object on which it is invoked. There is one negative int that remains negative when negated, strange as it may seem.
The Comparator in the preceding program works fine for sorting a List , but it does have one deficiency: It cannot be used to order a sorted collection, such as TreeSet , because it generates an ordering that is not compatible with equals. This means that this Comparator equates objects that the equals method does not. In particular, any two employees who were hired on the same date will compare as equal. When you're sorting a List , this doesn't matter; but when you're using the Comparator to order a sorted collection, it's fatal. If you use this Comparator to insert multiple employees hired on the same date into a TreeSet , only the first one will be added to the set; the second will be seen as a duplicate element and will be ignored.
To fix this problem, simply tweak the Comparator so that it produces an ordering that is compatible with equals . In other words, tweak it so that the only elements seen as equal when using compare are those that are also seen as equal when compared using equals . The way to do this is to perform a two-part comparison (as for Name ), where the first part is the one we're interested in — in this case, the hire date — and the second part is an attribute that uniquely identifies the object. Here the employee number is the obvious attribute. This is the Comparator that results.
One last note: You might be tempted to replace the final return statement in the Comparator with the simpler:
Don't do it unless you're absolutely sure no one will ever have a negative employee number! This trick does not work in general because the signed integer type is not big enough to represent the difference of two arbitrary signed integers. If i is a large positive integer and j is a large negative integer, i — j will overflow and will return a negative integer. The resulting comparator violates one of the four technical restrictions we keep talking about (transitivity) and produces horrible, subtle bugs. This is not a purely theoretical concern; people get burned by it.
# Comparable and Comparator
# Sorting a List using Comparable or a Comparator
Say we are working on a class representing a Person by their first and last names. We have created a basic class to do this and implemented proper equals and hashCode methods.
Now we would like to sort a list of Person objects by their name, such as in the following scenario:
Unfortunately, as marked, the above currently won’t compile. Collections.sort(..) only knows how to sort a list if the elements in that list are comparable, or a custom method of comparison is given.
If you were asked to sort the following list : 1,3,5,4,2 , you’d have no problem saying the answer is 1,2,3,4,5 . This is because Integers (both in Java and mathematically) have a natural ordering, a standard, default comparison base ordering. To give our Person class a natural ordering, we implement Comparable<Person> , which requires implementing the method compareTo(Person p):
Now, the main method given will function correctly
If, however, you either do not want or are unable to modify class Person , you can provide a custom Comparator<T> that handles the comparison of any two Person objects. If you were asked to sort the following list: circle, square, rectangle, triangle, hexagon you could not, but if you were asked to sort that list based on the number of corners, you could. Just so, providing a comparator instructs Java how to compare two normally not comparable objects.
Comparators can also be created/used as an anonymous inner class
# Lambda expression based comparators
As of Java 8, comparators can also be expressed as lambda expressions
# Comparator default methods
Furthermore, there are interesting default methods on the Comparator interface for building comparators : the following builds a comparator comparing by lastName and then firstName .
# Inversing the order of a comparator
Any comparator can also easily be reversed using the reversedMethod which will change ascending order to descending.
# The compareTo and compare Methods
The Comparable<T> interface requires one method:
And the Comparator<T> interface requires one method:
These two methods do essentially the same thing, with one minor difference: compareTo compares this to other , whereas compare compares t1 to t2 , not caring at all about this .
(opens new window) Thus, for the comparison of a and b :
- If a < b , a.compareTo(b) and compare(a,b) should return a negative integer, and b.compareTo(a) and compare(b,a) should return a positive integer
- If a > b , a.compareTo(b) and compare(a,b) should return a positive integer, and b.compareTo(a) and compare(b,a) should return a negative integer
- If a equals b for comparison, all comparisons should return 0 .
# Natural (comparable) vs explicit (comparator) sorting
There are two Collections.sort() methods:
First, here is a Person class that implements Comparable:
Here is how you would use the above class to sort a List in the natural ordering of its elements, defined by the compareTo() method override:
Here is how you would use an anonymous inline Comparator to sort a List that does not implement Comparable, or in this case, to sort a List in an order other than the natural ordering:
# Creating a Comparator using comparing method
This creates a comparator for the class Person that uses this person name as the comparison source. Also it is possible to use method version to compare long, int and double. For example:
Reversed order
To create a comparator that imposes the reverse ordering use reversed() method:
Chain of comparators
This will create a comparator that firs compares with last name then compares with first name. You can chain as many comparators as you want.
# Sorting Map entries
As of Java 8, there are default methods on the Map.Entry interface to allow sorting of map iterations.
Of course, these can also be used outside of the stream api :
# Syntax
- public class MyClass implements Comparable <MyClass >
- public class MyComparator implements Comparator <SomeOtherClass >
- public int compareTo(MyClass other)
- public int compare(SomeOtherClass o1, SomeOtherClass o2)
# Remarks
When implementing a compareTo(..) method which depends upon a double , do not do the following:
The truncation caused by the (int) cast will cause the method to sometimes incorrectly return 0 instead of a positive or negative number, and can thus lead to comparison and sorting bugs.
Instead, the simplest correct implementation is to use Double.compare
A non-generic version of Comparable<T> , simply Comparable , has existed since Java 1.2
(opens new window) . Other than for interfacing with legacy code, it’s always better to implement the generic version Comparable<T> , as it doesn’t require casting upon comparison.
It is very standard for a class to be comparable to itself, as in:
While it is possible to break from this paradigm, be cautious when doing so.
A Comparator<T> can still be used on instances of a class if that class implements Comparable<T> . In this case, the Comparator ‘s logic will be used; the natural ordering specified by the Comparable implementation will be ignored.
Выбор между Comparator и Comparable
Для реализации сортировки требуется, чтобы сортируемые объекты можно было сравнивать между собой на больше-меньше. Иначе говоря, чтобы было определено правило, которое позволит для любых двух объектов указать, какой из них в рамках данного контекста идет раньше, а какой позже.
В java эти правила определяются на уровне классов, к которым принадлежат объекты. Для примера возьмем класс для описания счета пользователя:
В зависимости от контекста сравнение счетов пользователя может происходить по разным правилам, например:
в приложении пользователь видит счета, отсортированные по currency, потом по value;
в админке счета всех пользователей отсортированы по дате изменения.
Для реализации сравнения на больше-меньше в java предусмотрено две возможности:
UserAccount реализует интерфейс Comparable<UserAccount> В этом случае два объекта получают возможность сравнения между собой: acc1.compareTo(acc2)
Создается отдельный класс, реализующий интерфейс Comparator<UserAccount> , и дальше объект этого класса может сравнить между собой два объекта исходного класса: userAccountComparator.compare(acc1, acc2)
Очевидно, что в некоторых случаях выбора между Comparable и Comparator нет. Если исходный класс нельзя модифицировать, или если требуются разные правила сравнения, то придется использовать Comparator. В остальных случаях, технически, можно использовать как Comparator, так и Comparable.
Согласно документации использование Comparable возможно, если для сравнения используется естественный порядок (class’s natural ordering). По ссылке есть представление разработчиков, что такое естественный порядок для стандартных классов (String, Date). Мне не удалось выяснить, что такое естественный порядок в общем случае. Выглядит, что это интуитивное представление разработчика о порядке в данном контексте. При этом даже для стандартных классов порядок может быть не интуитивен (в каком порядке должны идти значения BigDecimal с разной точностью, например 4.0 и 4.00?). Практика показывает, что «естественность» правил различается в понимании разных разработчиков и контекстов. Для меня необходимость опоры на интуицию является аргументом против использования Comparable.
При написании кода приходится лавировать между явностью и неявностью. Явность хороша тем, что для понимания участка кода требуется рассмотреть лишь узкий контекст его использования. В то же время неявность позволяет использовать одинаковые правила для всех участков кода. Разберем на примере: разработчику требуется отсортировать список счетов. Правила сравнения можно указать:
явно: Arrays.sort(accountsList, accountByValueComparator)
Чтобы разработчику узнать правила сортировки в первом случае ему нужно будет посмотреть, как реализован метод compareTo у класса UserAccount, а во втором — у accountByValueComparator. Здесь разницы нет. Но посмотрим на обратную задачу. Пусть разработчик видит перед собой код
Как определить, где используется объявленный метод compareTo ? Если искать по использованию метода, то потребуется включить в поиск и метод суперкласса Comparable#compareTo , так как именно он будет найден в Arrays.sort() . Но метод суперкласса используется также в огромном количестве других мест внутри кода jdk, и найти таким образом его будет сложно. Я не нашел способов искать такие использования методов кроме как ручным перебором: ищем все включения класса UserAccount и ниже по стеку обращаем внимание на все Arrays.sort(), stream.sorted() и тд.
В случае явной передачи компаратора найти его использования элементарно. Я считаю это аргументом за использование компаратора. (Еще одним примером сложностей с поиском неявных использований может служить equals/hashCode, но альтернативы в виде «Equalator»-а для них нет).
Резюмируя — в большинстве случаев аргументы за использование Comparator перевешивают аргументы за использование Comparable.
В чем разница между Comparable и Comparator?
Получается, это дублирующие друг друга вещи. Может, есть какие-то реальные различия?
- Comparator и Comparable — это оба интерфейсы
- Коллекция (ну хорошо, объект) является Comparable , когда объект может быть как то сравнен с другим объектом.
- Comparator , в отличие от этого — это способ сравнения объектов.
Пример: школьники на уроке физкультуры, физрук говорит: строиться по росту! — ученики быстренько сравнивают свои росты и строятся — кто выше вперед, кто ниже в хвост строя — это пример реализации Comparable , где в качестве compareTo(сосед) используется рост учеников.
Второй пример: те же школьники. Директор дает задание учителю математики сравнить учеников по успеваемости. Математичка берет журнал и сравнивает учеников по успеваемости — здесь работает compare(ученик1, ученик2) — Comparator’ом выступает математичка. Аналогично компаратором может выступить русичка или трудовик.
С философской точки зрения Comparator является субъектом — индивидом познающим внешний мир, сравнивая объекты.
А Comparable является объектом, т.е. на него направлена познавательная деятельность субъекта. И одновременно он сам является субъектом, который пытается познать другой объект, сравнивая его с самим собой.