Mappa ordinata
In questa lezione studieremo l' interfaccia SortedMap . Esploreremo nuovi metodi che appaiono in questa interfaccia, così come le caratteristiche di un'implementazione di SortedMap — TreeMap — e le differenze tra le implementazioni, così come i loro vantaggi rispetto a HashMap .
Vediamo come appare la gerarchia delle mappe. Presta particolare attenzione all'interfaccia SortedMap e alla sua implementazione TreeMap : sono il nostro obiettivo oggi:

L' interfaccia SortedMap estende l' interfaccia Map . In molti modi, è simile a SortedSet (che a sua volta estende Set ), poiché entrambi descrivono funzionalità simili per l'archiviazione e l'utilizzo di valori ordinati.
SortedSet lavora con e memorizza<TValue>, ma SortedMap memorizza<TKey, TValue>. È una mappa che memorizza tutti i suoi elementi in ordine crescente delle loro chiavi.
L' interfaccia SortedMap estende Map . Aggiunge i seguenti metodi:
Metodo | Descrizione |
---|---|
TChiave primaChiave() | Restituisce la chiave del primo elemento della mappa |
TChiave ultimaChiave() | Restituisce la chiave dell'ultimo elemento della mappa |
SortedMap<TKey, TValue> headMap(TKey end) | Restituisce una SortedMap che contiene tutti gli elementi della SortedMap originale fino a includere l'elemento con la fine della chiave |
SortedMap<TKey, Tvalue> tailMap(K inizio) | Restituisce un SortedMap che contiene tutti gli elementi dell'originale SortedMap , a partire dall'elemento con inizio chiave (incluso) |
SortedMap<TKey, TValue> subMap(TKey inizio, TKey fine) | Restituisce un SortedMap che contiene tutti gli elementi dell'originale SortedMap , dall'elemento con inizio chiave all'elemento con fine chiave (esclusa fine) |
Classe TreeMap
La classe TreeMap è un'implementazione dell'interfaccia SortedMap . Cioè, TreeMap implementa tutti i metodi aggiunti da SortedMap oltre a quelli standard dall'interfaccia Map .
Puoi creare un oggetto TreeMap usando costruttori come questi:
-
TreeMap() : crea una mappa vuota implementata come un albero;
-
TreeMap(Map<? extends TKey, ? extends TValue> map) : crea un albero e aggiunge tutti gli elementi dalla mappa di input;
-
TreeMap(SortedMap<TKey, ? extends TValue> smap) : crea un albero e aggiunge tutti gli elementi dalla mappa ordinata di input;
-
TreeMap(Comparator<? super TKey> comparator) : crea un albero vuoto — il comparatore verrà utilizzato per ordinare tutti gli elementi man mano che vengono aggiunti successivamente.
Qui TKey è il tipo delle chiavi nelle coppie memorizzate e TValue è il tipo dei valori nelle coppie memorizzate nella TreeMap .
Il comparatore è piuttosto importante per SortedMap / TreeMap . Stabilisce le regole per ordinare - o ordinare - la nostra mappa. Se non forniamo un comparatore, quando creiamo un SortedMap verrà utilizzato l'ordinamento naturale delle nostre chiavi .
Aggiunta di elementi a una TreeMap
Gli elementi vengono aggiunti a una mappa come coppie utilizzando il metodo put() . La chiave viene passata come primo argomento e il valore viene passato come secondo. Ad esempio, supponiamo di voler creare un elenco di studenti e i relativi voti.
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);
Risultato:
Quando aggiungiamo una coppia chiave-valore, se la chiave esiste già nella raccolta, il vecchio valore viene sostituito dal nuovo valore. Questo comportamento è illustrato nel nostro esempio con due coppie che hanno la stessa chiave — ("Oliver", 3) e ("Oliver", 5) .
Diamo un'occhiata a un esempio con un comparatore che creiamo. Supponiamo di voler memorizzare gli elementi ordinati per lunghezza della stringa chiave. Se la lunghezza delle chiavi è uguale, ordineremo alfabeticamente (l'ordine naturale delle stringhe):
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);
Ecco la sequenza risultante:
Questo comportamento rende una TreeMap come un array o un elenco ordinato i cui indici sono parole ( String ) anziché numeri.
È importante notare che quasi tutti i tipi possono essere KeyType o ValueType. Ci sono alcuni piccoli requisiti aggiuntivi per il KeyType e li imparerai quando studierai le raccolte in modo più dettagliato. |
Metodi SortedMap nella classe TreeMap
-
Se hai bisogno di ottenere la chiave del primo studente, puoi usare il metodo firstKey() :
String firstKey = map.firstKey(); System.out.println("First key → " + firstKey);
Risultato: Prima chiave → Anthony
-
Se hai bisogno di ottenere la chiave dell'ultimo studente, puoi usare il metodo lastKey() :
String lastKey = map.lastKey(); System.out.println("Last key → " + lastKey);
Risultato: Last Key → Jeff
-
Ottieni tutti gli oggetti che vengono dopo l'oggetto con la chiave " Sara ":
Map<String, Integer> tailMap = map.tailMap("Sara"); System.out.println("tailMap: " + tailMap);
Risultato: tailMap: {Sara=5, Jeff=4}
-
Ottieni tutti gli oggetti che precedono l'oggetto con la chiave " Nick ":
System.out.println("headMap: " + headMap); Map<String, Integer> headMap = map.headMap("Nick");
Risultato: headMap: {Anthony=5}
-
Prendi tutti gli oggetti che vengono dopo l'oggetto con la chiave " Oliver " e vengono prima dell'oggetto con la chiave " Sara ":
Map<String, Integer> subMap = map.subMap("Oliver", "Sara"); System.out.println("subMap: " + subMap);
Risultato: mappa secondaria: {Oliver=5, Roxy=5}
Confronto tra HashMap e SortedMap/TreeMap
Parliamo di come gli elementi sono ordinati e memorizzati:
-
Poiché HashMap non ci fornisce alcuna garanzia sull'ordine durante l'iterazione, l'ordine può cambiare completamente quando vengono aggiunti nuovi elementi.
-
In TreeMap , l'ordine è basato sull'"ordinamento naturale" delle chiavi secondo il loro metodo compareTo() (o un comparatore che forniamo). Inoltre, non dimenticare che TreeMap implementa l' interfaccia SortedMap , che contiene metodi che dipendono da questo ordinamento.
Passiamo ora a considerare le prestazioni e la velocità:
-
HashMap è una mappa basata su chiavi di hashing. Può inserire e ottenere elementi inO(1), tempo costante. Per supportare ciò, le chiavi devono implementarehashCode()eequals().
-
TreeMap è una mappa ad albero. Le sue operazioni di inserimento e recupero richiedono un tempo logaritmico, ovveroO(log n), che dipende dal numero di elementi nella mappa. Ciò è necessario affinché gli elementi abbiano una sorta di meccanismo di confronto fornito dalla nostra chiave o da un comparatore esterno. Questo meccanismo determina l'ordine di iterazione.
E questi fattori ci aiutano a decidere quali raccolte utilizzare e quando.
Se abbiamo bisogno di memorizzare i valori in un certo ordine, la scelta è ovvia: abbiamo bisogno di una SortedMap . Sebbene sia un po' più lento di HashMap , svolge compiti importanti per noi.
Come accennato in precedenza, SortedMap può darci la prima (o l'ultima) chiave, o valore, o coppia chiave-valore nella nostra mappa, indipendentemente da quando quel valore è stato aggiunto. L' implementazione HashMap non può farlo.
Ad esempio, considera una mappa con chiavi (i nomi degli studenti) e valori (i loro voti). Supponiamo di voler lavorare con un elenco in ordine alfabetico inverso.
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);
L'esempio mostra che l'utilizzo di una HashMap rende l'attività più complicata, poiché HashMap non garantisce né l'ordine di archiviazione né l'ordine di ottenimento degli elementi dalla mappa.
GO TO FULL VERSION