TreeMap i Java

Om du läser den här artikeln är du med största sannolikhet bekant med kartgränssnittet och var det kan användas på lämpligt sätt. Om inte, kom hit . Idag ska vi prata om funktionerna i Java TreeMaps implementering, och mer specifikt hur det skiljer sig från HashMap och hur man använder det korrekt.

Jämför TreeMap, HashMap och LinkedHashMap

Den mest använda implementeringen av kartgränssnittet är HashMap. Det är lätt att använda och garanterar snabb tillgång till data, så det är den bästa kandidaten för att lösa de flesta problem. De flesta, men inte alla. Ibland behöver man lagra data på ett strukturerat sätt och kunna navigera genom den. I det här fallet kommer en annan implementering av kartgränssnittet (TreeMap) till undsättning. TreeMap implementerar NavigableMap- gränssnittet, som ärver SortedMap , som i sin tur ärver Map-gränssnittet. Genom att implementera gränssnitten NavigableMap och SortedMap får TreeMap ytterligare funktionalitet som inte är tillgänglig i HashMap, men det betalar ett pris i form av prestanda. Det finns också LinkedHashMapklass , som också låter dig lagra data i en specifik ordning (den ordning som du lägger till den på kartan). För att förstå skillnaderna mellan dessa tre klasser, titta på den här tabellen: Som du kan se har dessa klasser mycket gemensamt, men det finns också flera skillnader. Även om TreeMap-klassen är den mest mångsidiga, kan den inte alltid lagra null som en nyckel. Dessutom tar det längsta tid att komma åt elementen i en TreeMap. Så om du inte behöver lagra data i någon sorterad ordning är det bättre att använda HashMap eller LinkedHashMap .

Röd-svart träd

Du har säkert märkt att TreeMap under huven använder en datastruktur som kallas ett röd-svart träd. Att lagra data i denna struktur är just det som ger dataordning. Så vad är det här för träd? Låt oss ta reda på det! Föreställ dig att du behöver lagra nummer-strängpar. Siffrorna 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 och 101 kommer att vara nycklar. Om du lagrar data i en traditionell lista och du behöver hitta elementet med nyckel 101, måste du gå igenom alla 13 element för att hitta det. För 13 element är det här ingen stor sak, men när vi arbetar med en miljon kommer vi att ha stora problem. För att lösa dessa problem använder programmerare lite mer komplexa datastrukturer. Det är här det rödsvarta trädet kommer in på scenen!Sökningen efter ett element börjar vid roten av trädet, som i vårt fall är 61. Sedan jämför vi nodvärdena med värdet som vi letar efter. Om vårt värde är mindre, så går vi till vänster; om den är större går vi till höger. Denna process upprepas tills vi hittar det önskade värdet eller stöter på ett element vars värde är null (ett blad av trädet). Färgerna rött och svart används för att förenkla navigering och balansering i trädet. Det finns regler som alltid måste följas när man bygger ett röd-svart träd:

• Roten måste vara svart.
• Trädets blad måste vara svarta.
• En röd nod måste ha två svarta barnnoder.
• En svart nod kan ha barnnoder av vilken färg som helst.
• En väg från en nod till dess blad måste innehålla samma antal svarta noder.
• Nya noder läggs till blad.

Om du betraktar reglerna 3, 4 och 5 tillsammans, kan du förstå hur nodfärg låter oss navigera i trädet snabbare: en väg genom svarta noder är alltid kortare än en genom röda noder. Följaktligen bestäms den totala storleken på trädet av antalet svarta noder, vilket kallas den "svarta höjden". Den röd-svarta träddatastrukturen är implementerad i olika programmeringsspråk. Det finns många Java-implementationer på Internet, så vi kommer inte att dröja här. Låt oss istället fortsätta att lära känna TreeMaps funktionalitet.

Metoder som kommer från SortedMap- och NavigableMap-gränssnitten

Liksom HashMap implementerar TreeMap Map-gränssnittet, vilket innebär att TreeMap har alla metoder som finns i HashMap. Men TreeMap implementerar också SortedMap- och NavigableMap- gränssnitten och får därmed ytterligare funktionalitet från dem. SortedMap är ett gränssnitt som utökar Map och lägger till metoder som är relevanta för en sorterad datamängd:

• firstKey() : returnerar nyckeln för det första elementet i kartan
• lastKey() : returnerar nyckeln för det sista elementet
• headMap(K end) : returnerar en karta som innehåller alla element i den aktuella kartan, från början till elementet med nyckelslutet
• tailMap(K start) : returnerar en karta som innehåller alla element i den aktuella kartan, från startelementet till slutet
• subMap(K start, K ​​end) : returnerar en karta som innehåller alla element i den aktuella kartan, från startelementet till elementet med nyckelslutet.

NavigableMap är ett gränssnitt som utökar SortedMap och lägger till metoder för att navigera mellan element i en karta:

• firstEntry() : returnerar det första nyckel-värdeparet
• lastEntry() : returnerar det sista nyckel-värdeparet
• pollFirstEntry() : returnerar och tar bort det första paret
• pollLastEntry() : returnerar och tar bort det sista paret
• loftKey(K obj) : returnerar den minsta nyckeln k som är större än eller lika med nyckeln obj. Om det inte finns någon sådan nyckel returneras null
• floorKey(K obj) : returnerar den största nyckeln k som är mindre än eller lika med nyckeln obj. Om det inte finns någon sådan nyckel returneras null
• lowerKey(K obj) : returnerar den största nyckeln k som är mindre än nyckeln obj. Om det inte finns någon sådan nyckel returneras null
• högreKey(K obj) : returnerar den minsta nyckeln k som är större än nyckeln obj. Om det inte finns någon sådan nyckel returneras null
• ceilingEntry(K obj) : liknande metoden ceilingKey(K obj), returnerar endast ett nyckel-värdepar (eller null)
• floorEntry(K obj) : liknande metoden floorKey(K obj), returnerar endast ett nyckel-värdepar (eller null)
• lowerEntry(K obj) : liknande metoden lowerKey(K obj), returnerar endast ett nyckel-värdepar (eller null)
• higherEntry(K obj) : liknande metoden higherKey(K obj), returnerar endast ett nyckel-värdepar (eller null)
• descendingKeySet() : returnerar en NavigableSet som innehåller alla nycklar sorterade i omvänd ordning
• descendingMap() : returnerar en NavigableMap som innehåller alla par sorterade i omvänd ordning
• navigableKeySet() : returnerar ett NavigableSet-objekt som innehåller alla nycklar i den ordning som de är lagrade
• headMap(K upperBound, boolean inkl) : returnerar en karta som innehåller par från början till upperBound-elementet. Incl-parametern anger om elementet upperBound ska inkluderas i den returnerade kartan
• tailMap(K lowerBound, boolean incl) : funktionalitet som liknar den tidigare metoden, returnerar endast par från nedre gräns till slutet
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : som med de tidigare metoderna, returnerar par från nedre gräns till övre gräns; Argumenten lowIncl och highIncl indikerar om gränselementen ska inkluderas i den nya kartan.

Utöver de vanliga konstruktörerna har TreeMap en annan konstruktor som accepterar en instans av en komparator. Denna komparator är ansvarig för i vilken ordning elementen lagras.

Exempel på TreeMap

Detta överflöd av extra metoder kan verka onödigt, men de visar sig vara mycket mer användbara än du kanske inser vid första anblicken. Låt oss utforska följande exempel tillsammans. Föreställ dig att vi arbetar på marknadsavdelningen på ett stort företag, och vi har en databas med personer som vi vill visa annonser för. Det finns två detaljer att tänka på:

• Vi måste ha koll på antalet visningar för varje person
• Algoritmen för att visa annonser för minderåriga är annorlunda.

Låt oss skapa en personklass , som lagrar all relevant information om varje 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 implementerar logiken i huvudklassen :

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

Skapa en TreeMap i huvudklassen, där varje nyckel representerar en specifik person, och varje värde är antalet annonsvisningar denna månad. Vi skickar konstruktören en komparator som sorterar människor efter ålder. Vi fyller kartan med godtyckliga värden. Nu vill vi få en referens till den första vuxen i vårt lilla dataförråd. Vi gör detta med hjälp av Stream API. Sedan får vi två separata kartor, som vi vidarebefordrar till metoderna som visar annonser. Det finns många, många sätt vi kunde ha utfört denna uppgift. TreeMap-klassens arsenal av metoder låter oss skapa skräddarsydda lösningar för alla behov. Du behöver inte komma ihåg dem alla, eftersom du alltid kan använda dokumentationen eller tipsen från din IDE. För att förstärka det du lärde dig föreslår vi att du tittar på en videolektion från vår Java-kurs Det var allt tills vidare! Jag hoppas att TreeMap-klassen är tydlig för dig nu, och att du kommer att tillämpa den på rätt sätt för att lösa praktiska kodningsuppgifter.