Mappa ordinata

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:

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.

Metodi SortedMap nella classe TreeMap

1. 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

2. 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

3. 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}

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}

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.