Caratteristiche di TreeMap in Java

Se stai leggendo questo articolo, è probabile che tu abbia familiarità con l' interfaccia della mappa e i suoi utilizzi. In caso contrario, ecco qua. Oggi parleremo delle funzionalità di implementazione di TreeMap e, più specificamente, di come differisce da HashMap e di come utilizzarlo correttamente.

Confronto tra TreeMap, HashMap e LinkedHashMap

L'implementazione più comunemente utilizzata dell'interfaccia Map è HashMap . È facile da usare e garantisce un rapido accesso ai dati, rendendolo il miglior candidato per la maggior parte delle attività. La maggior parte, ma non tutti. A volte è necessario archiviare i dati in una forma strutturata con la possibilità di navigarvi. In questo caso, un'altra implementazione dell'interfaccia Map viene in soccorso : TreeMap . TreeMap implementa l' interfaccia NavigableMap , che eredita da SortedMap , che a sua volta eredita dall'interfaccia Map . Implementando le interfacce NavigableMap e SortedMap , TreeMap ottiene funzionalità aggiuntive che HashMap non ha , ma questo ha un prezzo in termini di prestazioni. Esiste anche una classe LinkedHashMap , che consente anche di memorizzare i dati in un determinato ordine, nell'ordine in cui sono stati aggiunti. Per aiutarti a comprendere le differenze tra queste tre classi, guarda questa tabella: Come puoi vedere, queste classi hanno molto in comune, ma ci sono anche alcune differenze. Sebbene la classe TreeMapsia la più multifunzionale, non sempre può essere memorizzata nullcome chiave. Inoltre, il tempo di accesso agli elementi TreeMap sarà il più lungo. Pertanto, se non è necessario archiviare i dati in forma ordinata, è meglio utilizzare HashMapo LinkedHashMap.

Albero di ebano rosso

Come probabilmente avrai notato, sotto il cofano TreeMaputilizza una struttura dati chiamata albero rosso-nero. È l'archiviazione dei dati in questa struttura che garantisce l'ordine in cui i dati vengono archiviati. Cos'è quest'albero? Scopriamolo! Immagina di dover memorizzare coppie numero-stringa. I numeri 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 saranno le chiavi. Se memorizzi i dati in un elenco tradizionale e devi trovare un elemento con la chiave 101, dovrai scorrere tutti i 13 elementi per trovarlo. Per 13 elementi questo non è critico; lavorando con un milione avremo grossi problemi. Per risolvere tali problemi, i programmatori utilizzano strutture dati leggermente più complesse. Pertanto, incontra l'albero rosso-nero!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

La ricerca dell'elemento richiesto inizia dalla radice dell'albero, nel nostro caso è 61. Successivamente viene effettuato un confronto con il valore richiesto. Se il nostro valore è inferiore andiamo a sinistra, se è maggiore andiamo a destra. Ciò accade finché non troviamo il valore richiesto o raggiungiamo un elemento con un valore null(una foglia di un albero). I colori rosso e nero vengono utilizzati per rendere l'albero più facile da navigare e bilanciare. Ci sono delle regole che devono essere sempre seguite quando si costruisce un albero rosso-nero:

• La radice dovrebbe essere colorata di nero.
• Le foglie dell'albero dovrebbero essere nere.
• Un nodo rosso deve avere due nodi figli neri.
• Un nodo nero può avere qualsiasi nodo figlio.
• Il percorso da un nodo alle sue foglie deve contenere lo stesso numero di nodi neri.
• Nuovi nodi vengono aggiunti al posto delle foglie.

Se guardi insieme le regole 3, 4 e 5, puoi capire come colorare i nodi accelera la navigazione attraverso l'albero: il percorso attraverso i nodi neri è sempre più breve che attraverso quelli rossi. Pertanto, la dimensione totale dell'albero è determinata dal numero di nodi neri e questa dimensione è chiamata “altezza nera”. L'albero rosso-nero è implementato in diversi linguaggi di programmazione. Esistono molte implementazioni per Java su Internet, quindi non ci soffermeremo a lungo, ma continueremo a familiarizzare con le funzionalità TreeMap.

Metodi derivati ​​dalle interfacce SortedMap e NavigableMap

Ad esempio HashMap, TreeMapimplementa l'interfaccia Map, il che significa che TreeMapha tutti i metodi che HashMap. Inoltre, TreeMapimplementa interfacce SortedMape NavigableMap, ottenendo da esse funzionalità aggiuntive. SortedMap— un'interfaccia che estende Mape aggiunge metodi rilevanti per un set di dati ordinato:

• firstKey(): restituisce la chiave del primo elemento della mappa;
• lastKey(): restituisce la chiave dell'ultimo elemento;
• headMap(K end): restituisce una mappa che contiene tutti gli elementi di quella corrente, dall'inizio fino all'elemento con la chiave end;
• tailMap(K start): restituisce una mappa che contiene tutti gli elementi di quella corrente, iniziando dall'elemento starte finendo con la fine;
• subMap(K start, K end): restituisce una mappa che contiene tutti gli elementi di quella corrente, iniziando dall'elemento starte terminando con l'elemento con la chiave end.

NavigableMap— un'interfaccia che estende SortedMape aggiunge metodi per la navigazione tra gli elementi della mappa:

• firstEntry(): restituisce la prima coppia chiave-valore;
• lastEntry(): restituisce l'ultima coppia chiave-valore;
• pollFirstEntry(): restituisce e rimuove la prima coppia;
• pollLastEntry(): restituisce e rimuove 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 che è inferiore o uguale alla chiave obj. Se non esiste tale chiave, restituisce null;
• lowerKey(K obj): Restituisce la chiave più grande k che è più piccola della chiave obj. Se non esiste tale chiave, restituisce null;
• higherKey(K obj): Restituisce la chiave più piccola k che è maggiore della chiave obj. Se non esiste tale chiave, restituisce null;
• ceilingEntry(K obj): simile al metodo ceilingKey(K obj), ma restituisce una coppia chiave-valore (o null);
• floorEntry(K obj): simile al metodo floorKey(K obj), ma restituisce una coppia chiave-valore (o null);
• lowerEntry(K obj): simile al metodo lowerKey(K obj), ma restituisce una coppia chiave-valore (o null);
• higherEntry(K obj): simile al metodo upperKey(K obj), ma restituisce una coppia chiave-valore (o null);
• descendingKeySet(): restituisce un NavigableSet contenente tutte le chiavi ordinate in ordine inverso;
• descendingMap(): restituisce una Mappa Navigabile contenente tutte le coppie ordinate in ordine inverso;
• navigableKeySet(): restituisce un oggetto NavigableSet contenente tutte le chiavi in ​​ordine di archiviazione;
• headMap(K upperBound, boolean incl): restituisce una mappa che contiene coppie dall'inizio all'elemento upperBound. L'argomento incl specifica se l'elemento upperBound deve essere incluso nella mappa restituita;
• tailMap(K lowerBound, boolean incl): la funzionalità è simile al metodo precedente, vengono restituite solo le coppie da lowerBound alla fine;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Come nei metodi precedenti, vengono restituite coppie da lowerBound a upperBound, gli argomenti lowIncl e highIncl specificano se includere gli elementi di confine nella nuova mappa.

Nell'implementazione stessa TreeMap, oltre ai costruttori a noi familiari, ne viene aggiunto un altro, che accetta un'istanza del comparatore. Questo comparatore sarà responsabile dell'ordine in cui gli elementi vengono memorizzati.

Esempi di utilizzo di TreeMap

Una tale abbondanza di metodi aggiuntivi può sembrare inutile, ma molto spesso si rivelano molto più utili di quanto sembrasse inizialmente. Guardiamo questo esempio con te. Immagina di lavorare nel reparto marketing di una grande azienda e di avere un database di persone a cui vogliamo mostrare pubblicità. Ci sono due sfumature in questo:

• dobbiamo tenere traccia del numero di impressioni ricevute da ciascuna persona;
• L'algoritmo per mostrare la pubblicità ai minorenni è diverso.

Creiamo una classe Personche memorizzerà tutte le informazioni a nostra disposizione su una 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("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 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 Mainche creiamo TreeMap, dove keysi trova una persona specifica ed valueè il numero di impressioni dell'annuncio questo mese. Nel costruttore passiamo un comparatore che ordinerà le persone per età. Riempi con mapvalori casuali. Ora dobbiamo ottenere un riferimento al primo adulto nel nostro mini archivio dati. Lo facciamo utilizzando l'API Stream. Successivamente otteniamo due mappe indipendenti, che passiamo ai metodi di visualizzazione della pubblicità. Ci sono molti, molti modi in cui questo problema potrebbe essere risolto. L'arsenale di metodi della classe TreeMapti consente di inventare soluzioni per tutti i gusti. Non è necessario ricordarli tutti, perché è sempre possibile utilizzare la documentazione o i suggerimenti provenienti dall'ambiente di sviluppo. È tutto! Spero che ora la lezione TreeMapti sia chiara e che ne troverai un'applicazione precisa nella risoluzione di problemi pratici.