TreeMap în Java

Dacă citiți acest articol, cel mai probabil sunteți familiarizat cu interfața Hartă și unde poate fi aplicată în mod corespunzător. Dacă nu, atunci vino aici . Astăzi vom vorbi despre caracteristicile implementării Java TreeMap și, mai precis, despre cum diferă de HashMap și despre cum să-l folosești corect.

Compararea TreeMap, HashMap și LinkedHashMap

Cea mai utilizată implementare a interfeței Map este HashMap. Este ușor de utilizat și garantează acces rapid la date, deci este cel mai bun candidat pentru rezolvarea majorității problemelor. Majoritatea, dar nu toate. Uneori trebuie să stocați datele într-un mod structurat și să puteți naviga prin ele. În acest caz, o altă implementare a interfeței Map (TreeMap) vine în ajutor. TreeMap implementează interfața NavigableMap , care moștenește SortedMap , care la rândul său moștenește interfața Map. Prin implementarea interfețelor NavigableMap și SortedMap , TreeMap primește funcționalitate suplimentară care nu este disponibilă în HashMap, dar plătește un preț în ceea ce privește performanța. Există și LinkedHashMapclass , care vă permite de asemenea să stocați datele într-o anumită ordine (ordinea în care le adăugați pe hartă). Pentru a înțelege diferențele dintre aceste trei clase, priviți acest tabel: După cum puteți vedea, aceste clase au multe în comun, dar există și câteva diferențe. Deși clasa TreeMap este cea mai versatilă, nu poate stoca întotdeauna null ca cheie. În plus, accesarea elementelor unui TreeMap durează cel mai mult timp. Deci, dacă nu aveți nevoie să stocați datele într-o ordine sortată, este mai bine să utilizați HashMap sau LinkedHashMap .

Copac roșu-negru

Probabil ați observat că, sub capotă, TreeMap folosește o structură de date numită arbore roșu-negru. Stocarea datelor în această structură este tocmai ceea ce asigură ordonarea datelor. Deci, ce fel de copac este acesta? Să ne dăm seama! Imaginați-vă că trebuie să stocați perechi Number-String. Numerele 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 și 101 vor fi chei. Dacă stocați date într-o listă tradițională și trebuie să găsiți elementul cu cheia 101, atunci va trebui să parcurgeți toate cele 13 elemente pentru a-l găsi. Pentru 13 elemente, asta nu este mare lucru, dar când lucrăm cu un milion, vom avea mari probleme. Pentru a rezolva aceste probleme, programatorii folosesc structuri de date ceva mai complexe. Aici intră în scenă copacul roșu-negru!Căutarea unui element începe de la rădăcina arborelui, care în cazul nostru este 61. Apoi comparăm valorile nodurilor cu valoarea pe care o căutăm. Dacă valoarea noastră este mai mică, atunci mergem la stânga; daca este mai mare, atunci mergem la dreapta. Acest proces se repetă până când găsim valoarea dorită sau întâlnim un element a cărui valoare este nulă (o frunză a arborelui). Culorile roșu și negru sunt folosite pentru a simplifica navigarea și echilibrarea copacului. Există reguli care trebuie respectate întotdeauna la construirea unui copac roșu-negru:

• Rădăcina trebuie să fie neagră.
• Frunzele copacului trebuie să fie negre.
• Un nod roșu trebuie să aibă două noduri copii negre.
• Un nod negru poate avea noduri copii de orice culoare.
• O cale de la un nod la frunzele sale trebuie să conțină același număr de noduri negre.
• La frunze sunt adăugate noduri noi.

Dacă luați în considerare regulile 3, 4 și 5 împreună, puteți înțelege cum culoarea nodurilor ne permite să navigăm mai repede în arbore: o cale prin nodurile negre este întotdeauna mai scurtă decât una prin nodurile roșii. În consecință, dimensiunea totală a copacului este determinată de numărul de noduri negre, care se numește „înălțimea neagră”. Structura de date arbore roșu-negru este implementată în diferite limbaje de programare. Există o mulțime de implementări Java pe Internet, așa că nu vom zăbovi aici. În schimb, să continuăm să cunoaștem funcționalitatea TreeMap.

Metode care provin din interfețele SortedMap și NavigableMap

La fel ca HashMap, TreeMap implementează interfața Map, ceea ce înseamnă că TreeMap are toate metodele care există în HashMap. Dar TreeMap implementează și interfețele SortedMap și NavigableMap și, astfel, câștigă funcționalități suplimentare de la acestea. SortedMap este o interfață care extinde Map și adaugă metode relevante pentru un set de date sortat:

