Harta sortată

Harta sortată

În această lecție, vom studia interfața SortedMap . Vom explora metode noi care apar în această interfață, precum și caracteristicile unei implementări a SortedMap — TreeMap — și diferențele dintre implementări, precum și avantajele acestora în comparație cu HashMap .

Să vedem cum arată ierarhia hărților. Acordați o atenție deosebită interfeței SortedMap și implementării sale TreeMap - acestea ne concentrează astăzi:

Interfața SortedMap extinde interfața Map . În multe privințe, este similar cu SortedSet (care, la rândul său, extinde Set ), deoarece ambele descriu funcționalități similare pentru stocarea și utilizarea valorilor sortate.

SortedSet funcționează cu și stocheazăobiecte<TValue>perechi<TKey, TValue>Este o hartă care stochează toate elementele sale în ordinea crescătoare a cheilor lor.

Interfața SortedMap extinde Map . Se adaugă următoarele metode:

Clasa TreeMap

Clasa TreeMap este o implementare a interfeței SortedMap . Adică, TreeMap implementează toate metodele adăugate de SortedMap precum și pe cele standard din interfața Map .

Puteți crea un obiect TreeMap folosind constructori ca aceștia:

• TreeMap() : creează o hartă goală implementată ca arbore;

• TreeMap(Map<? extins TKey, ? extins TValue> map) : creează un arbore și adaugă toate elementele din harta de intrare;

• TreeMap(SortedMap<TKey, ? extins TValue> smap) : creează un arbore și adaugă toate elementele din harta sortată de intrare;

• TreeMap(Comparator<? super TKey> comparator) : creează un arbore gol — comparatorul va fi folosit pentru a sorta toate elementele pe măsură ce sunt adăugate ulterior.

Aici TKey este tipul cheilor din perechile stocate, iar TValue este tipul valorilor din perechile stocate în TreeMap .

Comparatorul este destul de important pentru SortedMap / TreeMap . Stabilește regulile pentru sortarea sau ordonarea hărții noastre. Dacă nu oferim un comparator, atunci ordinea naturală a cheilor noastre va fi folosită atunci când creăm un SortedMap .

Adăugarea de elemente la o hartă arboreală

Elementele sunt adăugate unei hărți ca perechi folosind metoda put() . Cheia este transmisă ca prim argument, iar valoarea este transmisă ca al doilea. De exemplu, să presupunem că vrem să creăm o listă de studenți și notele acestora.

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Rezultat:

Când adăugăm o pereche cheie-valoare, dacă cheia există deja în colecție, atunci valoarea veche este înlocuită cu noua valoare. Acest comportament este ilustrat în exemplul nostru cu două perechi care au aceeași cheie — ("Oliver", 3) și ("Oliver", 5) .

Să ne uităm la un exemplu cu un Comparator pe care l-am creat. Să presupunem că vrem să stocăm elementele sortate după lungimea șirului de chei. Dacă lungimea tastelor este egală, atunci vom sorta alfabetic (ordonarea naturală a șirurilor):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Iată secvența rezultată:

Acest comportament face ca un TreeMap să fie ca o matrice sau o listă sortată ai cărei indici sunt cuvinte ( String ) în loc de numere.

Metode SortedMap din clasa TreeMap

1. Dacă trebuie să obțineți cheia primului student, puteți utiliza metoda firstKey() :

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   Rezultat: Prima cheie → Anthony

2. Dacă trebuie să obțineți cheia ultimului student, puteți utiliza metoda lastKey() :

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   Rezultat: Ultima cheie → Jeff

3. Obțineți toate obiectele care vin după obiect cu cheia " Sara ":

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   Rezultat: tailMap: {Sara=5, Jeff=4}

4. Obțineți toate obiectele care vin înaintea obiectului cu cheia „ Nick ”:

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   Rezultat: headMap: {Anthony=5}

5. Obțineți toate obiectele care vin după obiect cu cheia „ Oliver ” și vin înaintea obiectului cu cheia „ Sara ”:

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   Rezultat: subHartă: {Oliver=5, Roxy=5}

Comparație între HashMap și SortedMap/TreeMap

Să vorbim despre modul în care sunt ordonate și stocate elementele:

• Deoarece HashMap nu ne oferă nicio garanție cu privire la ordinea la iterare, ordinea se poate schimba complet atunci când sunt adăugate elemente noi.

• În TreeMap , ordinea se bazează pe „ordonarea naturală” a cheilor în funcție de metoda lor compareTo() (sau un Comparator pe care îl oferim). De asemenea, nu uitați că TreeMap implementează interfața SortedMap , care conține metode care depind de această ordine de sortare.

Acum ne luăm în considerare performanța și viteza:

• HashMap este o hartă bazată pe chei de hashing. Poate insera și obține elemente înO(1), timp constant. Pentru a sprijini acest lucru, cheile trebuie să implementezehashCode()șiequals().

• TreeMap este o hartă bazată pe arbori. Operațiile sale de inserare și preluare durează timp logaritmic, adicăO(log n), care depinde de numărul de elemente din hartă. Acest lucru este necesar pentru ca elementele să aibă un fel de mecanism de comparație furnizat fie de cheia noastră, fie de un comparator extern. Acest mecanism determină ordinea iterației.

Și acești factori ne ajută să decidem ce colecții să folosim și când.

Dacă trebuie să stocăm valori într-o anumită ordine, alegerea este evidentă - avem nevoie de un SortedMap . Deși este puțin mai lent decât HashMap , îndeplinește sarcini importante pentru noi.

După cum am menționat mai devreme, SortedMap ne poate oferi prima (sau ultima) cheie, sau valoare sau pereche cheie-valoare din harta noastră, indiferent de momentul în care a fost adăugată valoarea respectivă. Implementarea HashMap nu poate face acest lucru .

De exemplu, luați în considerare o hartă cu chei (numele elevilor) și valori (notele lor). Să presupunem că vrem să lucrăm cu o listă în ordine alfabetică inversă.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

Exemplul arată că utilizarea unui HashMap face sarcina mai complicată, deoarece HashMap nu garantează nici ordinea stocării, nici ordinea obținerii elementelor din hartă.