Java TreeMap vs HashMap

1. Introduzione

In questo articolo, confronteremo due implementazioni di Map : TreeMap e HashMap .

Entrambe le implementazioni formano parte integrante di Java Collections Framework e memorizzano i dati come coppie chiave-valore .

2. Differenze

2.1. Implementazione

Per prima cosa parleremo di HashMap, che è un'implementazione basata su hashtable. Estende la classe AbstractMap e implementa l' interfaccia Map . Un HashMap funziona secondo il principio di hashing .

Questa implementazione di Map di solito agisce come una tabella hash in bucket , ma quando i bucket diventano troppo grandi, vengono trasformati in nodi di TreeNodes , ciascuno strutturato in modo simile a quelli in java.util.TreeMap.

Puoi trovare di più sugli interni di HashMap nell'articolo incentrato su di esso.

D'altra parte, TreeMap estende AbstractMap classe e implementa NavigableMap interfaccia. Una TreeMap negozi Mappa elementi in un rosso-nero albero, che è un auto-bilanciamento Binary Search Albero .

E puoi anche trovare ulteriori informazioni sugli interni di TreeMap nell'articolo incentrato su di esso qui.

2.2. Ordine

HashMap non fornisce alcuna garanzia sul modo in cui gli elementi sono disposti nella mappa .

Significa che non possiamo assumere alcun ordine durante l'iterazione di chiavi e valori di una HashMap :

@Test public void whenInsertObjectsHashMap_thenRandomOrder() { Map hashmap = new HashMap(); hashmap.put(3, "TreeMap"); hashmap.put(2, "vs"); hashmap.put(1, "HashMap"); assertThat(hashmap.keySet(), containsInAnyOrder(1, 2, 3)); }

Tuttavia, gli elementi in una TreeMap vengono ordinati in base al loro ordine naturale .

Se gli oggetti TreeMap non possono essere ordinati in base all'ordine naturale, possiamo utilizzare un Comparatore o un Comparable per definire l'ordine in cui gli elementi sono disposti all'interno della mappa:

@Test public void whenInsertObjectsTreeMap_thenNaturalOrder() { Map treemap = new TreeMap(); treemap.put(3, "TreeMap"); treemap.put(2, "vs"); treemap.put(1, "HashMap"); assertThat(treemap.keySet(), contains(1, 2, 3)); }

2.3. Valori nulli

HashMap consente di memorizzare al massimo una chiave null e molti valori null .

Vediamo un esempio:

@Test public void whenInsertNullInHashMap_thenInsertsNull() { Map hashmap = new HashMap(); hashmap.put(null, null); assertNull(hashmap.get(null)); }

Tuttavia, TreeMap non consente una chiave null ma può contenere molti valori null .

Una chiave nulla non è consentita perché il metodo compareTo () o compare () genera un'eccezione NullPointerException:

@Test(expected = NullPointerException.class) public void whenInsertNullInTreeMap_thenException() { Map treemap = new TreeMap(); treemap.put(null, "NullPointerException"); }

Se stiamo usando una TreeMap con un comparatore definito dall'utente , dipende dall'implementazione del metodo compare () come vengono gestiti i valori nulli .

3. Analisi delle prestazioni

Le prestazioni sono la metrica più critica che ci aiuta a comprendere l'idoneità di una struttura di dati a un caso d'uso.

In questa sezione, forniremo un'analisi completa delle prestazioni per HashMap e TreeMap.

3.1. HashMap

HashMap, essendo un'implementazione basata su hashtable, utilizza internamente una struttura dati basata su array per organizzare i suoi elementi in base alla funzione hash .

HashMap fornisce le prestazioni a tempo costante previste O (1) per la maggior parte delle operazioni come add () , remove () e contains (). Pertanto, è significativamente più veloce di una TreeMap .

Il tempo medio per cercare un elemento sotto l'ipotesi ragionevole, in una tabella hash è O (1). Tuttavia, un'implementazione impropria della funzione hash può portare a una cattiva distribuzione dei valori in bucket che si traduce in:

  • Overhead della memoria: molti bucket rimangono inutilizzati
  • Riduzione delle prestazioni : maggiore è il numero di collisioni, minore è la prestazione

Prima di Java 8, Separate Chaining era l'unico modo preferito per gestire le collisioni. Di solito è implementato utilizzando elenchi collegati, cioè , se c'è una collisione o due elementi diversi hanno lo stesso valore hash, memorizza entrambi gli elementi nello stesso elenco collegato.

Pertanto, la ricerca di un elemento in una HashMap, nel peggiore dei casi, avrebbe potuto richiedere tanto tempo quanto la ricerca di un elemento in un elenco collegato, ad esempio O (n) tempo.

