Mappa ad albero in Java

Se stai leggendo questo articolo, molto probabilmente conosci l'interfaccia della mappa e dove può essere applicata in modo appropriato. Se no, allora vieni qui . Oggi parleremo delle caratteristiche dell'implementazione di Java TreeMap e, più specificamente, di come differisce da HashMap e di come usarlo correttamente.

Confronto tra TreeMap, HashMap e LinkedHashMap

L'implementazione più utilizzata dell'interfaccia Map è HashMap. È facile da usare e garantisce un rapido accesso ai dati, quindi è il miglior candidato per risolvere la maggior parte dei problemi. La maggior parte, ma non tutti. A volte è necessario archiviare i dati in modo strutturato ed essere in grado di navigare attraverso di essi. In questo caso viene in soccorso un'altra implementazione dell'interfaccia Map (TreeMap). TreeMap implementa l' interfaccia NavigableMap , che eredita SortedMap , che a sua volta eredita l'interfaccia Map. Implementando le interfacce NavigableMap e SortedMap , TreeMap riceve funzionalità aggiuntive che non sono disponibili in HashMap, ma paga un prezzo in termini di prestazioni. C'è anche la LinkedHashMapclass , che consente anche di memorizzare i dati in un ordine specifico (l'ordine in cui li si aggiunge alla mappa). Per comprendere le differenze tra queste tre classi, guarda questa tabella: Come puoi vedere, queste classi hanno molto in comune, ma ci sono anche molte differenze. Sebbene la classe TreeMap sia la più versatile, non può sempre memorizzare null come chiave. Inoltre, l'accesso agli elementi di una TreeMap richiede il tempo più lungo. Quindi, se non è necessario archiviare i dati in un ordine ordinato, è meglio utilizzare HashMap o LinkedHashMap .

Albero rosso-nero

Probabilmente hai notato che, sotto il cofano, TreeMap utilizza una struttura dati chiamata albero rosso-nero. L'archiviazione dei dati in questa struttura è esattamente ciò che fornisce l'ordinamento dei dati. Quindi che tipo di albero è questo? Scopriamolo! Immagina di dover memorizzare coppie di stringhe numeriche. I numeri 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 e 101 saranno le chiavi. Se memorizzi i dati in un elenco tradizionale e devi trovare l'elemento con la chiave 101, dovrai scorrere tutti e 13 gli elementi per trovarlo. Per 13 elementi, questo non è un grosso problema, ma quando lavoriamo con un milione, avremo grossi problemi. Per risolvere questi problemi, i programmatori utilizzano strutture dati leggermente più complesse. È qui che entra in scena l'albero rosso-nero!La ricerca di un elemento inizia dalla radice dell'albero, che nel nostro caso è 61. Quindi confrontiamo i valori del nodo con il valore che stiamo cercando. Se il nostro valore è inferiore, andiamo a sinistra; se è maggiore, allora andiamo a destra. Questo processo si ripete finché non troviamo il valore desiderato o incontriamo un elemento il cui valore è nullo (una foglia dell'albero). I colori rosso e nero sono usati per semplificare la navigazione e il bilanciamento dell'albero. Ci sono regole che devono essere sempre osservate quando si costruisce un albero rosso-nero:

• La radice deve essere nera.
• Le foglie dell'albero devono essere nere.
• Un nodo rosso deve avere due nodi figlio neri.
• Un nodo nero può avere nodi figlio di qualsiasi colore.
• Un percorso da un nodo alle sue foglie deve contenere lo stesso numero di nodi neri.
• Nuovi nodi vengono aggiunti alle foglie.

Se consideri insieme le regole 3, 4 e 5, puoi capire come il colore dei nodi ci permetta di navigare più velocemente nell'albero: un percorso attraverso i nodi neri è sempre più breve di uno attraverso i nodi rossi. Di conseguenza, la dimensione totale dell'albero è determinata dal numero di nodi neri, chiamato "altezza nera". La struttura dati ad albero rosso-nero è implementata in vari linguaggi di programmazione. Ci sono molte implementazioni Java su Internet, quindi non ci soffermeremo qui. Continuiamo invece a conoscere le funzionalità di TreeMap.

Metodi che provengono dalle interfacce SortedMap e NavigableMap

Come HashMap, TreeMap implementa l'interfaccia Map, il che significa che TreeMap ha tutti i metodi esistenti in HashMap. Ma TreeMap implementa anche le interfacce SortedMap e NavigableMap , ottenendo così funzionalità aggiuntive da esse. SortedMap è un'interfaccia che estende Map e aggiunge metodi relativi a un set di dati ordinato:

