Een gids voor TreeMap in Java

1. Overzicht

In dit artikel gaan we het verkennen TreeMap invoer van Kaart interface van Java Collections Framework (JCF).

TreeMap is een kaartimplementatie die de ingangen gesorteerd houdt volgens de natuurlijke volgorde van de sleutels of, nog beter, met behulp van een vergelijker als deze door de gebruiker wordt verstrekt tijdens de constructie.

Eerder hebben we gedekt Hash kaart en LinkedHashMap implementaties en we zullen ons realiseren dat er nogal wat informatie is over hoe deze klassen werken die vergelijkbaar is.

De genoemde artikelen worden sterk aanbevolen om te lezen voordat u verder gaat met deze.

2. Standaard sorteren in TreeMap

Standaard, TreeMap sorteert al zijn vermeldingen op basis van hun natuurlijke volgorde. Voor een geheel getal zou dit een oplopende volgorde betekenen en voor strings in alfabetische volgorde.

Laten we eens kijken naar de natuurlijke volgorde in een test:

@Test openbare leegte gegevenTreeMap_whenOrdersEntriesNaturally_thenCorrect () {TreeMap map = nieuwe TreeMap (); map.put (3, "val"); map.put (2, "val"); map.put (1, "val"); map.put (5, "val"); map.put (4, "val"); assertEquals ("[1, 2, 3, 4, 5]", map.keySet (). toString ()); }

Merk op dat we de integer-sleutels op een niet-geordende manier hebben geplaatst, maar bij het ophalen van de sleutelset bevestigen we dat ze inderdaad in oplopende volgorde worden onderhouden. Dit is de natuurlijke volgorde van gehele getallen.

Evenzo, wanneer we strings gebruiken, worden ze in hun natuurlijke volgorde gesorteerd, d.w.z. alfabetisch:

@Test openbare ongeldig gegevenTreeMap_whenOrdersEntriesNaturally_thenCorrect2 () {TreeMap map = nieuwe TreeMap (); map.put ("c", "val"); map.put ("b", "val"); map.put ("a", "val"); map.put ("e", "val"); map.put ("d", "val"); assertEquals ("[a, b, c, d, e]", map.keySet (). toString ()); }

TreeMap, in tegenstelling tot een hash-map en een gekoppelde hash-map, gebruikt het nergens het hashing-principe, omdat het geen array gebruikt om zijn items op te slaan.

3. Aangepast sorteren in TreeMap

Als we niet tevreden zijn met de natuurlijke volgorde van TreeMapkunnen we ook onze eigen regel voor ordening definiëren door middel van een vergelijker tijdens het maken van een boomkaart.

In het onderstaande voorbeeld willen we dat de sleutels met gehele getallen in aflopende volgorde worden gerangschikt:

@Test openbare ongeldige gegevenTreeMap_whenOrdersEntriesByComparator_thenCorrect () {TreeMap map = nieuwe TreeMap (Comparator.reverseOrder ()); map.put (3, "val"); map.put (2, "val"); map.put (1, "val"); map.put (5, "val"); map.put (4, "val"); assertEquals ("[5, 4, 3, 2, 1]", map.keySet (). toString ()); }

Een hash-map garandeert niet de volgorde van de opgeslagen sleutels en garandeert specifiek niet dat deze volgorde in de loop van de tijd hetzelfde zal blijven, maar een boomstructuur garandeert dat de sleutels altijd volgens de opgegeven volgorde worden gesorteerd.

4. Belang van TreeMap Sorteren

Dat weten we nu TreeMap slaat al zijn vermeldingen op in gesorteerde volgorde. Vanwege dit kenmerk van boomkaarten kunnen we zoekopdrachten uitvoeren zoals; vind "grootste", zoek "kleinste", vind alle sleutels kleiner dan of groter dan een bepaalde waarde, enz.

De onderstaande code dekt slechts een klein percentage van deze gevallen:

@Test openbare ongeldig gegevenTreeMap_whenPerformsQueries_thenCorrect () {TreeMap map = nieuwe TreeMap (); map.put (3, "val"); map.put (2, "val"); map.put (1, "val"); map.put (5, "val"); map.put (4, "val"); Geheel getal hoogsteKey = map.lastKey (); Geheel getal laagsteKey = map.firstKey (); Stel keysLessThan3 = map.headMap (3) .keySet (); Stel keysGreaterThanEqTo3 = map.tailMap (3) .keySet (); assertEquals (nieuw geheel getal (5), hoogste sleutel); assertEquals (nieuw geheel getal (1), laagste sleutel); assertEquals ("[1, 2]", keysLessThan3.toString ()); assertEquals ("[3, 4, 5]", keysGreaterThanEqTo3.toString ()); }

