TreeMap i Java

Hvis du leser denne artikkelen, er du mest sannsynlig kjent med kartgrensesnittet og hvor det kan brukes. Hvis ikke, så kom hit . I dag skal vi snakke om funksjonene til Java TreeMaps implementering, og mer spesifikt, hvordan det skiller seg fra HashMap og hvordan du bruker det riktig.

Sammenligning av TreeMap, HashMap og LinkedHashMap

Den mest brukte implementeringen av kartgrensesnittet er HashMap. Den er enkel å bruke og garanterer rask tilgang til data, så den er den beste kandidaten for å løse de fleste problemer. De fleste, men ikke alle. Noen ganger må du lagre data på en strukturert måte og kunne navigere gjennom dem. I dette tilfellet kommer en annen implementering av kartgrensesnittet (TreeMap) til unnsetning. TreeMap implementerer NavigableMap- grensesnittet, som arver SortedMap , som igjen arver Map-grensesnittet. Ved å implementere grensesnittene NavigableMap og SortedMap får TreeMap tilleggsfunksjonalitet som ikke er tilgjengelig i HashMap, men det betaler en pris i form av ytelse. Det er også LinkedHashMapklasse , som også lar deg lagre data i en bestemt rekkefølge (rekkefølgen du legger dem til på kartet). For å forstå forskjellene mellom disse tre klassene, se på denne tabellen: Som du ser har disse klassene mye til felles, men det er også flere forskjeller. Selv om TreeMap-klassen er den mest allsidige, kan den ikke alltid lagre null som en nøkkel. I tillegg tar det lengst tid å få tilgang til elementene i et TreeMap. Så hvis du ikke trenger å lagre data i en sortert rekkefølge, er det bedre å bruke HashMap eller LinkedHashMap .

Rød-svart tre

Du har sikkert lagt merke til at TreeMap under panseret bruker en datastruktur som kalles et rød-svart tre. Lagring av data i denne strukturen er nettopp det som gir databestilling. Så hva slags tre er dette? La oss finne ut av det! Tenk deg at du må lagre nummer-streng-par. Tallene 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 og 101 vil være nøkler. Hvis du lagrer data i en tradisjonell liste og du trenger å finne elementet med tast 101, må du gå gjennom alle 13 elementene for å finne det. For 13 elementer er ikke dette en stor sak, men når vi jobber med en million, vil vi få store problemer. For å løse disse problemene bruker programmerere litt mer komplekse datastrukturer. Det er her det rød-svarte treet entrer scenen!Søk etter et element begynner ved roten av treet, som i vårt tilfelle er 61. Deretter sammenligner vi nodeverdiene med verdien vi ser etter. Hvis verdien vår er mindre, går vi til venstre; hvis den er større, går vi til høyre. Denne prosessen gjentas til vi finner den ønskede verdien eller møter et element hvis verdi er null (et blad av treet). Fargene rød og svart brukes for å forenkle navigering og balansering av treet. Det er regler som alltid må overholdes når du bygger et rød-svart tre:

• Roten skal være svart.
• Bladene på treet må være svarte.
• En rød node må ha to svarte barnenoder.
• En svart node kan ha underordnede noder av hvilken som helst farge.
• En bane fra en node til dens blader må inneholde samme antall svarte noder.
• Nye noder legges til blader.

Hvis du vurderer regel 3, 4 og 5 sammen, kan du forstå hvordan nodefarge lar oss navigere i treet raskere: en vei gjennom svarte noder er alltid kortere enn en gjennom røde noder. Følgelig bestemmes den totale størrelsen på treet av antall svarte noder, som kalles den "svarte høyden". Den rød-svarte tredatastrukturen er implementert i forskjellige programmeringsspråk. Det er mange Java-implementeringer på Internett, så vi skal ikke dvele her. La oss i stedet fortsette å bli kjent med TreeMaps funksjonalitet.

Metoder som kommer fra SortedMap- og NavigableMap-grensesnittene

I likhet med HashMap implementerer TreeMap Map-grensesnittet, som betyr at TreeMap har alle metodene som finnes i HashMap. Men TreeMap implementerer også SortedMap- og NavigableMap- grensesnittene, og får dermed ekstra funksjonalitet fra dem. SortedMap er et grensesnitt som utvider Map og legger til metoder som er relevante for et sortert datasett:

• firstKey() : returnerer nøkkelen til det første elementet i kartet
• lastKey() : returnerer nøkkelen til det siste elementet
• headMap(K end) : returnerer et kart som inneholder alle elementene i gjeldende kart, fra begynnelsen til elementet med nøkkelslutt
• tailMap(K start) : returnerer et kart som inneholder alle elementene i det gjeldende kartet, fra startelementet til slutten
• subMap(K start, K ​​end) : returnerer et kart som inneholder alle elementene i gjeldende kart, fra startelementet til elementet med nøkkelslutt.

