SortedMap

SortedMap

In dieser Lektion lernen wir die SortedMap- Schnittstelle kennen. Wir werden neue Methoden untersuchen, die in dieser Schnittstelle angezeigt werden, sowie die Funktionen einer Implementierung von SortedMap – TreeMap – und die Unterschiede zwischen Implementierungen sowie deren Vorteile im Vergleich zu HashMap .

Mal sehen, wie die Hierarchie der Karten aussieht. Achten Sie besonders auf die SortedMap- Schnittstelle und ihre TreeMap- Implementierung – sie stehen heute im Fokus:

Die SortedMap- Schnittstelle erweitert die Map- Schnittstelle. In vielerlei Hinsicht ähnelt es SortedSet (das wiederum Set erweitert ), da beide ähnliche Funktionen zum Speichern und Verwenden sortierter Werte beschreiben.

SortedSet arbeitet mit<TValue>-Objekten und speichert diese, SortedMap speichert jedoch<TKey, TValue>-Paare. Es handelt sich um eine Karte, die alle ihre Elemente in aufsteigender Reihenfolge ihrer Schlüssel speichert.

Die SortedMap- Schnittstelle erweitert Map . Es werden die folgenden Methoden hinzugefügt:

TreeMap-Klasse

Die TreeMap- Klasse ist eine Implementierung der SortedMap- Schnittstelle. Das heißt, TreeMap implementiert alle von SortedMap hinzugefügten Methoden sowie die Standardmethoden der Map- Schnittstelle.

Sie können ein TreeMap- Objekt mit Konstruktoren wie diesen erstellen:

• TreeMap() : erstellt eine leere Karte, die als Baum implementiert ist;

• TreeMap(Map<? erweitert TKey, ? erweitert TValue> map) : erstellt einen Baum und fügt alle Elemente aus der Eingabekarte hinzu;

• TreeMap(SortedMap<TKey, ? erweitert TValue> smap) : erstellt einen Baum und fügt alle Elemente aus der eingegebenen sortierten Karte hinzu;

• TreeMap(Comparator<? super TKey> comparator) : erstellt einen leeren Baum – der Komparator wird verwendet, um alle Elemente zu sortieren, wenn sie anschließend hinzugefügt werden.

Hier ist TKey der Typ der Schlüssel in den gespeicherten Paaren und TValue der Typ der Werte in den in der TreeMap gespeicherten Paaren .

Comparator ist für SortedMap / TreeMap ziemlich wichtig. Es legt die Regeln für das Sortieren – oder Ordnen – unserer Karte fest. Wenn wir keinen Komparator bereitstellen, wird die natürliche Reihenfolge unserer Schlüssel verwendet, wenn wir eine SortedMap erstellen .

Elemente zu einer TreeMap hinzufügen

Elemente werden mit der Methode put() als Paare zu einer Karte hinzugefügt . Als erstes Argument wird der Schlüssel und als zweites der Wert übergeben. Angenommen, wir möchten eine Liste der Schüler und ihrer Noten erstellen.

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Ergebnis:

Wenn wir ein Schlüssel-Wert-Paar hinzufügen und der Schlüssel bereits in der Sammlung vorhanden ist, wird der alte Wert durch den neuen Wert ersetzt. Dieses Verhalten wird in unserem Beispiel anhand zweier Paare veranschaulicht, die denselben Schlüssel haben – („Oliver“, 3) und („Oliver“, 5) .

Schauen wir uns ein Beispiel mit einem von uns erstellten Komparator an. Angenommen, wir möchten die Elemente nach der Länge der Schlüsselzeichenfolge sortiert speichern. Wenn die Länge der Schlüssel gleich ist, sortieren wir alphabetisch (die natürliche Reihenfolge von Zeichenfolgen):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Hier ist die resultierende Sequenz:

Durch dieses Verhalten ähnelt eine TreeMap einem sortierten Array oder einer Liste, deren Indizes Wörter ( String ) anstelle von Zahlen sind.

SortedMap-Methoden in der TreeMap-Klasse

1. Wenn Sie den Schlüssel des ersten Schülers benötigen, können Sie die Methode firstKey() verwenden:

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   Ergebnis: Erster Schlüssel → Anthony

2. Wenn Sie den Schlüssel des letzten Schülers benötigen, können Sie die Methode lastKey() verwenden:

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   Ergebnis: Letzter Schlüssel → Jeff

3. Holen Sie sich alle Objekte, die nach dem Objekt mit dem Schlüssel „ Sara “ kommen:

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   Ergebnis: tailMap: {Sara=5, Jeff=4}

4. Holen Sie sich alle Objekte, die vor dem Objekt mit dem Schlüssel „ Nick “ stehen:

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   Ergebnis: headMap: {Anthony=5}

5. Holen Sie sich alle Objekte, die nach dem Objekt mit dem Schlüssel „ Oliver “ und vor dem Objekt mit dem Schlüssel „ Sara “ kommen:

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   Ergebnis: subMap: {Oliver=5, Roxy=5}

Vergleich von HashMap und SortedMap/TreeMap

Lassen Sie uns darüber sprechen, wie die Elemente geordnet und gespeichert werden:

• Da uns HashMap beim Iterieren keine Garantien für die Reihenfolge gibt, kann sich die Reihenfolge beim Hinzufügen neuer Elemente vollständig ändern.

• In TreeMap basiert die Reihenfolge auf der „natürlichen Reihenfolge“ der Schlüssel gemäß ihrer Methode „compareTo()“ (oder einem von uns bereitgestellten Comparator ). Vergessen Sie außerdem nicht, dass TreeMap die SortedMap- Schnittstelle implementiert , die Methoden enthält, die von dieser Sortierreihenfolge abhängen.

Nun wenden wir uns einer Betrachtung von Leistung und Geschwindigkeit zu:

• HashMap ist eine Karte, die auf Hashing-Schlüsseln basiert. Es kann Elemente in O(1)in konstanter Zeiteinfügen und abrufenUm dies zu unterstützen, müssen die SchlüsselhashCode()undequal().

• TreeMap ist eine baumbasierte Karte. Seine Einfüge- und Abrufvorgänge benötigen logarithmische Zeit, dhO(log n), die von der Anzahl der Elemente in der Karte abhängt. Dies ist notwendig, damit die Elemente über einen Vergleichsmechanismus verfügen, der entweder von unserem Schlüssel oder einem externen Komparator bereitgestellt wird. Dieser Mechanismus bestimmt die Iterationsreihenfolge.

Und diese Faktoren helfen uns bei der Entscheidung, welche Sammlungen wir wann verwenden.

Wenn wir Werte in einer bestimmten Reihenfolge speichern müssen, liegt die Wahl auf der Hand – wir benötigen eine SortedMap . Obwohl es etwas langsamer als HashMap ist , erledigt es wichtige Aufgaben für uns.

Wie bereits erwähnt, kann SortedMap uns den ersten (oder letzten) Schlüssel oder Wert oder Schlüssel-Wert-Paar in unserer Karte liefern, unabhängig davon, wann dieser Wert hinzugefügt wurde. Die HashMap- Implementierung kann dies nicht leisten.

Betrachten Sie beispielsweise eine Karte mit Schlüsseln (Namen der Schüler) und Werten (ihren Noten). Nehmen wir an, wir möchten mit einer Liste in umgekehrter alphabetischer Reihenfolge arbeiten.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

Das Beispiel zeigt, dass die Verwendung einer HashMap die Aufgabe komplizierter macht, da HashMap weder die Reihenfolge der Speicherung noch die Reihenfolge des Abrufens von Elementen aus der Karte garantiert.