TreeMap in Java

Als u dit artikel aan het lezen bent, bent u waarschijnlijk bekend met de kaartinterface en waar deze op de juiste manier kan worden toegepast. Zo niet, kom dan hier . Vandaag zullen we het hebben over de kenmerken van de implementatie van Java TreeMap, en meer specifiek, hoe het verschilt van HashMap en hoe het correct te gebruiken.

Vergelijking van TreeMap, HashMap en LinkedHashMap

De meest gebruikte implementatie van de kaartinterface is HashMap. Het is gemakkelijk te gebruiken en garandeert snelle toegang tot gegevens, dus het is de beste kandidaat om de meeste problemen op te lossen. De meeste, maar niet alle. Soms moet je data gestructureerd opslaan en er doorheen kunnen navigeren. In dit geval komt een andere implementatie van de kaartinterface (TreeMap) te hulp. TreeMap implementeert de NavigableMap- interface, die SortedMap erft , die op zijn beurt de Map-interface erft. Door de NavigableMap- en SortedMap- interfaces te implementeren, krijgt TreeMap extra functionaliteit die niet beschikbaar is in HashMap, maar het betaalt een prijs in termen van prestaties. Er is ook de LinkedHashMapclass , waarmee u ook gegevens in een specifieke volgorde kunt opslaan (de volgorde waarin u deze aan de kaart toevoegt). Bekijk deze tabel om de verschillen tussen deze drie klassen te begrijpen: Zoals je ziet hebben deze klassen veel gemeen, maar er zijn ook een aantal verschillen. Hoewel de TreeMap-klasse de meest veelzijdige is, kan deze niet altijd null als sleutel opslaan. Bovendien kost de toegang tot de elementen van een TreeMap de meeste tijd. Dus als u gegevens niet in een bepaalde volgorde hoeft op te slaan, is het beter om HashMap of LinkedHashMap te gebruiken .

Rood-zwarte boom

Je hebt waarschijnlijk gemerkt dat TreeMap onder de motorkap een gegevensstructuur gebruikt die een rood-zwarte boom wordt genoemd. Het opslaan van gegevens in deze structuur is precies wat zorgt voor ordening van gegevens. Wat voor boom is dit dan? Laten we het uitzoeken! Stel je voor dat je Number-String-paren moet opslaan. De nummers 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 en 101 worden sleutels. Als u gegevens opslaat in een traditionele lijst en u moet het element vinden met sleutel 101, dan moet u door alle 13 elementen stappen om het te vinden. Voor 13 elementen is dit geen probleem, maar als we met een miljoen werken, krijgen we grote problemen. Om deze problemen op te lossen, gebruiken programmeurs iets complexere datastructuren. Hier komt de rood-zwarte boom het podium op!Zoeken naar een element begint bij de wortel van de boom, in ons geval 61. Vervolgens vergelijken we de knooppuntwaarden met de waarde waarnaar we zoeken. Als onze waarde lager is, gaan we naar links; als het groter is, gaan we naar rechts. Dit proces herhaalt zich totdat we de gewenste waarde vinden of een element tegenkomen waarvan de waarde nul is (een blad van de boom). De kleuren rood en zwart worden gebruikt om het navigeren en balanceren van de boom te vergemakkelijken. Er zijn regels die altijd in acht moeten worden genomen bij het bouwen van een rood-zwarte boom:

• De wortel moet zwart zijn.
• De bladeren van de boom moeten zwart zijn.
• Een rode node moet twee zwarte onderliggende nodes hebben.
• Een zwart knooppunt kan onderliggende knooppunten van elke kleur hebben.
• Een pad van een knooppunt naar zijn bladeren moet hetzelfde aantal zwarte knooppunten bevatten.
• Nieuwe knooppunten worden toegevoegd aan bladeren.

Als u Regel 3, 4 en 5 samen beschouwt, kunt u begrijpen hoe knooppuntkleur ons sneller door de boom laat navigeren: een pad door zwarte knooppunten is altijd korter dan een pad door rode knooppunten. Dienovereenkomstig wordt de totale grootte van de boom bepaald door het aantal zwarte knopen, wat de "zwarte hoogte" wordt genoemd. De rood-zwarte boomdatastructuur is geïmplementeerd in verschillende programmeertalen. Er zijn veel Java-implementaties op internet, dus we blijven hier niet hangen. Laten we in plaats daarvan doorgaan met het leren kennen van de functionaliteit van TreeMap.

Methoden die afkomstig zijn van de SortedMap- en NavigableMap-interfaces

Net als HashMap implementeert TreeMap de Map-interface, wat betekent dat TreeMap alle methoden heeft die in HashMap bestaan. Maar TreeMap implementeert ook de SortedMap- en NavigableMap- interfaces en haalt er dus extra functionaliteit uit. SortedMap is een interface die Map uitbreidt en methoden toevoegt die relevant zijn voor een gesorteerde dataset:

