Confronto tra HashSet e TreeSet

1. Introduzione

In questo articolo, confronteremo due delle implementazioni Java più popolari dell'interfaccia java.util.Set : HashSet e TreeSet .

2. Differenze

HashSet e TreeSet sono foglie dello stesso ramo, ma differiscono in pochi aspetti importanti.

2.1. Ordinazione

HashSet memorizza gli oggetti in ordine casuale, mentre TreeSet applica l'ordine naturale degli elementi. Vediamo il seguente esempio:

@Test public void givenTreeSet_whenRetrievesObjects_thenNaturalOrder() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add("Awesome"); assertEquals(3, set.size()); assertTrue(set.iterator().next().equals("Awesome")); }

Dopo aver aggiunto gli oggetti String in TreeSet , vediamo che il primo è "Awesome", anche se è stato aggiunto proprio alla fine. Un'operazione simile eseguita con HashSet non garantisce che l'ordine degli elementi rimarrà costante nel tempo.

2.2. Oggetti nulli

Un'altra differenza è che HashSet può memorizzare oggetti nulli , mentre TreeSet non li consente :

@Test(expected = NullPointerException.class) public void givenTreeSet_whenAddNullObject_thenNullPointer() { Set set = new TreeSet(); set.add("Baeldung"); set.add("is"); set.add(null); } @Test public void givenHashSet_whenAddNullObject_thenOK() { Set set = new HashSet(); set.add("Baeldung"); set.add("is"); set.add(null); assertEquals(3, set.size()); }

Se proviamo a memorizzare l' oggetto null in un TreeSet , l'operazione risulterà in una NullPointerException generata . L'unica eccezione era in Java 7 quando era consentito avere esattamente un elemento nullo nel TreeSet .

2.3. Prestazione

In poche parole, HashSet è più veloce del TreeSet .

HashSet fornisce prestazioni a tempo costante per la maggior parte delle operazioni come add () , remove () e contains () , rispetto al tempo di log ( n ) offerto dal TreeSet.

Di solito, possiamo vedere che il tempo di esecuzione per l'aggiunta di elementi in TreeSet è molto migliore rispetto a HashSet .

Ricorda che la JVM potrebbe non essere stata riscaldata, quindi i tempi di esecuzione possono differire. Una buona discussione su come progettare ed eseguire micro test utilizzando varie implementazioni di Set è disponibile qui.

2.4. Metodi implementati

TreeSet è ricco di funzionalità , implementando metodi aggiuntivi come:

  • pollFirst () - per restituire il primo elemento o null se Set è vuoto
  • pollLast () - per recuperare e rimuovere l'ultimo elemento o restituire null se Set è vuoto
  • first () - per restituire il primo elemento
  • last () - per restituire l'ultimo elemento
  • soffitto () - per restituire l'elemento minimo maggiore o uguale all'elemento dato, o null se non esiste tale elemento
  • lower () - per restituire l'elemento più grande strettamente inferiore all'elemento dato, o null se non esiste tale elemento

I metodi sopra menzionati rendono TreeSet molto più facile da usare e più potente di HashSet .

3. Somiglianze

3.1. Elementi unici

Sia TreeSet che HashSet garantiscono una raccolta di elementi priva di duplicati, poiché fa parte dell'interfaccia generica di Set :

@Test public void givenHashSetAndTreeSet_whenAddDuplicates_thenOnlyUnique() { Set set = new HashSet(); set.add("Baeldung"); set.add("Baeldung"); assertTrue(set.size() == 1); Set set2 = new TreeSet(); set2.add("Baeldung"); set2.add("Baeldung"); assertTrue(set2.size() == 1); }

3.2. Non sincronizzato

Nessuna delle implementazioni di Set descritte è sincronizzata . Ciò significa che se più thread accedono a un set contemporaneamente e almeno uno dei thread lo modifica, è necessario sincronizzarlo esternamente.

3.3. Iteratori fail-fast

Gli Iterator restituiti da TreeSet e HashSet sono rapidi.

Ciò significa che qualsiasi modifica del set in qualsiasi momento dopo la creazione dell'iteratore genererà un'eccezione ConcurrentModificationException:

@Test(expected = ConcurrentModificationException.class) public void givenHashSet_whenModifyWhenIterator_thenFailFast() { Set set = new HashSet(); set.add("Baeldung"); Iterator it = set.iterator(); while (it.hasNext()) { set.add("Awesome"); it.next(); } }

4. Quale implementazione utilizzare?

Entrambe le implementazioni soddisfano il contratto dell'idea di un set, quindi dipende dal contesto quale implementazione potremmo usare.

Ecco alcuni punti rapidi da ricordare:

  • Se vogliamo mantenere ordinate le nostre voci, dobbiamo andare per TreeSet
  • Se valutiamo le prestazioni più del consumo di memoria, dovremmo scegliere HashSet
  • Se siamo a corto di memoria, dovremmo scegliere TreeSet
  • Se vogliamo accedere a elementi che sono relativamente vicini tra loro in base al loro ordinamento naturale, potremmo prendere in considerazione TreeSet perché ha una maggiore località
  • Le prestazioni di HashSet possono essere regolate utilizzando initialCapacity e loadFactor , che non è possibile per TreeSet
  • Se vogliamo preservare l'ordine di inserzione e beneficiare di un accesso costante nel tempo, possiamo utilizzare LinkedHashSet

5. conclusione

In questo articolo, abbiamo coperto le differenze e le somiglianze tra TreeSet e HashSet .

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