• firstKey() : restituisce la chiave del primo elemento nella mappa
• lastKey() : restituisce la chiave dell'ultimo elemento
• headMap(K end) : restituisce una mappa che contiene tutti gli elementi della mappa corrente, dall'inizio all'elemento con la chiave end
• tailMap(K start) : restituisce una mappa che contiene tutti gli elementi della mappa corrente, dall'elemento iniziale alla fine
• subMap(K start, K ​​end) : restituisce una mappa che contiene tutti gli elementi della mappa corrente, dall'elemento start all'elemento con la chiave end.

NavigableMap è un'interfaccia che estende SortedMap e aggiunge metodi per navigare tra gli elementi di una mappa:

• firstEntry() : restituisce la prima coppia chiave-valore
• lastEntry() : restituisce l'ultima coppia chiave-valore
• pollFirstEntry() : restituisce ed elimina la prima coppia
• pollLastEntry() : restituisce ed elimina l'ultima coppia
• ceilingKey(K obj) : restituisce la chiave più piccola k maggiore o uguale alla chiave obj. Se non esiste tale chiave, restituisce null
• floorKey(K obj) : restituisce la chiave più grande k minore o uguale alla chiave obj. Se non esiste tale chiave, restituisce null
• lowerKey(K obj) : restituisce la chiave più grande k minore della chiave obj. Se non esiste tale chiave, restituisce null
• upperKey(K obj) : restituisce la chiave più piccola k che è più grande della chiave obj. Se non esiste tale chiave, restituisce null
• ceilingEntry(K obj) : simile al metodo ceilingKey(K obj), restituisce solo una coppia chiave-valore (o null)
• floorEntry(K obj) : simile al metodo floorKey(K obj), restituisce solo una coppia chiave-valore (o null)
• lowerEntry(K obj) : simile al metodo lowerKey(K obj), restituisce solo una coppia chiave-valore (o null)
• upperEntry(K obj) : simile al metodo upperKey(K obj), restituisce solo una coppia chiave-valore (o null)
• discendenteKeySet() : restituisce un NavigableSet contenente tutte le chiavi ordinate in ordine inverso
• discendenteMap() : restituisce una NavigableMap contenente tutte le coppie ordinate in ordine inverso
• navigableKeySet() : restituisce un oggetto NavigableSet contenente tutte le chiavi nell'ordine in cui sono memorizzate
• headMap(K upperBound, boolean incl) : restituisce una mappa che contiene coppie dall'inizio all'elemento upperBound. Il parametro incl indica se includere l'elemento upperBound nella mappa restituita
• tailMap(K lowerBound, boolean incl) : funzionalità simile al metodo precedente, restituisce solo coppie da lowerBound alla fine
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : come con i metodi precedenti, restituisce le coppie da lowerBound a upperBound; gli argomenti lowIncl e highIncl indicano se includere gli elementi di contorno nella nuova mappa.

Oltre ai soliti costruttori, TreeMap ha un altro costruttore che accetta un'istanza di un comparatore. Questo comparatore è responsabile dell'ordine in cui gli elementi vengono memorizzati.

Esempi di TreeMap

Questa abbondanza di metodi extra può sembrare superflua, ma si rivelano molto più utili di quanto potresti immaginare a prima vista. Esploriamo insieme il seguente esempio. Immagina di lavorare nel reparto marketing di una grande azienda e di avere un database di persone a cui vogliamo mostrare annunci. Ci sono due dettagli da tenere a mente:

• Dobbiamo tenere traccia del numero di impressioni per ogni persona
• L'algoritmo per la visualizzazione degli annunci ai minori è diverso.

Creiamo una classe Person , che memorizzerà tutte le informazioni rilevanti su ogni persona:

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

Implementiamo la logica nella classe 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) {}
}

Nella classe Main, crea una TreeMap, in cui ogni chiave rappresenta una persona specifica e ogni valore è il numero di impressioni dell'annuncio questo mese. Passiamo al costruttore un comparatore che ordina le persone per età. Riempiamo la mappa con valori arbitrari. Ora vogliamo ottenere un riferimento al primo adulto nel nostro piccolo archivio di dati. Lo facciamo utilizzando l'API Stream. Quindi otteniamo due mappe separate, che passiamo ai metodi che mostrano gli annunci. Ci sono molti, molti modi in cui avremmo potuto portare a termine questo compito. L'arsenale di metodi della classe TreeMap ci consente di creare soluzioni personalizzate per ogni esigenza. Non è necessario ricordarli tutti, perché puoi sempre utilizzare la documentazione o i suggerimenti del tuo IDE. Per rafforzare ciò che hai imparato, ti suggeriamo di guardare una lezione video dal nostro corso Java È tutto per ora! Spero che la classe TreeMap ti sia chiara ora e che la applicherai correttamente per risolvere compiti pratici di codifica.