TreeMap in Java

Wenn Sie diesen Artikel lesen, sind Sie höchstwahrscheinlich mit der Kartenoberfläche vertraut und wissen, wo sie entsprechend angewendet werden kann. Wenn nicht, dann kommen Sie hierher . Heute sprechen wir über die Funktionen der Java TreeMap-Implementierung und insbesondere darüber, wie sie sich von HashMap unterscheidet und wie man sie richtig verwendet.

Vergleich von TreeMap, HashMap und LinkedHashMap

Die am häufigsten verwendete Implementierung der Map-Schnittstelle ist HashMap. Da es einfach zu bedienen ist und einen schnellen Zugriff auf Daten gewährleistet, ist es der beste Kandidat für die Lösung der meisten Probleme. Die meisten, aber nicht alle. Manchmal müssen Sie Daten strukturiert speichern und darin navigieren können. In diesem Fall hilft eine andere Implementierung der Map-Schnittstelle (TreeMap). TreeMap implementiert die NavigableMap- Schnittstelle, die SortedMap erbt , das wiederum die Map-Schnittstelle erbt. Durch die Implementierung der NavigableMap- und SortedMap- Schnittstellen erhält TreeMap zusätzliche Funktionalität, die in HashMap nicht verfügbar ist, zahlt jedoch einen Preis in Bezug auf die Leistung. Es gibt auch die LinkedHashMapclass , die es Ihnen auch ermöglicht, Daten in einer bestimmten Reihenfolge zu speichern (der Reihenfolge, in der Sie sie der Karte hinzufügen). Um die Unterschiede zwischen diesen drei Klassen zu verstehen, sehen Sie sich diese Tabelle an: Wie Sie sehen, haben diese Klassen viele Gemeinsamkeiten, es gibt jedoch auch einige Unterschiede. Obwohl die TreeMap-Klasse die vielseitigste ist, kann sie nicht immer Null als Schlüssel speichern. Darüber hinaus dauert der Zugriff auf die Elemente einer TreeMap am längsten. Wenn Sie Daten also nicht in einer sortierten Reihenfolge speichern müssen, ist es besser, HashMap oder LinkedHashMap zu verwenden.

Rot-schwarzer Baum

Sie haben wahrscheinlich bemerkt, dass TreeMap unter der Haube eine Datenstruktur verwendet, die als Rot-Schwarz-Baum bezeichnet wird. Das Speichern von Daten in dieser Struktur ist genau das, was die Datenreihenfolge ermöglicht. Was ist das denn für ein Baum? Lass es uns herausfinden! Stellen Sie sich vor, Sie müssen Zahlen-String-Paare speichern. Die Zahlen 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 und 101 werden Schlüssel sein. Wenn Sie Daten in einer herkömmlichen Liste speichern und das Element mit Schlüssel 101 finden müssen, müssen Sie alle 13 Elemente durchgehen, um es zu finden. Für 13 Elemente ist das keine große Sache, aber wenn wir mit einer Million arbeiten, werden wir große Probleme haben. Um diese Probleme zu lösen, verwenden Programmierer etwas komplexere Datenstrukturen. Hier betritt der rot-schwarze Baum die Bühne!Die Suche nach einem Element beginnt an der Wurzel des Baums, in unserem Fall bei 61. Dann vergleichen wir die Knotenwerte mit dem gesuchten Wert. Wenn unser Wert geringer ist, gehen wir nach links; ist es größer, dann gehen wir nach rechts. Dieser Vorgang wiederholt sich, bis wir den gewünschten Wert finden oder auf ein Element stoßen, dessen Wert Null ist (ein Blatt des Baums). Die Farben Rot und Schwarz werden verwendet, um das Navigieren und Ausbalancieren im Baum zu vereinfachen. Beim Bau eines rot-schwarzen Baumes gibt es Regeln, die unbedingt beachtet werden müssen:

• Die Wurzel muss schwarz sein.
• Die Blätter des Baumes müssen schwarz sein.
• Ein roter Knoten muss zwei schwarze untergeordnete Knoten haben.
• Ein schwarzer Knoten kann untergeordnete Knoten beliebiger Farbe haben.
• Ein Pfad von einem Knoten zu seinen Blättern muss die gleiche Anzahl schwarzer Knoten enthalten.
• Den Blättern werden neue Knoten hinzugefügt.

Wenn Sie die Regeln 3, 4 und 5 zusammen betrachten, können Sie verstehen, wie die Knotenfarbe uns schneller durch den Baum navigieren lässt: Ein Pfad durch schwarze Knoten ist immer kürzer als einer durch rote Knoten. Dementsprechend wird die Gesamtgröße des Baumes durch die Anzahl der schwarzen Knoten bestimmt, die als „schwarze Höhe“ bezeichnet wird. Die Datenstruktur des Rot-Schwarz-Baums ist in verschiedenen Programmiersprachen implementiert. Es gibt viele Java-Implementierungen im Internet, daher werden wir uns hier nicht länger aufhalten. Lassen Sie uns stattdessen weiterhin die Funktionalität von TreeMap kennenlernen.

Methoden, die von den Schnittstellen SortedMap und NavigableMap stammen

Wie HashMap implementiert TreeMap die Map-Schnittstelle, was bedeutet, dass TreeMap über alle Methoden verfügt, die in HashMap vorhanden sind. TreeMap implementiert aber auch die Schnittstellen SortedMap und NavigableMap und erhält dadurch zusätzliche Funktionalität. SortedMap ist eine Schnittstelle, die Map erweitert und für einen sortierten Datensatz relevante Methoden hinzufügt:

• firstKey() : gibt den Schlüssel des ersten Elements in der Karte zurück
• lastKey() : gibt den Schlüssel des letzten Elements zurück
• headMap(K end) : gibt eine Map zurück, die alle Elemente der aktuellen Map enthält, vom Anfang bis zum Element mit dem Schlüsselende
• tailMap(K start) : gibt eine Karte zurück, die alle Elemente der aktuellen Karte enthält, vom Startelement bis zum Ende
• subMap(K start, K ​​end) : gibt eine Karte zurück, die alle Elemente der aktuellen Karte enthält, vom Startelement bis zum Element mit dem Schlüsselende.

NavigableMap ist eine Schnittstelle, die SortedMap erweitert und Methoden zum Navigieren zwischen Elementen einer Karte hinzufügt:

• firstEntry() : gibt das erste Schlüssel-Wert-Paar zurück
• lastEntry() : gibt das letzte Schlüssel-Wert-Paar zurück
• pollFirstEntry() : gibt das erste Paar zurück und löscht es
• pollLastEntry() : gibt das letzte Paar zurück und löscht es
• ceilingKey(K obj) : gibt den kleinsten Schlüssel k zurück, der größer oder gleich dem Schlüssel obj ist. Wenn kein solcher Schlüssel vorhanden ist, wird null zurückgegeben
• floorKey(K obj) : gibt den größten Schlüssel k zurück, der kleiner oder gleich dem Schlüssel obj ist. Wenn kein solcher Schlüssel vorhanden ist, wird null zurückgegeben
• LowerKey(K obj) : gibt den größten Schlüssel k zurück, der kleiner als der Schlüssel obj ist. Wenn kein solcher Schlüssel vorhanden ist, wird null zurückgegeben
• higherKey(K obj) : gibt den kleinsten Schlüssel k zurück, der größer als das Schlüsselobj ist. Wenn kein solcher Schlüssel vorhanden ist, wird null zurückgegeben
• DeckeEntry(K obj) : Ähnlich wie die Methode DeckeKey(K obj), gibt nur ein Schlüssel-Wert-Paar (oder Null) zurück.
• floorEntry(K obj) : Ähnlich der Methode floorKey(K obj), gibt nur ein Schlüssel-Wert-Paar (oder Null) zurück.
• LowerEntry(K obj) : Ähnlich wie die Methode „lowerKey(K obj)“ gibt sie nur ein Schlüssel-Wert-Paar (oder null) zurück.
• higherEntry(K obj) : Ähnlich wie die MethodehigherKey(K obj), gibt nur ein Schlüssel-Wert-Paar (oder Null) zurück.
• DescendingKeySet() : Gibt ein NavigableSet zurück, das alle Schlüssel in umgekehrter Reihenfolge enthält
• DescendingMap() : Gibt eine NavigableMap zurück, die alle Paare in umgekehrter Reihenfolge enthält
• navigableKeySet() : Gibt ein NavigableSet-Objekt zurück, das alle Schlüssel in der Reihenfolge enthält, in der sie gespeichert sind
• headMap(K UpperBound, boolean incl) : gibt eine Karte zurück, die Paare vom Anfang bis zum UpperBound-Element enthält. Der Parameter „incl“ gibt an, ob das UpperBound-Element in die zurückgegebene Karte aufgenommen werden soll
• tailMap(K LowerBound, boolean incl) : Funktionalität ähnlich der vorherigen Methode, gibt nur Paare von LowerBound bis zum Ende zurück
• subMap(K LowerBound, Boolean LowIncl, K UpperBound, Boolean HighIncl) : Gibt wie bei den vorherigen Methoden Paare von LowerBound bis UpperBound zurück; Die Argumente lowIncl und highIncl geben an, ob die Grenzelemente in die neue Karte einbezogen werden sollen.