• firstKey() : returnează cheia primului element din hartă
• lastKey() : returnează cheia ultimului element
• headMap(K end) : returnează o hartă care conține toate elementele hărții curente, de la început până la elementul cu sfârșitul cheii
• tailMap(K start) : returnează o hartă care conține toate elementele hărții curente, de la elementul de început până la sfârșit
• subMap(K start, K ​​end) : returnează o hartă care conține toate elementele hărții curente, de la elementul de început până la elementul cu sfârșitul cheii.

NavigableMap este o interfață care extinde SortedMap și adaugă metode de navigare între elementele unei hărți:

• firstEntry() : returnează prima pereche cheie-valoare
• lastEntry() : returnează ultima pereche cheie-valoare
• pollFirstEntry() : returnează și șterge prima pereche
• pollLastEntry() : returnează și șterge ultima pereche
• ceilingKey(K obj) : returnează cea mai mică cheie k care este mai mare sau egală cu cheia obj. Dacă nu există o astfel de cheie, returnează null
• floorKey(K obj) : returnează cea mai mare cheie k care este mai mică sau egală cu cheia obj. Dacă nu există o astfel de cheie, returnează null
• lowerKey(K obj) : returnează cea mai mare cheie k care este mai mică decât cheia obj. Dacă nu există o astfel de cheie, returnează null
• higherKey(K obj) : returnează cea mai mică cheie k care este mai mare decât cheia obj. Dacă nu există o astfel de cheie, returnează null
• ceilingEntry(K obj) : similar cu metoda ceilingKey(K obj), returnează doar o pereche cheie-valoare (sau nulă)
• floorEntry(K obj) : similar cu metoda floorKey(K obj), returnează doar o pereche cheie-valoare (sau nulă)
• lowerEntry(K obj) : similar cu metoda lowerKey(K obj), returnează doar o pereche cheie-valoare (sau nulă)
• higherEntry(K obj) : similar cu metoda higherKey(K obj), returnează doar o pereche cheie-valoare (sau nulă)
• descendingKeySet() : returnează un NavigableSet care conține toate cheile sortate în ordine inversă
• descendingMap() : returnează un NavigableMap care conține toate perechile sortate în ordine inversă
• navigableKeySet() : returnează un obiect NavigableSet care conține toate cheile în ordinea în care sunt stocate
• headMap(K upperBound, boolean incl) : returnează o hartă care conține perechi de la început la elementul upperBound. Parametrul incl indică dacă să includă elementul upperBound în harta returnată
• tailMap(K lowerBound, boolean incl) : funcționalitate similară cu metoda anterioară, returnează numai perechi de la lowBound până la sfârșit
• subMap(K LowBound, boolean lowIncl, K upperBound, boolean highIncl) : ca și în cazul metodelor anterioare, returnează perechi de la lowBound la upperBound; argumentele lowIncl și highIncl indică dacă să includă elementele de limită în noua hartă.

În plus față de constructorii obișnuiți, TreeMap are un alt constructor care acceptă o instanță a unui comparator. Acest comparator este responsabil pentru ordinea în care sunt stocate elementele.

Exemple de TreeMap

Această abundență de metode suplimentare poate părea inutilă, dar se dovedesc a fi mult mai utile decât ați putea realiza la prima vedere. Să explorăm împreună următorul exemplu. Imaginează-ți că lucrăm în departamentul de marketing al unei companii mari și că avem o bază de date cu persoane cărora dorim să le afișăm reclame. Sunt două detalii de reținut:

• Trebuie să urmărim numărul de afișări pentru fiecare persoană
• Algoritmul de afișare a reclamelor minorilor este diferit.

Să creăm o clasă Persoană , care va stoca toate informațiile relevante despre fiecare persoană:

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

Implementăm logica în clasa Main :

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

În clasa principală, creați o hartă arborescentă, în care fiecare cheie reprezintă o anumită persoană, iar fiecare valoare este numărul de afișări de anunțuri în această lună. Trecem constructorului un comparator care sortează oamenii după vârstă. Umplem harta cu valori arbitrare. Acum vrem să obținem o referință la primul adult din micul nostru depozit de date. Facem acest lucru folosind API-ul Stream. Apoi obținem două hărți separate, pe care le trecem la metodele care arată reclame. Există multe, multe moduri în care am fi putut îndeplini această sarcină. Arsenalul de metode al clasei TreeMap ne permite să creăm soluții personalizate pentru fiecare nevoie. Nu trebuie să le amintiți pe toate, deoarece puteți utiliza oricând documentația sau sfaturile din IDE-ul dumneavoastră. Pentru a consolida ceea ce ați învățat, vă sugerăm să urmăriți o lecție video de la Cursul nostru Java Asta este tot pentru acum! Sper că clasa TreeMap vă este clară acum și că o veți aplica corect în rezolvarea sarcinilor practice de codare.