TreeMap i Java

Hvis du læser denne artikel, er du højst sandsynligt bekendt med kortgrænsefladen, og hvor den kan anvendes. Hvis ikke, så kom her . I dag vil vi tale om funktionerne i Java TreeMaps implementering, og mere specifikt, hvordan det adskiller sig fra HashMap, og hvordan man bruger det korrekt.

Sammenligning af TreeMap, HashMap og LinkedHashMap

Den mest anvendte implementering af kortgrænsefladen er HashMap. Det er nemt at bruge og garanterer hurtig adgang til data, så det er den bedste kandidat til at løse de fleste problemer. De fleste, men ikke alle. Nogle gange har du brug for at gemme data på en struktureret måde og kunne navigere gennem dem. I dette tilfælde kommer en anden implementering af kortgrænsefladen (TreeMap) til undsætning. TreeMap implementerer NavigableMap- grænsefladen, som arver SortedMap , som igen arver Map-grænsefladen. Ved at implementere NavigableMap- og SortedMap -grænsefladerne modtager TreeMap yderligere funktionalitet, som ikke er tilgængelig i HashMap, men det betaler en pris i forhold til ydeevne. Der er også LinkedHashMapklasse , som også giver dig mulighed for at gemme data i en bestemt rækkefølge (den rækkefølge, du tilføjer dem til kortet). For at forstå forskellene mellem disse tre klasser, se denne tabel: Som du kan se, har disse klasser meget til fælles, men der er også flere forskelle. Selvom TreeMap-klassen er den mest alsidige, kan den ikke altid gemme null som en nøgle. Derudover tager det længst tid at få adgang til elementerne i et TreeMap. Så hvis du ikke har brug for at gemme data i en eller anden sorteret rækkefølge, er det bedre at bruge HashMap eller LinkedHashMap .

Rød-sort træ

Du har sikkert bemærket, at TreeMap under motorhjelmen bruger en datastruktur kaldet et rød-sort træ. Lagring af data i denne struktur er netop det, der giver databestilling. Så hvad er det for et træ? Lad os finde ud af det! Forestil dig, at du skal gemme nummer-streng-par. Tallene 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 og 101 vil være nøgler. Hvis du gemmer data i en traditionel liste, og du skal finde elementet med tast 101, så skal du gå gennem alle 13 elementer for at finde det. For 13 elementer er dette ikke en big deal, men når vi arbejder med en million, vil vi have store problemer. For at løse disse problemer bruger programmører lidt mere komplekse datastrukturer. Det er her det rød-sorte træ kommer ind på scenen!Søgning efter et element begynder ved roden af ​​træet, som i vores tilfælde er 61. Derefter sammenligner vi nodeværdierne med den værdi, vi leder efter. Hvis vores værdi er mindre, så går vi til venstre; hvis den er større, så går vi til højre. Denne proces gentages, indtil vi finder den ønskede værdi eller støder på et element, hvis værdi er nul (et blad af træet). Farverne rød og sort bruges til at forenkle navigation og balancering i træet. Der er regler, der altid skal overholdes, når du bygger et rød-sort træ:

• Roden skal være sort.
• Træets blade skal være sorte.
• En rød knude skal have to sorte underknuder.
• En sort node kan have underordnede noder af enhver farve.
• En sti fra en node til dens blade skal indeholde det samme antal sorte noder.
• Nye noder føjes til blade.

Hvis du betragter reglerne 3, 4 og 5 sammen, kan du forstå, hvordan nodefarve lader os navigere i træet hurtigere: en vej gennem sorte noder er altid kortere end en gennem røde noder. I overensstemmelse hermed bestemmes træets samlede størrelse af antallet af sorte noder, som kaldes den "sorte højde". Den rød-sorte trædatastruktur er implementeret i forskellige programmeringssprog. Der er mange Java-implementeringer på internettet, så vi vil ikke blive hængende her. Lad os i stedet blive ved med at lære TreeMaps funktionalitet at kende.

Metoder, der kommer fra SortedMap- og NavigableMap-grænsefladerne

Ligesom HashMap implementerer TreeMap Map-grænsefladen, hvilket betyder, at TreeMap har alle de metoder, der findes i HashMap. Men TreeMap implementerer også SortedMap- og NavigableMap- grænsefladerne og får dermed yderligere funktionalitet fra dem. SortedMap er en grænseflade, der udvider Map og tilføjer metoder, der er relevante for et sorteret datasæt:

• firstKey() : returnerer nøglen til det første element i kortet
• lastKey() : returnerer nøglen til det sidste element
• headMap(K end) : returnerer et kort, der indeholder alle elementerne i det aktuelle kort, fra begyndelsen til elementet med nøgleslut
• tailMap(K start) : returnerer et kort, der indeholder alle elementerne i det aktuelle kort, fra startelementet til slutningen
• subMap(K start, K ​​end) : returnerer et kort, der indeholder alle elementerne i det aktuelle kort, fra startelementet til elementet med nøgleslut.