Tuttavia, con l'entrata in scena di JEP 180, c'è stato un sottile cambiamento nell'implementazione del modo in cui gli elementi sono disposti in una HashMap.

Secondo la specifica, quando i bucket diventano troppo grandi e contengono un numero sufficiente di nodi, vengono trasformati in modalità di TreeNodes , ciascuna strutturata in modo simile a quelle di TreeMap .

Quindi, in caso di collisioni di hash elevate, le prestazioni nel caso peggiore miglioreranno da O (n) a O (log n).

Il codice che esegue questa trasformazione è stato illustrato di seguito:

if(binCount >= TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); }

Il valore per TREEIFY_THRESHOLD è otto che denota effettivamente il conteggio della soglia per l'utilizzo di un albero piuttosto che un elenco collegato per un bucket.

È evidente che:

  • Una HashMap richiede molta più memoria di quella necessaria per conservare i suoi dati
  • Una HashMap non dovrebbe essere piena per più del 70% - 75%. Se si avvicina, viene ridimensionato e le voci modificate
  • Il rehashing richiede n operazioni che sono costose in cui il nostro inserimento di tempo costante diventa di ordine O (n)
  • È l'algoritmo di hashing che determina l'ordine di inserimento degli oggetti nella HashMap

The performance of a HashMap can be tuned by setting the custom initial capacity and the load factor, at the time of HashMap object creation itself.

However, we should choose a HashMap if:

  • we know approximately how many items to maintain in our collection
  • we don't want to extract items in a natural order

Under the above circumstances, HashMap is our best choice because it offers constant time insertion, search, and deletion.

3.2. TreeMap

A TreeMap stores its data in a hierarchical tree with the ability to sort the elements with the help of a custom Comparator.

A summary of its performance:

  • TreeMap provides a performance of O(log(n)) for most operations like add(), remove() and contains()
  • A Treemap can save memory (in comparison to HashMap) because it only uses the amount of memory needed to hold its items, unlike a HashMap which uses contiguous region of memory
  • A tree should maintain its balance in order to keep its intended performance, this requires a considerable amount of effort, hence complicates the implementation

We should go for a TreeMap whenever:

  • memory limitations have to be taken into consideration
  • we don't know how many items have to be stored in memory
  • we want to extract objects in a natural order
  • if items will be consistently added and removed
  • we're willing to accept O(log n) search time

4. Similarities

4.1. Unique Elements

Both TreeMap and HashMap don't support duplicate keys. If added, it overrides the previous element (without an error or an exception):

@Test public void givenHashMapAndTreeMap_whenputDuplicates_thenOnlyUnique() { Map treeMap = new HashMap(); treeMap.put(1, "Baeldung"); treeMap.put(1, "Baeldung"); assertTrue(treeMap.size() == 1); Map treeMap2 = new TreeMap(); treeMap2.put(1, "Baeldung"); treeMap2.put(1, "Baeldung"); assertTrue(treeMap2.size() == 1); }

4.2. Concurrent Access

Both Map implementations aren't synchronized and we need to manage concurrent access on our own.

Both must be synchronized externally whenever multiple threads access them concurrently and at least one of the threads modifies them.

We have to explicitly use Collections.synchronizedMap(mapName) to obtain a synchronized view of a provided map.

4.3. Fail-Fast Iterators

The Iterator throws a ConcurrentModificationException if the Map gets modified in any way and at any time once the iterator has been created.

Additionally, we can use the iterator’s remove method to alter the Map during iteration.

Let's see an example:

@Test public void whenModifyMapDuringIteration_thenThrowExecption() { Map hashmap = new HashMap(); hashmap.put(1, "One"); hashmap.put(2, "Two"); Executable executable = () -> hashmap .forEach((key,value) -> hashmap.remove(1)); assertThrows(ConcurrentModificationException.class, executable); }

5. Which Implementation to Use?

In general, both implementations have their respective pros and cons, however, it's about understanding the underlying expectation and requirement which must govern our choice regarding the same.

Summarizing:

  • We should use a TreeMap if we want to keep our entries sorted
  • We should use a HashMap if we prioritize performance over memory consumption
  • Poiché una TreeMap ha una località più significativa, potremmo considerarla se vogliamo accedere a oggetti relativamente vicini tra loro in base al loro ordinamento naturale
  • HashMap può essere regolato utilizzando initialCapacity e loadFactor , che non è possibile per TreeMap
  • Possiamo usare LinkedHashMap se vogliamo preservare l'ordine di inserzione beneficiando di un accesso costante nel tempo

6. Conclusione

In questo articolo, abbiamo mostrato le differenze e le somiglianze tra TreeMap e HashMap .

Come sempre, gli esempi di codice per questo articolo sono disponibili su GitHub.