Boomkaart op Java
1. Inleiding
Een Tree Map is een rood-zwart op bomen gebaseerde NavigableMap implementatie. Een NavigableMap is een SortedMap met enkele navigatiemethoden - dit geeft de beste overeenkomst voor bepaalde zoekdoelen. De sortering gebeurt volgens de natuurlijke volgorde van de sleutels die op de kaart aanwezig zijn. Als er een vergelijker wordt geleverd op het moment dat deze wordt gemaakt, heft deze de natuurlijke volgorde op. Deze implementatie biedt gegarandeerde log(n)tijdkosten voor de containsKey , get , put en remove operaties.
Houd er rekening mee dat de volgorde die wordt onderhouden door een treemap, zoals elke gesorteerde kaart, en of er al dan niet een expliciete comparator wordt gegeven, consistent moet zijn met equals als deze gesorteerde kaart de Map . correct moet implementeren koppel. Dit is zo omdat de Map interface is gedefinieerd in termen van de equals bewerking, maar een gesorteerde kaart voert alle belangrijke vergelijkingen uit met behulp van zijn compareTo (of compare ) methode, dus twee sleutels die door deze methode als gelijk worden beschouwd, zijn, vanuit het standpunt van de gesorteerde kaart, gelijk. Het gedrag van een gesorteerde kaart is goed gedefinieerd, zelfs als de volgorde niet overeenkomt met equals; het voldoet gewoon niet aan het algemene contract van de Map interface.
2. Draadveiligheid
TreeMap is impliciet geen thread-veilige verzameling - je moet het maken als een van de threads de kaart structureel wijzigt. Als meerdere threads tegelijkertijd toegang hebben tot een kaart en ten minste één van de threads de kaart structureel wijzigt, moet extern worden gesynchroniseerd. Een structurele wijziging is elke bewerking die een of meer toewijzingen toevoegt of verwijdert; alleen het wijzigen van de waarde die is gekoppeld aan een bestaande sleutel is geen structurele wijziging. Dit wordt meestal bereikt door te synchroniseren op een object dat van nature de kaart inkapselt. Als zo'n object niet bestaat, moet de kaart worden "ingepakt" met de Collections.synchronizedSortedMap methode. Dit kan het beste worden gedaan tijdens het maken, om onbedoelde niet-gesynchroniseerde toegang tot de kaart te voorkomen:
final SortedMap sortedMap = Collections.synchronizedSortedMap(new TreeMap());
3. Iteratie
De iterators geretourneerd door de iterator methode van de collecties die worden geretourneerd door alle "collectieweergavemethoden" van deze klasse zijn fail-fast :als de kaart structureel wordt gewijzigd op enig moment nadat de iterator is gemaakt, op welke manier dan ook, behalve via de eigen remove van de iterator methode, gooit de iterator een ConcurrentModificationException . Dus, in het licht van gelijktijdige modificatie, faalt de iterator snel en netjes, in plaats van willekeurig, niet-deterministisch gedrag te riskeren op een onbepaald tijdstip in de toekomst. Merk op dat het faalsnelle gedrag van een iterator niet kan worden gegarandeerd, aangezien het in het algemeen onmogelijk is om harde garanties te geven in de aanwezigheid van niet-gesynchroniseerde gelijktijdige wijziging. Fail-fast iterators gooien ConcurrentModificationException op basis van best-effort. Daarom zou het verkeerd zijn om een programma te schrijven dat voor zijn correctheid afhankelijk was van deze uitzondering:het faalsnelle gedrag van iterators zou alleen moeten worden gebruikt om bugs te detecteren.
4. Constructeur
TreeMap klasse heeft vier constructors. Deze kunnen worden gebruikt volgens de vereisten.
4.1 TreeMap()
Deze constructor construeert een nieuwe, lege treemap met behulp van de natuurlijke volgorde van de sleutels. Alle sleutels die in de kaart worden ingevoegd, moeten de Comparable . implementeren koppel. Bovendien moeten al deze sleutels onderling vergelijkbaar zijn:k1.compareTo(k2) mag geen ClassCastException . gooien voor alle toetsen k1 en k2 op de kaart. Als de gebruiker probeert een sleutel in de kaart te plaatsen die deze beperking schendt (de gebruiker probeert bijvoorbeeld een tekenreekssleutel in een kaart te plaatsen waarvan de sleutels gehele getallen zijn), de put(Object key, Object value) oproep levert een ClassCastException . op
4.2 TreeMap(Comparator comparator)
Dit construeert een nieuwe, lege treemap, geordend volgens de gegeven comparator. Alle sleutels die in de kaart zijn ingevoegd, moeten onderling vergelijkbaar zijn door de gegeven comparator:comparator.compare(k1, k2) mag geen ClassCastException . gooien voor alle toetsen k1 en k2 op de kaart. Als de gebruiker probeert een sleutel in de kaart te plaatsen die deze beperking schendt, wordt de put(Object key, Object value) oproep levert een ClassCastException . op
4.3 TreeMap(Map m uit)
Construeert een nieuwe boomkaart met dezelfde toewijzingen als de gegeven kaart, geordend volgens de natuurlijke volgorde van de sleutels. Alle sleutels die in de nieuwe kaart worden ingevoegd, moeten de Comparable . implementeren koppel. Bovendien moeten al deze sleutels onderling vergelijkbaar zijn:k1.compareTo(k2) mag geen ClassCastException throw gooien voor alle toetsen k1 en k2 op de kaart. Deze methode wordt uitgevoerd in n*log(n) tijd. Als de kaart die als argument aan de methode is doorgegeven null is, dan zal dit NullPointerException . opleveren .
4.4 TreeMap(SortedMap m)
Maakt een nieuwe boomstructuurkaart met dezelfde toewijzingen en met dezelfde volgorde als de opgegeven gesorteerde kaart. Deze methode werkt in lineaire tijd.
5. Methoden
In deze sectie zullen we enkele van de belangrijkste en meest gebruikte methoden van Tree Map . bekijken klas.
containsKey(Objectsleutel)
Retourneert true als deze kaart een toewijzing voor de opgegeven sleutel bevat. Deze methode genereert ClassCastException als de opgegeven sleutel niet kan worden vergeleken met de sleutels die momenteel op de kaart staan. Het gooit NullPointerException als de opgegeven sleutel null is en deze kaart natuurlijke volgorde gebruikt, of als de comparator geen null-sleutels toestaat.
containsValue(Objectwaarde)
Retourneert true als deze kaart een of meer sleutels toewijst aan de opgegeven waarde. Meer formeel, retourneert true als en slechts als deze kaart ten minste één toewijzing bevat naar een waarde v zodanig dat (value==null ? v==null : value.equals(v)) . Deze bewerking zal voor de meeste implementaties waarschijnlijk tijd lineair in de kaartgrootte vergen.
get(Objectsleutel)
Retourneert de waarde waaraan de opgegeven sleutel is toegewezen, of null als deze kaart geen toewijzing voor de sleutel bevat. Als deze kaart een toewijzing bevat van een sleutel k naar een waarde v zodat de sleutel gelijk is aan k volgens de volgorde van de kaart, dan retourneert deze methode v; anders retourneert het null . Een geretourneerde waarde van null geeft niet noodzakelijk aan dat de kaart geen toewijzing voor de sleutel bevat; het is ook mogelijk dat de kaart de sleutel expliciet toewijst aan null . Deze methode genereert ClassCastException als de opgegeven sleutel niet kan worden vergeleken met de sleutels die momenteel op de kaart staan.
putAll(Kaart)
Kopieert alle toewijzingen van de opgegeven kaart naar deze kaart. Deze toewijzingen vervangen alle toewijzingen die deze toewijzing had voor een van de sleutels die zich momenteel in de opgegeven toewijzing bevinden.
put(K-toets, V-waarde)
Koppelt de opgegeven waarde aan de opgegeven sleutel in deze map. Als de kaart eerder een toewijzing voor de sleutel bevatte, wordt de oude waarde vervangen. Deze methode genereert ClassCastException als de opgegeven sleutel niet kan worden vergeleken met de sleutels die momenteel op de kaart staan.
6. Voorbeeld boomkaart
TreeMapExample.java
package org.javacodegeeks.treemap;
import java.util.*;
public class TreeMapExample {
public static void main(String[] args) {
TreeMapExample treeMapExample = new TreeMapExample();
treeMapExample.constructor1();
treeMapExample.constructor2();
treeMapExample.constructor3();
treeMapExample.clear();
treeMapExample.containsKey();
treeMapExample.containsValue();
treeMapExample.removeAndReplace();
}
/** Constructs a new, empty tree map, using the natural ordering of its keys */
private void constructor1() {
TreeMap<Integer, String> treeMap = new TreeMap();
treeMap.put(1, "one");
treeMap.put(2, "two");
System.out.println("Constructor1: " + treeMap);
}
/** Constructs a new, empty tree map, ordered according to the given comparator */
private void constructor2() {
TreeMap<Integer, String> treeMap = new TreeMap(Comparator.reverseOrder());
treeMap.put(2, "two");
treeMap.put(1, "one");
System.out.println("Constructor2: " + treeMap);
}
/** Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys */
private void constructor3() {
Map<String, Integer> map = Map.of("one", 1, "two", 2, "three", 3, "four", 4);
TreeMap<Integer, String> treeMap = new TreeMap(map);
System.out.println("Constructor3: " + treeMap);
}
// #####################################################################
// ################# Important methods #################################
// #####################################################################
private TreeMap<String, Integer> constructTreeMap() {
TreeMap<String, Integer> treeMap = new TreeMap();
treeMap.put("one", 1);
treeMap.put("two", 2);
treeMap.put("three", 3);
treeMap.put("four", 4);
treeMap.put("five", 5);
return treeMap;
}
private void clear() {
TreeMap<String, Integer> treeMap = constructTreeMap();
System.out.println("\nBefore Clearing: " + treeMap);
treeMap.clear();
System.out.println("After Clearing: " + treeMap);
}
private void containsKey() {
TreeMap<String, Integer> treeMap = constructTreeMap();
System.out.println("\nContains key four: " + treeMap.containsKey("four"));
System.out.println("Does not contains key six: " + treeMap.containsKey("six"));
}
private void containsValue() {
TreeMap<String, Integer> treeMap = constructTreeMap();
System.out.println("\nContains value 4: " + treeMap.containsValue(4));
System.out.println("Does not contains value 6: " + treeMap.containsValue(6));
}
private void removeAndReplace() {
TreeMap<String, Integer> treeMap = constructTreeMap();
treeMap.remove("four");
System.out.println("\nContains key four: " + treeMap.containsKey("four"));
treeMap.replace("five", 6);
System.out.println("Value of five replaced with: " + treeMap.get("five"));
}
}
Wanneer u de bovenstaande code uitvoert, ziet u iets als hieronder:
Constructor1: {1=one, 2=two}
Constructor2: {2=two, 1=one}
Constructor3: {four=4, one=1, three=3, two=2}
Before Clearing: {five=5, four=4, one=1, three=3, two=2}
After Clearing: {}
Contains key four: true
Does not contains key six: false
Contains value 4: true
Does not contains value 6: false
Contains key four: false
Value of five replaced with: 6
Process finished with exit code 0
7. Samenvatting
In dit artikel hebben we gekeken naar een van de verzamelklassen van Java - Tree Map . We hebben gekeken naar verschillende manieren om het object te construeren en waarom we ze zullen gebruiken. We hebben ook enkele van de meest voorkomende methoden besproken die beschikbaar zijn in deze klasse. We hebben ook besproken hoe we dit een thread-safe collectie kunnen maken en ook hoe we de elementen in dit object kunnen herhalen.
8. Downloaden
Dit was een voorbeeld van het gebruik van TreeMap-verzameling in Javacollections datastructuur treemap