• firstKey() : retourneert de sleutel van het eerste element in de kaart
• lastKey() : retourneert de sleutel van het laatste element
• headMap(K end) : retourneert een kaart die alle elementen van de huidige kaart bevat, van het begin tot het element met de sleutel einde
• tailMap(K start) : retourneert een kaart die alle elementen van de huidige kaart bevat, van het startelement tot het einde
• subMap(K start, K ​​end) : retourneert een kaart die alle elementen van de huidige kaart bevat, van het startelement tot het element met het sleuteleinde.

NavigableMap is een interface die SortedMap uitbreidt en methoden toevoegt voor het navigeren tussen elementen van een kaart:

• firstEntry() : retourneert het eerste sleutel-waardepaar
• lastEntry() : retourneert het laatste sleutel-waardepaar
• pollFirstEntry() : retourneert en verwijdert het eerste paar
• pollLastEntry() : retourneert en verwijdert het laatste paar
• ceilingKey(K obj) : retourneert de kleinste sleutel k die groter is dan of gelijk is aan de sleutel obj. Als een dergelijke sleutel niet bestaat, wordt null geretourneerd
• floorKey(K obj) : retourneert de grootste sleutel k die kleiner is dan of gelijk is aan de sleutel obj. Als een dergelijke sleutel niet bestaat, wordt null geretourneerd
• lowerKey(K obj) : retourneert de grootste sleutel k die kleiner is dan de sleutel obj. Als een dergelijke sleutel niet bestaat, wordt null geretourneerd
• higherKey(K obj) : geeft de kleinste sleutel k die groter is dan de sleutel obj. Als een dergelijke sleutel niet bestaat, wordt null geretourneerd
• ceilingEntry(K obj) : vergelijkbaar met de methode ceilingKey(K obj), retourneert alleen een sleutel-waardepaar (of null)
• floorEntry(K obj) : vergelijkbaar met de floorKey(K obj) methode, retourneert alleen een sleutel-waardepaar (of null)
• lowerEntry(K obj) : vergelijkbaar met de methode lowerKey(K obj), retourneert alleen een sleutel-waardepaar (of null)
• highEntry(K obj) : vergelijkbaar met de methode upperKey(K obj), retourneert alleen een sleutel-waardepaar (of null)
• aflopendeKeySet() : retourneert een NavigableSet die alle sleutels in omgekeerde volgorde bevat
• aflopendeMap() : retourneert een NavigableMap die alle paren in omgekeerde volgorde bevat
• navigableKeySet() : retourneert een NavigableSet-object dat alle sleutels bevat in de volgorde waarin ze zijn opgeslagen
• headMap(K upperBound, boolean incl) : retourneert een kaart die paren bevat vanaf het begin tot het upperBound-element. De parameter incl geeft aan of het element upperBound moet worden opgenomen in de geretourneerde kaart
• tailMap(K lowerBound, boolean incl) : functionaliteit vergelijkbaar met de vorige methode, retourneert alleen paren van ondergrens tot het einde
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : net als bij de voorgaande methoden, retourneert paren van ondergrens naar bovengrens; de argumenten lowIncl en highIncl geven aan of de grenselementen in de nieuwe kaart moeten worden opgenomen.

Naast de gebruikelijke constructors heeft TreeMap nog een constructor die een instantie van een comparator accepteert. Deze vergelijker is verantwoordelijk voor de volgorde waarin elementen worden opgeslagen.

Voorbeelden van TreeMap

Deze overvloed aan extra methoden lijkt misschien overbodig, maar ze blijken veel nuttiger te zijn dan je op het eerste gezicht zou denken. Laten we samen het volgende voorbeeld bekijken. Stel je voor dat we op de marketingafdeling van een groot bedrijf werken en we hebben een database met mensen aan wie we advertenties willen laten zien. Er zijn twee details waarmee u rekening moet houden:

• We moeten het aantal vertoningen voor elke persoon bijhouden
• Het algoritme voor het weergeven van advertenties aan minderjarigen is anders.

Laten we een persoonsklasse maken , waarin alle relevante informatie over elke persoon wordt opgeslagen:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

We implementeren de logica in de klasse Main :

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

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

Maak in de klasse Main een TreeMap, waarin elke sleutel een specifieke persoon vertegenwoordigt en elke waarde het aantal advertentievertoningen deze maand is. We geven de constructor een comparator door die mensen sorteert op leeftijd. We vullen de kaart met willekeurige waarden. Nu willen we een verwijzing krijgen naar de eerste volwassene in onze kleine gegevensopslagplaats. Dit doen we met behulp van de Stream API. Vervolgens krijgen we twee afzonderlijke kaarten, die we doorgeven aan de methoden die advertenties weergeven. Er zijn heel veel manieren waarop we deze taak hadden kunnen volbrengen. Met het arsenaal aan methoden van de TreeMap-klasse kunnen we voor elke behoefte aangepaste oplossingen creëren. Je hoeft ze niet allemaal te onthouden, want je kunt altijd de documentatie of tips uit je IDE gebruiken. Om te versterken wat je hebt geleerd, raden we je aan een videoles van onze Java-cursus te bekijken Dat is het voor nu! Ik hoop dat de TreeMap-klasse u nu duidelijk is en dat u deze op de juiste manier zult toepassen bij het oplossen van praktische codeertaken.