codestory

Die Anleitung zu Java TreeMap

  1. TreeMap
  2. Wie lagert TreeMap die Daten?
  3. Examples
  4. TreeMap mit dem Schlüssel null

1. TreeMap

In diesem Artikel werden wir die Klasse TreeMap untersuchen, die eine Implementierung der Interface Map ist und sich im Java Collection Framework befindet.
public class TreeMap<K,V> extends AbstractMap<K,V>
                    implements NavigableMap<K,V>, Cloneable, java.io.Serializable
Grundsätzlich lernen wir in diesem Artikel die Eigenschaften von TreeMap und wie es Mapping speichert. Die grundlegenden Konzepte von Map werden nicht noch einmal erwähnt, wenn Sie das Konzept von Map nicht kennen, sollten Sie mit diesem Artikel fortfahren.
Map<K,V>
SortedMap<K,V>
NavigableMap<K,V>
TreeMap<K,V>
Doppelte Schlüssel sind nicht erlaubt.
Kann den Schlüssel null und die Werte null zulassen.
Nur Schlüssel null sind zulässig wenn ein geeigneter Comparator bereitgestellt wird.
Die Reihenfolge der Schlüssel wird nicht garantiert.
Der Schlüssel werden in die aufsteigende Reihenfolge nach ihrer natürlichen Reihenfolge oder nach einem bereitgestellten Comparator sortiert.
Erbt die Funktionen der Interface SortedMap. Alle Schlüssel von TreeMapmüssen vom Typ Comparable (vergleichbar) sein, oder Sie müssen einen Comparator für TreeMap bereitstellen, damit er die Schlüssel miteinander vergleicht. Andernfalls wird ClassCastException geworfen. Comparator wird bei einer Zeitpunk der Erstellung vom Objekt TreeMap über einen seiner Kontruktoren bereitgestellt.
TreeMap​ constructors
TreeMap()

TreeMap​(Map<? extends K,​? extends V> m)    

TreeMap​(Comparator<? super K> comparator)

// Using the same ordering as the specified sortedMap.
TreeMap​(SortedMap<K,​? extends V> m)

2. Wie lagert TreeMap die Daten?

TreeMap verwendet comparator.compare(key1,key2) um zwei Schlüssel zu vergleichen wenn Comparator bereitgestellt wird. Andernfalls verwendet es key1.compareTo(key2) um zwei Schlüssel zu vergleichen.TreeMap wurde entwickelt, um sicherzustellen, dass das Suchen, Aktualisieren, oder Löschen einer Karte so wenig Zeit wie möglich in Anspruch nimmt, indem die Anzahl der Schlüsselvergleiche reduziert wird. In diesem Abschnitt erfahren Sie, wie TreeMap seine Daten speichert.
Entry<K,V> ist eine Klasse zum Speichern einer Zuordnung, die aus 5 Properties besteht: key, value, parent, left, right. TreeMap verwaltet eine Referenz auf einen Entry mit der Ursprung - root. Die Suchen auf TreeMap beginnen am Root-Entry und breiten sich zu einem Blatt des Baums aus.
Entry<K,V>
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
Sehen wir uns zum besseren Verständnis an, was passiert, wenn wir einer TreeMap<Integer,String> Mappings hinzufügen.
TreeMap<Integer, String> map = new TreeMap<>();

// keys = 5, 3, 9, 7, 1, 11.
map.put(5, "Five");
map.put(3,  "Three");
map.put(9,  "Nine");
map.put(7, "Seven");
map.put(1, "One");
map.put(11, "Eleven");
Das obige Bild zeigt die Baumstruktur von TreeMap. Das erste zur TreeMap hinzugefügte Mapping ist die Wurzel (Root) des Baums, das Mapping mit dem kleineren Schlüssel wird links platziert und das Mapping mit dem größeren Schlüssel wird rechts platziert.
get(key)?
map.get(7); // key =  7
Die Suche nach einer Mapping beginnt immer beim StammEntry vom Baum. Der zu suchende Schlüssel wird mit dem aktuellen Schlüssel von Entry verglichen, wenn er größer ist, wird er mit dem nächsten Schlüssel von Entry rechts verglichen. Andernfalls wenn es kleiner ist, wird es mit dem Schlüssel vom nächsten Entry auf der linken Seite verglichen, bis die Blätter des Baums gefunden oder erreicht werden.
remove(key)?
Als Nächstes sehen wir uns an, was TreeMap tut, um ein Mapping zu entfernen.
map.remove(5); // Remove the mapping has key = 5.
Um ein Mapping zu entfernen, identifiziert die TreeMap den Standort des zu entfernenden Entry . Dann sucht es nach dem Entry mit dem kleinste Schlüssel und größer als der zu entfernende Schlüssel, um ihn an der Position des zu entfernenden Entry zu ersetzen.
put(key,value)?
map.put(2, "Two");

3. Examples

Wie wir alle wissen, implementiert die Klasse Integer die Interface Comparable, sodass die Objekte Integer miteinander verglichen werden können. TreeMap mit Schlüssel Integer muss keinen Comparator bereitstellen.
TreeMapEx1.java
package org.o7planning.treemap.ex;

import java.util.Set;
import java.util.TreeMap;

public class TreeMapEx1 {

    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}
Output:
[1, 3, 5, 7, 9, 11]
1 --> One
3 --> Three
5 --> Five
7 --> Seven
9 --> Nine
11 --> Eleven
Beispiel: Verwenden Sie den benutzerdefinierten Comparator um die Schlüsselreihenfolge umzukehren.
TreeMap_reverseOrder_ex1.java
package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMap_reverseOrder_ex1 {

    public static void main(String[] args) {
        Comparator<Integer> reverseOrderComparator = Comparator.reverseOrder();
        
        TreeMap<Integer, String> map = new TreeMap<>(reverseOrderComparator);
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}
Output:
[11, 9, 7, 5, 3, 1]
11 --> Eleven
9 --> Nine
7 --> Seven
5 --> Five
3 --> Three
1 --> One
Sehen Sie sich die weiteren Beispielen für die Verwendung des benutzerdefinieren Comparator an und wie Sie navigieren, nach Schlüsseln oder Mappings suchen:

4. TreeMap mit dem Schlüssel null

TreeMap lässt den Schlüssel null nur zu, wenn es mit einem Comparator bereitgestellt wird, der den Vergleich von Schlüssel null mit anderen Schlüssel unterstützt.
TreeMap_nullKey_ex1.java
package org.o7planning.treemap.ex;

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

public class TreeMap_nullKey_ex1 {

    public static void main(String[] args) {
        // Comparator.nullsFirst
        // Comparator.nullsLast
        Comparator<String> comparator = Comparator.nullsFirst(Comparator.naturalOrder());

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
Output:
--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
Z.B: Schreiben Sie einen benutzerdefinierten Comparator, der das Vergleichen von Schlüssel null mit anderen Schlüsseln unterstützt:
TreeMap_nullKey_ex2.java
package org.o7planning.treemap.ex;

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

public class TreeMap_nullKey_ex2 {

    public static void main(String[] args) {  
        Comparator<String> comparator = new StringNullComparator();

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
// The comparator supports null comparison.
class StringNullComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if(o1 == o2) {
            return 0; // o1 = o2
        }
        if(o1 == null)  {
            return -1; // o1 < o2
        }
        if(o2 == null)  {
            return 1; // o1 > o2
        }
        return o1.compareTo(o2);
    }
}
Output:
--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400

Die Anleitungen Java Collections Framework

Show More

Neueste Artikel

Show More