NavigableMap er en grænseflade, der udvider SortedMap og tilføjer metoder til at navigere mellem elementer på et kort:

• firstEntry() : returnerer det første nøgleværdi-par
• lastEntry() : returnerer det sidste nøgleværdi-par
• pollFirstEntry() : returnerer og sletter det første par
• pollLastEntry() : returnerer og sletter det sidste par
• loftKey(K obj) : returnerer den mindste nøgle k, der er større end eller lig med nøglen obj. Hvis der ikke er en sådan nøgle, returneres null
• floorKey(K obj) : returnerer den største nøgle k, der er mindre end eller lig med nøglen obj. Hvis der ikke er en sådan nøgle, returneres null
• lowerKey(K obj) : returnerer den største nøgle k, der er mindre end nøglen obj. Hvis der ikke er en sådan nøgle, returneres null
• højereKey(K obj) : returnerer den mindste nøgle k, der er større end nøglen obj. Hvis der ikke er en sådan nøgle, returneres null
• loftEntry(K obj) : svarende til loftKey(K obj) metoden, returnerer kun et nøgle-værdi-par (eller null)
• floorEntry(K obj) : svarende til floorKey(K obj) metoden, returnerer kun et nøgle-værdi-par (eller null)
• lowerEntry(K obj) : svarende til lowerKey(K obj)-metoden, returnerer kun et nøgle-værdi-par (eller null)
• højereEntry(K obj) : svarende til metoden higherKey(K obj), returnerer kun et nøgleværdi-par (eller null)
• descendingKeySet() : returnerer et NavigableSet, der indeholder alle nøgler sorteret i omvendt rækkefølge
• descendingMap() : returnerer et NavigableMap, der indeholder alle par sorteret i omvendt rækkefølge
• navigableKeySet() : returnerer et NavigableSet-objekt, der indeholder alle nøglerne i den rækkefølge, de er gemt i
• headMap(K upperBound, boolean incl) : returnerer et kort, der indeholder par fra begyndelsen til upperBound-elementet. Incl-parameteren angiver, om elementet upperBound skal inkluderes i det returnerede kort
• tailMap(K lowerBound, boolean incl) : funktionalitet svarende til den forrige metode, returnerer kun par fra nedre grænse til slutningen
• subMap(K nedre grænse, boolsk lavInkl, K øvre grænse, boolsk højInkl) : som med de tidligere metoder returnerer par fra nedre grænse til øvre grænse; Argumenterne lowIncl og highIncl angiver, om grænseelementerne skal inkluderes i det nye kort.

Ud over de sædvanlige konstruktører har TreeMap en anden konstruktør, der accepterer en forekomst af en komparator. Denne komparator er ansvarlig for den rækkefølge, som elementerne opbevares i.

Eksempler på TreeMap

Denne overflod af ekstra metoder kan virke unødvendige, men de viser sig at være meget mere nyttige, end du måske er klar over ved første øjekast. Lad os sammen udforske følgende eksempel. Forestil dig, at vi arbejder i marketingafdelingen i en stor virksomhed, og vi har en database med personer, som vi ønsker at vise annoncer til. Der er to detaljer at huske på:

• Vi skal holde styr på antallet af indtryk for hver person
• Algoritmen til at vise annoncer til mindreårige er anderledes.

Lad os oprette en personklasse , som gemmer alle relevante oplysninger om hver person:

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;
   }
}

Vi implementerer logikken i hovedklassen :

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) {}
}

I Main-klassen skal du oprette et TreeMap, hvor hver nøgle repræsenterer en bestemt person, og hver værdi er antallet af annoncevisninger denne måned. Vi giver konstruktøren en komparator, der sorterer folk efter alder. Vi fylder kortet med vilkårlige værdier. Nu ønsker vi at få en reference til den første voksne i vores lille datalager. Det gør vi ved hjælp af Stream API. Så får vi to separate kort, som vi videregiver til de metoder, der viser annoncer. Der er mange, mange måder, vi kunne have udført denne opgave på. TreeMap-klassens arsenal af metoder lader os skabe skræddersyede løsninger til ethvert behov. Du behøver ikke huske dem alle, for du kan altid bruge dokumentationen eller tips fra din IDE. For at styrke det, du har lært, foreslår vi, at du ser en videolektion fra vores Java-kursus Det er alt for nu! Jeg håber, at TreeMap-klassen er klar for dig nu, og at du vil anvende den ordentligt til at løse praktiske kodningsopgaver.