Das Innenleben von TreeMap in Java

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.

Das Innenleben von TreeMap in Java

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.

Beziehung von Red Black Tree und TreeMap

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.

Konstrukteur von TreeMap

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.

Beispiel

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

Ausgabe

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

Fazit

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!