Einführung in die TreeMap-Sammlung

Eines Tages an der Universität musste ich Code schreiben, um die Nachnamen meiner Klassenkameraden, die als Schlüssel zu ihren persönlichen Daten dienten, in aufsteigender Reihenfolge zu sortieren. Ich habe viel Zeit damit verbracht. Aber wenn ich damals von der TreeMap- Klasse gewusst hätte , wäre ich mit der Aufgabe viel schneller fertig geworden.

Was ist eine TreeMap ? Es handelt sich um eine wörterbuchähnliche Datenstruktur, die Elemente als Schlüssel-Wert-Paare speichert und nach Schlüssel sortiert.

Wo und wie kann es eingesetzt werden? Nun, es wäre ideal für die gleiche Aufgabe mit den Nachnamen meiner Klassenkameraden gewesen. Wenn ich Werte in aufsteigender Reihenfolge speichern muss, muss ich, anstatt meinen eigenen Sortieralgorithmus zu schreiben, lediglich eine TreeMap erstellen und die Werte darin einfügen.

Es sortiert Typen wie Integer und String in aufsteigender Reihenfolge. Wenn Sie jedoch Ihren eigenen benutzerdefinierten Typ in eine TreeMap einfügen möchten , muss Ihre Klasse die Comparable- Schnittstelle implementieren , damit sie die Methode „compareTo()“ implementiert , die angibt, wie Instanzen Ihrer Klasse sortiert werden.

public class Person implements Comparable<Person> {

    private String firstName;
    private String lastName;

    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }

    public String getFirstName() {
        return firstName;
    }

    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }

  …

    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }

    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

Überschreiben wir die Methode „compareTo()“ , sodass sie die Werte nach Vornamen in umgekehrter alphabetischer Reihenfolge sortiert:

TreeMap map = new TreeMap<Person, String>();

map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

Die Werte werden in der folgenden Reihenfolge gespeichert:

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

Die TreeMap- Klasse implementiert die NavigableMap- Schnittstelle, die wiederum die SortedMap- Schnittstelle erweitert. Dadurch kann die TreeMap- Klasse Bäume verwenden, um Werte in sortierter Reihenfolge zu speichern.

Vereinfacht ausgedrückt ist ein Rot-Schwarz-Baum eine Datenstruktur, die Werte im rechten Teilbaum speichert, wenn sie größer als die Wurzel sind, und im linken Teilbaum, wenn sie kleiner sind. Diese Implementierung kann Werte in der Struktur sehr schnell nachschlagen.

Ein Rot-Schwarz-Baum balanciert sich selbst, d. h. er ändert seine Struktur, wenn jeder neue Wert eingefügt wird. Der zuerst geschaffene Wert wird zunächst als Wurzel betrachtet, im Verlauf des Bilanzierungsprozesses kann jedoch auch ein anderer Wert zur Wurzel werden.

Nun wissen Sie, was TreeMap ist und wie es funktioniert.

Denken Sie daran, dass TreeMap nur Objekte speichern kann, deren Klasse die Comparable- Schnittstelle implementiert und die Methode CompareTo() überschreibt.

Aber was ist, wenn wir Klassen von Drittanbietern verwenden, die aus verschiedenen Bibliotheken geladen werden, und Comparable darin nicht implementieren können? Dafür gibt es eine Lösung: Schreiben Sie Ihren eigenen Comparator .

Comparator ist eine Schnittstelle mit einer Compare()-Methode. Wir können damit Objekte vergleichen und in einer TreeMap speichern .

Comparator<Person> comparator = new Comparator<Person>() {

    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};


TreeMap map = new TreeMap<Person, String>(comparator);

In diesem Beispiel haben wir einen benutzerdefinierten Comparator erstellt und eine TreeMap an die Klasse übergeben.

Ab Java 8 können wir dies mit einem Lambda-Ausdruck schreiben:

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

Mit anderen Worten: Um Werte in einer TreeMap zu speichern , müssen Sie angeben, wie sie sortiert werden sollen. Dafür gibt es zwei Möglichkeiten: Implementieren Sie Comparable oder implementieren Sie Ihren eigenen Comparator .

Aber was ist, wenn wir null als Schlüssel in eine TreeMap einfügen müssen ? Mit HashMap können Sie dies tun. Ja, aber wie geht TreeMap damit um?

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

Das Ausführen dieses Codes führt zu einer Fehlermeldung:

Das Problem besteht darin, dass die TreeMap- Klasse intern Werte mithilfe der Methode „compareTo()“ vergleicht . Sie können durchaus einen Nullwert übergeben und der Code wird kompiliert. Zur Laufzeit erhalten Sie jedoch eine Fehlermeldung, da die Methode für einen Nullwert aufgerufen wird und eine NullPointerException ausgelöst wird .

Vergleich von HashMap und TreeMap

Im Gegensatz zu TreeMap können Sie mit HashMap null als Schlüssel speichern. Die Struktur hat einen bestimmten Platz für alle Nullschlüssel . HashMap ist in der Lage, Nullschlüssel zu speichern , da es anhand ihres Hash-Werts bestimmt, wohin sie gehen, und die Berechnung des Hash-Werts keine Vergleiche erfordert. Alle Nullschlüssel haben also ihren Platz.

Da haben Sie es – jetzt wissen Sie, was Sie verwenden müssen, wenn Sie Werte in sortierter Reihenfolge speichern müssen, und wie Sie die Regeln für die Sortierung festlegen.