NavigableMap er et grensesnitt som utvider SortedMap og legger til metoder for å navigere mellom elementer i et kart:

• firstEntry() : returnerer det første nøkkelverdi-paret
• lastEntry() : returnerer det siste nøkkelverdi-paret
• pollFirstEntry() : returnerer og sletter det første paret
• pollLastEntry() : returnerer og sletter det siste paret
• loftKey(K obj) : returnerer den minste nøkkelen k som er større enn eller lik nøkkelen obj. Hvis det ikke finnes en slik nøkkel, returneres null
• floorKey(K obj) : returnerer den største nøkkelen k som er mindre enn eller lik nøkkelen obj. Hvis det ikke finnes en slik nøkkel, returneres null
• lowerKey(K obj) : returnerer den største nøkkelen k som er mindre enn nøkkelen obj. Hvis det ikke finnes en slik nøkkel, returneres null
• høyereKey(K obj) : returnerer den minste nøkkelen k som er større enn nøkkelen obj. Hvis det ikke finnes en slik nøkkel, returneres null
• ceilingEntry(K obj) : ligner på ceilingKey(K obj)-metoden, returnerer bare et nøkkelverdi-par (eller null)
• floorEntry(K obj) : ligner på floorKey(K obj)-metoden, returnerer bare et nøkkelverdi-par (eller null)
• lowerEntry(K obj) : lignende metoden lowerKey(K obj), returnerer bare et nøkkelverdi-par (eller null)
• høyereEntry(K obj) : lik metoden higherKey(K obj), returnerer bare et nøkkelverdi-par (eller null)
• descendingKeySet() : returnerer et NavigableSet som inneholder alle nøklene sortert i omvendt rekkefølge
• descendingMap() : returnerer et NavigableMap som inneholder alle parene sortert i omvendt rekkefølge
• navigableKeySet() : returnerer et NavigableSet-objekt som inneholder alle nøklene i den rekkefølgen de er lagret
• headMap(K upperBound, boolean incl) : returnerer et kart som inneholder par fra begynnelsen til upperBound-elementet. Incl-parameteren indikerer om opperBound-elementet skal inkluderes i det returnerte kartet
• tailMap(K nedre grense, boolsk inkl.) : funksjonalitet som ligner på forrige metode, returnerer bare par fra nedre grense til slutten
• subMap(K nedre grense, boolsk lavInkl, K øvre grense, boolsk høyInkl) : som med de forrige metodene, returnerer par fra nedre grense til øvre grense; Argumentene lowIncl og highIncl indikerer om grenseelementene skal inkluderes i det nye kartet.

I tillegg til de vanlige konstruktørene, har TreeMap en annen konstruktør som godtar en forekomst av en komparator. Denne komparatoren er ansvarlig for rekkefølgen elementene lagres i.

Eksempler på TreeMap

Denne overfloden av ekstra metoder kan virke unødvendig, men de viser seg å være mye mer nyttige enn du kanskje er klar over ved første øyekast. La oss utforske følgende eksempel sammen. Tenk deg at vi jobber i markedsavdelingen til et stort selskap, og vi har en database med personer vi ønsker å vise annonser til. Det er to detaljer å huske på:

• Vi må holde oversikt over antall visninger for hver person
• Algoritmen for å vise annonser til mindreårige er annerledes.

La oss lage en personklasse , som vil lagre all relevant informasjon 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 hovedklassen oppretter du et trekart, der hver nøkkel representerer en bestemt person, og hver verdi er antall annonsevisninger denne måneden. Vi passerer konstruktøren en komparator som sorterer folk etter alder. Vi fyller kartet med vilkårlige verdier. Nå ønsker vi å få en referanse til den første voksne i vårt lille datalager. Vi gjør dette ved å bruke Stream API. Deretter får vi to separate kart, som vi overfører til metodene som viser annonser. Det er mange, mange måter vi kunne ha oppnådd denne oppgaven på. TreeMap-klassens arsenal av metoder lar oss lage tilpassede løsninger for ethvert behov. Du trenger ikke å huske dem alle, fordi du alltid kan bruke dokumentasjonen eller tipsene fra IDE-en din. For å forsterke det du lærte, foreslår vi at du ser en videoleksjon fra vårt Java-kurs Det er alt for nå! Jeg håper at TreeMap-klassen er tydelig for deg nå, og at du vil bruke den riktig for å løse praktiske kodeoppgaver.