5. Interne implementatie van TreeMap

TreeMap werktuigen NavigableMap interface en baseert zijn interne werking op de principes van rood-zwarte bomen:

public class TreeMap breidt uit AbstractMap implementeert NavigableMap, Cloneable, java.io.Serializable

Het principe van rood-zwarte bomen valt buiten het bestek van dit artikel, maar er zijn belangrijke dingen die u moet onthouden om te begrijpen hoe ze passen in TreeMap.

Allereerst, een rood-zwarte boom is een datastructuur die uit knooppunten bestaat; Stel je een omgekeerde mangoboom voor met zijn wortel in de lucht en de takken die naar beneden groeien. De root bevat het eerste element dat aan de boom is toegevoegd.

De regel is dat vanaf de wortel elk element in de linkertak van een knooppunt altijd kleiner is dan het element in het knooppunt zelf. Degenen aan de rechterkant zijn altijd groter. Wat meer of minder definieert dan wordt bepaald door de natuurlijke ordening van de elementen of de gedefinieerde comparator bij de constructie, zoals we eerder zagen.

Deze regel garandeert dat de items van een treemap altijd in gesorteerde en voorspelbare volgorde zullen zijn.

ten tweede, een rood-zwarte boom is een zelfbalancerende binaire zoekboom. Dit kenmerk en het bovenstaande garanderen dat basisbewerkingen zoals zoeken, ophalen, plaatsen en verwijderen logaritmische tijd in beslag nemen O (logboek n).

Zelfbalancerend zijn is hier de sleutel. Terwijl we steeds items invoegen en verwijderen, stelt u zich voor dat de boom langer wordt aan de ene rand of korter aan de andere.

Dit zou betekenen dat een operatie een kortere tijd zou kosten op de kortere tak en langere tijd op de tak die het verst van de root verwijderd is, iets wat we niet zouden willen gebeuren.

Daarom wordt hier bij het ontwerp van roodzwarte bomen voor gezorgd. Bij elke invoeging en verwijdering wordt de maximale hoogte van de boom op elke rand gehandhaafd O (logboek n) d.w.z. de boom balanceert zichzelf continu.

Net als hash-map en gekoppelde hash-map, wordt een boomstructuur niet gesynchroniseerd en daarom zijn de regels voor het gebruik ervan in een omgeving met meerdere threads vergelijkbaar met die in de andere twee mapimplementaties.

6. De juiste kaart kiezen

Heb gekeken Hash kaart en LinkedHashMap implementaties eerder en nu TreeMap, is het belangrijk om een ‚Äč‚Äčkorte vergelijking te maken tussen de drie om ons te helpen bij welke waar past.

Een hash-kaart is goed als een algemene kaartimplementatie die snelle opslag- en ophaalbewerkingen mogelijk maakt. Het schiet echter tekort vanwege de chaotische en ongeordende indeling van inzendingen.

Dit zorgt ervoor dat het slecht presteert in scenario's met veel iteratie, aangezien de volledige capaciteit van de onderliggende array de traversal beïnvloedt, behalve alleen het aantal items.

Een gekoppelde hash-kaart bezit de goede eigenschappen van hash-kaarten en voegt orde toe aan de ingangen. Het presteert beter wanneer er veel iteratie is, omdat alleen het aantal inzendingen wordt meegerekend, ongeacht de capaciteit.

Een boomkaart tilt ordenen naar een hoger niveau door volledige controle te bieden over hoe de sleutels moeten worden gesorteerd. Aan de andere kant biedt het slechtere algemene prestaties dan de andere twee alternatieven.

We zouden een gekoppelde hash-map vermindert de chaos bij het ordenen van een hash-map zonder de prestatieverbinding van een tree-map op te lopen.

7. Conclusie

In dit artikel hebben we Java verkend TreeMap klasse en de interne implementatie ervan. Omdat het de laatste is in een reeks veelgebruikte kaartinterface-implementaties, hebben we ook kort besproken waar het het beste past in relatie tot de andere twee.

De volledige broncode voor alle voorbeelden die in dit artikel worden gebruikt, is te vinden in het GitHub-project.