Comparator in Java

Only lazy people haven’t written about Comparator and comparison in Java. I'm not lazy - so I ask you to love and favor one more variation. I hope it won't be superfluous. And yes, this article is the answer to the question: “Can you write a comparator from memory?” I hope that after reading this article everyone will be able to write a comparator from memory.

Introduction Java is known to be an object-oriented language. As a result, in Java it is common to operate with objects. But sooner or later the task of comparing objects according to some principle arises. So, given: We have some message, which is described by the Message class:

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;
    }
}

Let's add this class to Tutorialspoint java compiler . Let's also remember to add imports:

import java.util.Random;
import java.util.ArrayList;
import java.util.List;

In the main method we will create several messages:

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

Let's think about what we should do if we want to compare them? For example, we want to sort by id. And in order to create order, you need to somehow compare objects in order to understand which object is previous (that is, smaller) and which is next (that is, larger). Let's start with a class like java.lang.Object . As we know, all classes inherit implicitly from this Object class. And this is logical, because This essentially expresses the concept: "Everything is an object" and provides common behavior for all classes. And this class defines that each class has two methods: → hashCode The hashCode method returns some numeric (int) representation of the object as an instance of the class. What does it mean? This means that if you created two different instances of a class, then since the instances are different, their hashCode should be different. This is what it says in the description of the method: “As much as is reasonably practical, the hashCode method defined by class Object does return distinct integers for distinct objects” That is, if these are two different instances, then they should have different hashCodes. That is, this method is not suitable for our comparison. → equals The equals method answers the question “are objects equal” and returns a boolean. This method has the default code:

public boolean equals(Object obj) {
    return (this == obj);
}

That is, without overriding this method on an object, this method essentially says whether the references to the object match or not. This is not suitable for our messages, because we are not interested in links to the object, we are interested in the message id. And even if we override the equals method, the maximum we would get is: “They are equal” or “They are not equal.” But this is not enough for us to determine the order.

Comparator and Comparable in Java

What suits us? If we translate the word “compare” into English in the translator, we will get the translation “compare”. Great, then we need someone who will compare. If you compare this compare, then the one who compares is the Comparator. Let's open Java Api and find Comparator there . And indeed, there is such an interface - java.util.Comparator java.util.Comparator and java.lang.Comparable As you can see, there is such an interface. The class that implements it says that “I am implementing a function for comparing objects.” The only thing to really remember is the comparator contract, which is expressed as follows:


Comparator возвращает int по следующей схеме: 

отрицательный int (первый an object отрицательный, то есть меньше)
положительный int (первый an object положительный, хороший, то есть больший)
ноль = an objectы равны

Now let's write a comparator. We will need to import java.util.Comparator . After import, add a method to main: Comparator<Message> comparator = new Comparator<Message>(); Naturally, this will not work, because Comparator is an interface. Therefore, after the parentheses we will add curly ones { }. In these brackets we will write the method:

public int compare(Message o1, Message o2) {
    return o1.getId().compareTo(o2.getId());
}

You don't even have to remember to write this. A comparator is one who performs a comparison, that is, makes a compare. To answer the question of what order the compared objects are in, we return int. That's all, actually. Simply and easily. As we can see from the example, in addition to Comparator, there is another interface - java.lang.Comparable , implementing which we must define the compareTo method . This interface says that "A class that implements an interface allows instances of the class to be compared." For example, Integer's implementation of compareTo looks like this:

(x < y) ? -1 : ((x == y) ? 0 : 1)

How to remember all these interfaces? What for? Everything comes from English. Compare - to compare, the one who compares is Comparator (as a registrar, for example. That is, the one who registers), and the adjective “compared” is Comparable. Well, “Compare with” is translated not only as compare with, but also as compare to. It's simple. The Java language was written by English-speaking people, and in naming everything in Java they were guided simply by English and there was some kind of logic in the naming. And the compareTo method describes how an instance of a class should be compared with other instances. For example, strings are compared lexigraphically , and numbers are compared by value.

Java 8 brought some nice changes. If we look closely at the Comparator interface, we will see that there is an annotation above it @FunctionalInterface. In fact, this annotation is for information and means that this interface is functional. This means that this interface has only 1 abstract method without an implementation. What does this give us? We can write the comparator code now like this:

