Una guida a TreeMap in Java

1. Panoramica

In questo articolo, esploreremo l' implementazione TreeMap dell'interfaccia Map da Java Collections Framework (JCF).

TreeMap è un'implementazione della mappa che mantiene le sue voci ordinate secondo l'ordine naturale delle sue chiavi o meglio ancora utilizzando un comparatore se fornito dall'utente in fase di costruzione.

In precedenza, abbiamo trattato le implementazioni di HashMap e LinkedHashMap e ci renderemo conto che ci sono un bel po 'di informazioni su come funzionano queste classi che sono simili.

Si consiglia vivamente di leggere gli articoli menzionati prima di procedere con questo.

2. Ordinamento predefinito in TreeMap

Per impostazione predefinita, TreeMap ordina tutte le sue voci in base al loro ordine naturale. Per un numero intero, questo significherebbe ordine crescente e per le stringhe, ordine alfabetico.

Vediamo l'ordinamento naturale in un test:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[1, 2, 3, 4, 5]", map.keySet().toString()); }

Si noti che abbiamo posizionato le chiavi intere in modo non ordinato, ma dopo aver recuperato il set di chiavi, confermiamo che sono effettivamente mantenute in ordine crescente. Questo è l'ordine naturale degli interi.

Allo stesso modo, quando usiamo le stringhe, verranno ordinate nel loro ordine naturale, cioè alfabeticamente:

@Test public void givenTreeMap_whenOrdersEntriesNaturally_thenCorrect2() { TreeMap map = new TreeMap(); map.put("c", "val"); map.put("b", "val"); map.put("a", "val"); map.put("e", "val"); map.put("d", "val"); assertEquals("[a, b, c, d, e]", map.keySet().toString()); }

TreeMap , a differenza di una mappa hash e di una mappa hash collegata, non utilizza il principio di hashing da nessuna parte poiché non utilizza un array per memorizzare le sue voci.

3. Ordinamento personalizzato in TreeMap

Se non siamo soddisfatti dell'ordinamento naturale di TreeMap , possiamo anche definire una nostra regola per l'ordinamento tramite un comparatore durante la costruzione di una mappa ad albero.

Nell'esempio seguente, vogliamo che le chiavi intere siano ordinate in ordine decrescente:

@Test public void givenTreeMap_whenOrdersEntriesByComparator_thenCorrect() { TreeMap map = new TreeMap(Comparator.reverseOrder()); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); assertEquals("[5, 4, 3, 2, 1]", map.keySet().toString()); }

Una mappa hash non garantisce l'ordine delle chiavi memorizzate e specificamente non garantisce che questo ordine rimarrà lo stesso nel tempo, ma una mappa ad albero garantisce che le chiavi saranno sempre ordinate secondo l'ordine specificato.

4. Importanza della TreeMap Sorting

Ora sappiamo che TreeMap memorizza tutte le sue voci in ordine ordinato. A causa di questo attributo delle mappe ad albero, possiamo eseguire query come; trova "più grande", trova "più piccolo", trova tutte le chiavi minori o maggiori di un determinato valore, ecc.

Il codice seguente copre solo una piccola percentuale di questi casi:

@Test public void givenTreeMap_whenPerformsQueries_thenCorrect() { TreeMap map = new TreeMap(); map.put(3, "val"); map.put(2, "val"); map.put(1, "val"); map.put(5, "val"); map.put(4, "val"); Integer highestKey = map.lastKey(); Integer lowestKey = map.firstKey(); Set keysLessThan3 = map.headMap(3).keySet(); Set keysGreaterThanEqTo3 = map.tailMap(3).keySet(); assertEquals(new Integer(5), highestKey); assertEquals(new Integer(1), lowestKey); assertEquals("[1, 2]", keysLessThan3.toString()); assertEquals("[3, 4, 5]", keysGreaterThanEqTo3.toString()); }

5. Implementazione interna di TreeMap

TreeMap implementa NavigableMap interfaccia e basa il suo funzionamento interno sui principi di alberi rosso-neri:

public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, java.io.Serializable

Il principio degli alberi rosso-neri va oltre lo scopo di questo articolo, tuttavia, ci sono cose fondamentali da ricordare per capire come si adattano a TreeMap .

Prima di tutto , un albero rosso-nero è una struttura di dati che consiste di nodi; immagina un albero di mango capovolto con la sua radice nel cielo ei rami che crescono verso il basso. La radice conterrà il primo elemento aggiunto all'albero.

La regola è che partendo dalla radice, qualsiasi elemento nel ramo sinistro di qualsiasi nodo è sempre minore dell'elemento nel nodo stesso. Quelle a destra sono sempre maggiori. Ciò che definisce maggiore o minore di è determinato dall'ordinamento naturale degli elementi o dal comparatore definito alla costruzione come abbiamo visto in precedenza.

Questa regola garantisce che le voci di una mappa ad albero siano sempre ordinate e prevedibili.

In secondo luogo , un albero rosso-nero è un albero di ricerca binario autobilanciato. Questo attributo e quanto sopra garantiscono che le operazioni di base come ricerca, get, put e remove richiedono tempo logaritmico O (log n) .

Essere auto-bilanciati è la chiave qui. Mentre continuiamo a inserire ed eliminare voci, immagina l'albero che si allunga su un bordo o si accorcia sull'altro.

Ciò significherebbe che un'operazione richiederebbe un tempo più breve sul ramo più corto e un tempo più lungo sul ramo più lontano dalla radice, cosa che non vorremmo che accadesse.

Pertanto, questo è curato nella progettazione di alberi rosso-neri. Per ogni inserzione e cancellazione, l'altezza massima dell'albero su ogni bordo è mantenuta a O (log n) cioè l'albero si bilancia continuamente.

Proprio come la mappa hash e la mappa hash collegata, una mappa ad albero non è sincronizzata e quindi le regole per usarla in un ambiente multi-thread sono simili a quelle nelle altre due implementazioni della mappa.

6. Scegliere la mappa giusta

Dopo aver esaminato le implementazioni di HashMap e LinkedHashMap in precedenza e ora TreeMap , è importante fare un breve confronto tra i tre per guidarci su quale si adatta dove.

Una mappa hash è utile come implementazione di una mappa generica che fornisce operazioni rapide di archiviazione e recupero. Tuttavia, è inferiore a causa della sua disposizione caotica e disordinata delle voci.

Ciò fa sì che funzioni male in scenari in cui è presente molta iterazione poiché l'intera capacità della matrice sottostante influisce sull'attraversamento oltre al numero di voci.

Una mappa hash collegata possiede i buoni attributi delle mappe hash e aggiunge ordine alle voci. Funziona meglio dove c'è molta iterazione perché viene preso in considerazione solo il numero di voci indipendentemente dalla capacità.

Una mappa ad albero porta l'ordinamento al livello successivo fornendo il controllo completo su come ordinare le chiavi. D'altro canto, offre prestazioni generali peggiori rispetto alle altre due alternative.

Potremmo dire che una mappa hash collegata riduce il caos nell'ordine di una mappa hash senza incorrere nella penalizzazione delle prestazioni di una mappa ad albero .

7. Conclusione

In questo articolo, abbiamo esplorato la classe Java TreeMap e la sua implementazione interna. Poiché è l'ultima di una serie di implementazioni comuni dell'interfaccia Map, siamo anche andati avanti per discutere brevemente dove si adatta meglio rispetto alle altre due.

Il codice sorgente completo per tutti gli esempi utilizzati in questo articolo può essere trovato nel progetto GitHub.