Zusätzlich zu den üblichen Konstruktoren verfügt TreeMap über einen weiteren Konstruktor, der eine Instanz eines Komparators akzeptiert. Dieser Komparator ist für die Reihenfolge verantwortlich, in der Elemente gespeichert werden.

Beispiele für TreeMap

Diese Fülle an zusätzlichen Methoden mag unnötig erscheinen, aber sie erweisen sich als viel nützlicher, als Sie auf den ersten Blick erkennen. Lassen Sie uns gemeinsam das folgende Beispiel untersuchen. Stellen Sie sich vor, wir arbeiten in der Marketingabteilung eines großen Unternehmens und verfügen über eine Datenbank mit Personen, denen wir Anzeigen zeigen möchten. Dabei sind zwei Details zu beachten:

• Wir müssen die Anzahl der Impressionen für jede Person im Auge behalten
• Der Algorithmus zur Anzeige von Werbung für Minderjährige ist unterschiedlich.

Erstellen wir eine Person- Klasse, die alle relevanten Informationen zu jeder Person speichert:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

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

Wir implementieren die Logik in der Main- Klasse:

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

Erstellen Sie in der Main-Klasse eine TreeMap, in der jeder Schlüssel eine bestimmte Person darstellt und jeder Wert die Anzahl der Anzeigenimpressionen in diesem Monat angibt. Wir übergeben dem Konstruktor einen Komparator, der die Personen nach Alter sortiert. Wir füllen die Karte mit beliebigen Werten. Jetzt wollen wir einen Verweis auf den ersten Erwachsenen in unserem kleinen Datenrepository erhalten. Wir tun dies mithilfe der Stream-API. Dann erhalten wir zwei separate Karten, die wir an die Methoden übergeben, die Anzeigen anzeigen. Es gibt viele, viele Möglichkeiten, wie wir diese Aufgabe hätten erfüllen können. Mit dem Methodenarsenal der TreeMap-Klasse können wir individuelle Lösungen für jeden Bedarf erstellen. Sie müssen sich nicht alle merken, da Sie jederzeit auf die Dokumentation oder Tipps Ihrer IDE zurückgreifen können. Um das Gelernte zu vertiefen, empfehlen wir Ihnen, sich eine Videolektion aus unserem Java-Kurs anzusehen

Das ist alles für jetzt! Ich hoffe, dass Ihnen die TreeMap-Klasse jetzt klar ist und Sie sie bei der Lösung praktischer Codierungsaufgaben richtig anwenden werden.