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.