TreeMap ist eine Klasse des Java Collection Framework, die die NavigableMap-Schnittstelle implementiert. Sie speichert die Elemente der Karte in einer Baumstruktur und bietet eine effiziente Alternative zum Speichern der Schlüssel-Wert-Paare in sortierter Reihenfolge. TreeMap verwendet intern einen rot-schwarzen Baum , bei dem es sich um einen selbstausgleichenden binären Suchbaum handelt, muss das Comparable Interface oder einen benutzerdefinierten Komparator implementieren, damit die Sortierreihenfolge seiner Elemente beibehalten werden kann. Andernfalls tritt eine java.lang.ClassCastException auf wie TreeMap intern in Java funktioniert.
Um das Innenleben von TreeMap zu verstehen, ist es notwendig, einen Überblick über den Rot-Schwarz-Baum-Algorithmus zu haben, da TreeMap ihn zum Speichern von Elementen verwendet.
Ein Rot-Schwarz-Baum ist ein selbstausgleichender binärer Suchbaum mit den folgenden Eigenschaften:
Jeder Knoten enthält ein zusätzliches Bit, dargestellt durch Rot oder Schwarz. Diese Farben werden verwendet, um sicherzustellen, dass der Baum im Gleichgewicht bleibt.
Die Farbe des Wurzelknotens ist immer schwarz.
Ein roter Knoten kann keinen anderen Knoten derselben Farbe wie sein Nachbar haben
Vom Wurzelknoten bis zum leeren Knoten muss die Anzahl der schwarzen Knoten auf allen Pfaden gleich sein
Sehen wir uns nun die Struktur von TreeMap an:
Wenn wir der TreeMap ein Element hinzufügen, wird der erste Eintrag an erster Stelle hinzugefügt. Ab dem zweiten Element wird geprüft, ob der Schlüssel des aktuellen Eintrags größer oder kleiner als der vorherige Eintrag ist werden links hinzugefügt und diejenigen mit größerem Wert werden rechts vom übergeordneten Eintrag hinzugefügt.
Um die TreeMap-Sammlung in unserem Programm zu verwenden, müssen wir zunächst eine Instanz der TreeMap-Klasse erstellen. Dafür stellt Java die folgenden Konstruktoren bereit:
TreeMap(): Es wird eine leere TreeMap-Sammlung erstellt
TreeMap(Map mapInstance): Wir können eine Baumkarte mit Einträgen aus einer anderen Karte erstellen
TreeMap(Comparator comparatorInstance): Es ermöglicht uns, eine leere Baumkarte zu erstellen, die mithilfe eines Komparators sortiert wird.
TreeMap(SortedMap sortedmapInstance): Wir können auch eine Baumkarte mit den Einträgen einer sortierten Karte erstellen.
Lassen Sie uns einige Beispiele besprechen, um die oben besprochenen Punkte besser zu verstehen.
Im folgenden Beispiel erstellen wir eine leere TreeMap und speichern dann einige Elemente darin mithilfe der Methode „put()“. Wir drucken die Details mithilfe der for-each-Schleife aus. Die Ergebnisse werden in sortierter Reihenfolge angezeigt.
import java.util.*;
public class Example1 {
public static void main(String[] args) {
// creating a TreeMap
TreeMap<String, Integer> TrMap = new TreeMap<>();
// Adding elements in the map
TrMap.put("Kurti", 4000);
TrMap.put("Shirt", 3000);
TrMap.put("TShirt", 1500);
TrMap.put("Watch", 2000);
TrMap.put("Perfume", 2500);
// printing the details of map
System.out.println("Elements of the map: ");
// iterating through the map
for (String unKey : TrMap.keySet()) {
// printing details of each node
System.out.println("Item: " + unKey + ", Price: " +
TrMap.get(unKey));
}
String frstKey = TrMap.firstKey(); // accessing first key
String lstKey = TrMap.lastKey(); // accessing last key
System.out.println("Accessing name of first key in Map: " +
frstKey);
System.out.println("Accessing name of last key in Map: " +
lstKey);
}
}
Elements of the map: Item: Kurti, Price: 4000 Item: Perfume, Price: 2500 Item: Shirt, Price: 3000 Item: TShirt, Price: 1500 Item: Watch, Price: 2000 Accessing name of first key in Map: Kurti Accessing name of last key in Map: Watch
Wir haben diesen Artikel mit der Definition einer TreeMap begonnen und im nächsten Abschnitt deren Funktionsweise besprochen. TreeMap verwendet einen Rot-Schwarz-Baum zum Speichern seiner Elemente, bei dem es sich um einen selbstausgleichenden binären Suchbaum handelt. Darüber hinaus haben wir auch ein Beispiel besprochen, um die Funktionsweise von TreeMap zu veranschaulichen.
Das obige ist der detaillierte Inhalt vonDas Innenleben von TreeMap in Java. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!
