streamalism.org

1. Oversigt

I denne artikel skal vi udforske TreeMap gennemførelse af Kort interface fra Java Collections Framework (JCF).

TreeMap er en kortimplementering, der holder sine poster sorteret efter den naturlige rækkefølge af dens nøgler eller endnu bedre ved hjælp af en komparator, hvis den leveres af brugeren på konstruktionstidspunktet.

Tidligere har vi dækket HashMap og LinkedHashMap implementeringer, og vi vil indse, at der er en hel del information om, hvordan disse klasser fungerer, der ligner hinanden.

De nævnte artikler anbefales stærkt at læse, inden du går videre med denne.

2. Standardsortering i TreeMap

Som standard, TreeMap sorterer alle dens poster i henhold til deres naturlige rækkefølge. For et heltal betyder dette stigende rækkefølge og for strenge alfabetisk rækkefølge.

Lad os se den naturlige rækkefølge i en test:

@Test offentlig ugyldighed givenTreeMap_whenOrdersEntriesNaturally_thenCorrect () {TreeMap map = new 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 ()); }

Bemærk, at vi placerede heltalstasterne på en ikke-ordnet måde, men ved hentning af nøglesættet bekræfter vi, at de faktisk opretholdes i stigende rækkefølge. Dette er den naturlige rækkefølge af heltal.

Når vi bruger strenge, sorteres de ligeledes i deres naturlige rækkefølge, dvs. alfabetisk:

@Test offentlig ugyldighed givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2 () {TreeMap map = new 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 ()); }

TreeMapi modsætning til et hash-kort og linket hash-kort, anvender det ikke hashing-princippet overalt, da det ikke bruger et array til at gemme dets poster.

3. Brugerdefineret sortering TreeMap

Hvis vi ikke er tilfredse med den naturlige ordning af TreeMap, kan vi også definere vores egen regel for bestilling ved hjælp af en komparator under konstruktionen af ​​et trækort.

I eksemplet nedenfor ønsker vi, at heltalstasterne ordnes i faldende rækkefølge:

@Test offentlig ugyldighed givenTreeMap_whenOrdersEntriesByComparator_thenCorrect () {TreeMap map = new 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 ()); }

Et hash-kort garanterer ikke rækkefølgen af ​​de lagrede nøgler og garanterer specifikt ikke, at denne ordre forbliver den samme over tid, men et trækort garanterer, at nøglerne altid sorteres efter den angivne rækkefølge.

4. Betydningen af TreeMap Sortering

Det ved vi nu TreeMap gemmer alle sine poster i sorteret rækkefølge. På grund af denne egenskab af trækort kan vi udføre forespørgsler som; find "største", find "mindste", find alle nøgler mindre end eller større end en bestemt værdi osv.

Koden nedenfor dækker kun en lille procentdel af disse tilfælde:

@Test offentlig ugyldighed givenTreeMap_whenPerformsQueries_thenCorrect () {TreeMap map = new TreeMap (); map.put (3, "val"); map.put (2, "val"); map.put (1, "val"); map.put (5, "val"); map.put (4, "val"); Heltal højeste nøgle = map.lastKey (); Heltal laveste nøgle = map.firstKey (); Indstil keysLessThan3 = map.headMap (3) .keySet (); Indstil keysGreaterThanEqTo3 = map.tailMap (3) .keySet (); assertEquals (nyt heltal (5), højeste nøgle); assertEquals (nyt heltal (1), laveste nøgle); assertEquals ("[1, 2]", keysLessThan3.toString ()); assertEquals ("[3, 4, 5]", keysGreaterThanEqTo3.toString ()); }

5. Intern implementering af TreeMap

TreeMap redskaber NavigableMap interface og baserer sit interne arbejde på principperne for rød-sorte træer:

offentlig klasse TreeMap udvider AbstractMap implementerer NavigableMap, Cloneable, java.io.Serializable

Princippet om rød-sorte træer ligger uden for denne artikels anvendelsesområde, men der er vigtige ting at huske for at forstå, hvordan de passer ind i TreeMap.

Først og fremmest, et rød-sort træ er en datastruktur, der består af noder; billede et omvendt mangotræ med dets rod i himlen og grenene vokser nedad. Roden indeholder det første element, der føjes til træet.

Reglen er, at startende fra roden er ethvert element i den venstre gren af ​​en hvilken som helst node altid mindre end elementet i selve noden. De til højre er altid større. Hvad der definerer større eller mindre end bestemmes af den naturlige rækkefølge af elementerne eller den definerede komparator ved konstruktion som vi så tidligere.

Denne regel garanterer, at indtastningerne af et trækort altid vil være i sorteret og forudsigelig rækkefølge.

For det andet, et rød-sort træ er et selvbalancerende binært søgetræ. Denne attribut og ovenstående garanterer, at grundlæggende operationer som søgning, hentning, placering og fjernelse tager logaritmisk tid O (log n).

At være selvbalancerende er nøglen her. Når vi fortsætter med at indsætte og slette poster, skal du se træet vokse længere på den ene kant eller kortere på den anden.

Dette ville betyde, at en operation ville tage kortere tid på den kortere gren og længere tid på den gren, der er længst væk fra roden, noget vi ikke ønsker at ske.

Derfor er dette taget hånd om i designet af rød-sorte træer. For hver indsættelse og sletning opretholdes træets maksimale højde på enhver kant på O (log n) dvs. træet afbalancerer sig kontinuerligt.

Ligesom hash-kort og linket hash-kort synkroniseres ikke et trækort, og derfor er reglerne for brug i et miljø med flere tråde svarende til dem i de to andre kortimplementeringer.

6. Valg af det rigtige kort

Efter at have set på HashMap og LinkedHashMap implementeringer tidligere og nu TreeMap, er det vigtigt at lave en kort sammenligning mellem de tre for at guide os om, hvilken der passer hvor.

Et hash-kort er godt som en generel kortimplementering, der giver hurtig opbevaring og hentning. Det mangler dog på grund af dets kaotiske og uordnede arrangement af poster.

Dette får det til at fungere dårligt i scenarier, hvor der er meget iteration, da hele kapaciteten i det underliggende array påvirker anden gennemgang end blot antallet af poster.

Et linket hash-kort besidder de gode egenskaber ved hash-kort og tilføjer orden til posterne. Det fungerer bedre, hvor der er meget iteration, fordi kun antallet af poster tages i betragtning uanset kapacitet.

Et trækort tager ordre til det næste niveau ved at give fuld kontrol over, hvordan tasterne skal sorteres. På bagsiden tilbyder det dårligere generel ydeevne end de to andre alternativer.

Vi kunne sige en linket hash-kort reducerer kaoset i rækkefølgen af ​​et hash-kort uden at pådrage sig et træskorts ydeevne.

7. Konklusion

I denne artikel har vi udforsket Java TreeMap klasse og dens interne implementering. Da det er det sidste i en række almindelige implementeringer af kortgrænseflader, fortsatte vi også kort med at diskutere, hvor det passer bedst i forhold til de to andre.

Den fulde kildekode til alle eksemplerne i denne artikel kan findes i GitHub-projektet.