Funktionen von TreeMap in Java

Wenn Sie diesen Artikel lesen, sind Sie wahrscheinlich mit der Kartenoberfläche und ihren Verwendungsmöglichkeiten vertraut. Wenn nicht, dann sind Sie hier richtig. Heute werden wir über die Implementierungsfunktionen von TreeMap sprechen und insbesondere darüber, wie es sich von HashMap unterscheidet und wie man es richtig verwendet.

Vergleich von TreeMap, HashMap und LinkedHashMap

Die am häufigsten verwendete Implementierung der Map- Schnittstelle ist HashMap . Es ist einfach zu bedienen und garantiert einen schnellen Zugriff auf Daten, was es für die meisten Aufgaben zum besten Kandidaten macht. Die meisten, aber nicht alle. Manchmal ist es notwendig, Daten in strukturierter Form zu speichern und durch sie navigieren zu können. In diesem Fall kommt eine andere Implementierung der Map- Schnittstelle zur Rettung – TreeMap . TreeMap implementiert die NavigableMap- Schnittstelle , die von SortedMap erbt , das wiederum von der Map- Schnittstelle erbt . Durch die Implementierung der Schnittstellen NavigableMap und SortedMap erhält TreeMap zusätzliche Funktionalität, die HashMap nicht bietet , allerdings hat dies seinen Preis in Bezug auf die Leistung. Es gibt auch eine LinkedHashMap- Klasse , die es Ihnen ebenfalls ermöglicht, Daten in einer bestimmten Reihenfolge zu speichern – in der Reihenfolge, in der sie hinzugefügt wurden. Um Ihnen zu helfen, 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 Klasse TreeMapdie multifunktionalste ist, kann sie nicht immer nullals Schlüssel gespeichert werden. Darüber hinaus ist die Zugriffszeit auf TreeMap-Elemente am längsten. Wenn Sie Daten nicht in sortierter Form speichern müssen, ist es daher besser, HashMapor zu verwenden LinkedHashMap.

Baum aus rotem Ebenholz

Wie Sie wahrscheinlich bemerkt haben, verwendet es unter der Haube TreeMapeine Datenstruktur namens Rot-Schwarz-Baum. Durch die Speicherung der Daten in dieser Struktur wird die Reihenfolge sichergestellt, in der die Daten gespeichert werden. Was ist dieser 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, 101 werden die Schlüssel sein. Wenn Sie Daten in einer herkömmlichen Liste speichern und ein Element mit Schlüssel 101 suchen müssen, müssen Sie alle 13 Elemente durchlaufen, um es zu finden. Für 13 Elemente ist das nicht kritisch; wenn wir mit einer Million arbeiten, werden wir große Probleme haben. Um solche Probleme zu lösen, verwenden Programmierer etwas komplexere Datenstrukturen. Treffen Sie deshalb den rot-schwarzen Baum!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

Die Suche nach dem benötigten Element beginnt an der Wurzel des Baums, in unserem Fall ist es 61. Als nächstes erfolgt ein Vergleich mit dem benötigten Wert. Ist unser Wert kleiner, gehen wir nach links, ist er größer, gehen wir nach rechts. Dies geschieht so lange, bis wir den erforderlichen Wert finden oder auf ein Element mit einem Wert null(ein Blatt eines Baums) stoßen. Die Farben Rot und Schwarz sollen das Navigieren und Ausbalancieren des Baums erleichtern. Es gibt Regeln, die beim Bau eines rot-schwarzen Baumes immer beachtet werden müssen:

• Die Wurzel sollte schwarz gefärbt sein.
• Die Blätter des Baumes sollten schwarz sein.
• Ein roter Knoten muss zwei schwarze untergeordnete Knoten haben.
• Ein schwarzer Knoten kann beliebige untergeordnete Knoten haben.
• Der Pfad von einem Knoten zu seinen Blättern muss die gleiche Anzahl schwarzer Knoten enthalten.
• Anstelle von Blättern werden neue Knoten hinzugefügt.

Wenn Sie die Regeln 3, 4 und 5 zusammen betrachten, können Sie verstehen, wie das Färben von Knoten die Navigation durch den Baum beschleunigt: Der Weg durch schwarze Knoten ist immer kürzer als durch rote. Daher wird die Gesamtgröße des Baums durch die Anzahl der schwarzen Knoten bestimmt und diese Größe wird als „schwarze Höhe“ bezeichnet. Der Rot-Schwarz-Baum ist in verschiedenen Programmiersprachen implementiert. Es gibt viele Implementierungen für Java im Internet, daher werden wir uns nicht lange damit befassen, sondern uns weiterhin mit der Funktionalität vertraut machen TreeMap.