Comparator<Message> comparator = (o1, o2) -> o1.getId().compareTo(o2.getId());

In parentheses is how we name the variables. Java itself will see that because... If there is only one method, then it is clear what input parameters are needed, how many, and what types. Next, we say with an arrow that we want to transfer them to this section of the code. In addition, thanks to Java 8, default methods appeared in interfaces - these are methods that appear by default (by default) when we implement an interface. There are several of these in the Comparator interface. For example:

Comparator moreImportant = Comparator.reverseOrder();
Comparator lessImportant = Comparator.naturalOrder();

There is another method that will make your code cleaner. Let's look at the example above, where we described our comparator. What is he doing? It's quite primitive. It simply takes an object and extracts some value from it that is comparable. For example, Integer implements comparable, so we were able to perform compareTo on message id values. This simple comparator function can also be written like this:

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

That is, literally, “We have a Comparator that compares like this: it takes objects, gets Comparable from them using the getId() method, compares using compareTo.” And no more terrible designs. And finally, I would like to note one more feature. Comparators can be chained together. For example:

Comparator<Message> comparator = Comparator.comparing(obj -> obj.getId());
comparator = comparator.thenComparing(obj -> obj.getMessage().length());

Application

The comparator declaration turned out to be quite logical, didn't it? Now we need to see how to use it and in what places. → Collections.sort (java.util.Collections) Of course, we can sort collections this way. But not everything, just lists. And there is nothing unusual here, because... It is the list that requires access to an element by index. And this allows element number two to be swapped with element number three. Therefore, sorting in this way is only possible for lists:

Comparator<Message> comparator = Comparator.comparing(obj -> obj.getId());
Collections.sort(messages, comparator);

→ Arrays.sort (java.util.Arrays) Arrays are also convenient to sort. Again, for the same reason of accessing elements by index. → Descendants of java.util.SortedSet and java.util.SortedMap As we remember, Set and Map do not guarantee the order of storing records. BUT we have special implementations that guarantee order. And if the collection elements do not implement java.lang.Comparable, then we can pass Comparator to the constructor of such collections:

Set<Message> msgSet = new TreeSet(comparator);

→ Stream API In the Stream Api, which appeared in Java 8, a comparator allows you to simplify work on stream elements. For example, we need a sequence of random numbers from 0 to 999 inclusive:

Supplier<Integer> randomizer = () -> new Random().nextInt(1000);
Stream.generate(randomizer)
    .limit(10)
    .sorted(Comparator.naturalOrder())
    .forEach(e -> System.out.println(e));

We could stop, but there are more interesting problems. For example, you need to prepare a Map, where the key is the message id. At the same time, we want to sort these keys so that the keys are in order, from smallest to largest. Let's start with this code:

Map<Integer, Message> collected = Arrays.stream(messages)
                .sorted(Comparator.comparing(msg -> msg.getId()))
                .collect(Collectors.toMap(msg -> msg.getId(), msg -> msg));

What we will get back here is actually a HashMap. And as we know, it does not guarantee any order. Therefore, our records sorted by ID simply got out of order. Not good. We'll have to change our collector a little:

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

The code looked a little creepier, but the problem was now solved correctly thanks to the explicit implementation of the TreeMap. You can read more about the various groups here:

You can create the collector yourself. You can read more here: "Creating a custom collector in Java 8" . And it's useful to read the discussion here: "Java 8 list to map with stream" .

Comparator and Comparable rakes are good. But there is one nuance associated with them that is worth remembering. When a class performs sorting, it calculates that it can cast your class to Comparable. If this is not the case, you will receive an error at execution time. Let's look at an example:

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

It seems that there is nothing wrong here. But in fact, in our example, it will crash with the error: java.lang.ClassCastException: Message cannot be cast to java.lang.Comparable And all because it tried to sort the elements (It is a SortedSet, after all). And I couldn't. You should remember this when working with SortedMap and SortedSet. Additionally Recommended for viewing: Yuri Tkach: HashSet and TreeSet - Collections #1 - Advanced Java