Von den Schnittstellen SortedMap und NavigableMap abgeleitete Methoden

Es implementiert beispielsweise die Schnittstelle , was bedeutet, dass es HashMapüber alle dafür erforderlichen Methoden verfügt . Aber darüber hinaus implementiert es Schnittstellen und und erhält dadurch zusätzliche Funktionalität. – eine Schnittstelle, die für einen sortierten Datensatz relevante Methoden erweitert und hinzufügt: TreeMapMapTreeMapHashMapTreeMapSortedMapNavigableMapSortedMapMap

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

NavigableMap– eine Schnittstelle, die SortedMapMethoden zum Navigieren zwischen Kartenelementen erweitert und 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 entfernt es;
• pollLastEntry(): gibt das letzte Paar zurück und entfernt 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üsselobjekt 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 Schlüsselobj 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 Schlüsselobj ist. Wenn kein solcher Schlüssel vorhanden ist, wird null zurückgegeben.
• ceilingEntry(K obj): ähnelt der Methode „ceilingKey(K obj)“, gibt jedoch ein Schlüssel-Wert-Paar (oder null) zurück;
• floorEntry(K obj): ähnelt der Methode floorKey(K obj), gibt aber ein Schlüssel-Wert-Paar (oder null) zurück;
• lowerEntry(K obj): ähnelt der Methode „lowerKey(K obj), gibt aber ein Schlüssel-Wert-Paar (oder null) zurück“
• higherEntry(K obj): ähnelt der Methode higherKey(K obj), gibt aber 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 Speicherreihenfolge enthält;
• headMap(K upperBound, boolean incl): Gibt eine Karte zurück, die Paare vom Anfang bis zum UpperBound-Element enthält. Das Argument „incl“ gibt an, ob das UpperBound-Element in die zurückgegebene Karte einbezogen werden soll.
• tailMap(K lowerBound, boolean incl): Die Funktionalität ähnelt der vorherigen Methode, es werden nur Paare von LowerBound bis zum Ende zurückgegeben.
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Wie bei den vorherigen Methoden werden Paare von LowerBound bis UpperBound zurückgegeben, wobei die Argumente lowIncl und highIncl angeben, ob die Grenzelemente in die neue Karte aufgenommen werden sollen.

In der Implementierung selbst TreeMapkommt zusätzlich zu den uns bekannten Konstruktoren noch ein weiterer hinzu, der eine Instanz des Komparators akzeptiert. Dieser Komparator ist für die Reihenfolge verantwortlich, in der die Elemente gespeichert werden.

Beispiele für die Verwendung von TreeMap

Eine solche Fülle zusätzlicher Methoden mag unnötig erscheinen, aber sehr oft erweisen sie sich als viel nützlicher, als es zunächst schien. Schauen wir uns dieses Beispiel mit Ihnen an. Stellen Sie sich vor, wir arbeiten in der Marketingabteilung eines großen Unternehmens und verfügen über eine Datenbank mit Personen, denen wir Werbung zeigen möchten. Dabei gibt es zwei Nuancen:

• wir müssen die Anzahl der Eindrücke jeder Person im Auge behalten;
• Der Algorithmus zur Anzeige von Werbung für Minderjährige ist unterschiedlich.

Erstellen wir eine Klasse Person, die alle uns zur Verfügung stehenden Informationen über eine 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 Klasse Main:

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("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 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){}
}

MainIn der von uns erstellten Klasse ist TreeMap„Wo“ keyeine bestimmte Person und valuedie Anzahl der Anzeigenimpressionen in diesem Monat. Im Konstruktor übergeben wir einen Komparator, der die Personen nach Alter sortiert. mapMit Zufallswerten füllen . Jetzt müssen wir einen Verweis auf den ersten Erwachsenen in unserem Mini-Datenspeicher erhalten. Wir tun dies mithilfe der Stream-API. Danach erhalten wir zwei unabhängige Karten, die wir an die Methoden übergeben, die Werbung anzeigen. Es gibt viele, viele Möglichkeiten, dieses Problem zu lösen. Das Methodenarsenal der Klasse TreeMapermöglicht es Ihnen, Lösungen für jeden Geschmack zu finden. Es ist nicht notwendig, sich alle zu merken, da Sie jederzeit auf die Dokumentation oder Hinweise aus der Entwicklungsumgebung zurückgreifen können. Das ist alles! TreeMapIch hoffe , dass Ihnen die Lektion nun klar ist und Sie sie bei der Lösung praktischer Probleme präzise anwenden können.