Differenze tra HashSet e TreeSet – Lezione 35 di Java Avanzato

Gli elementi che vengono aggiunti in un TreeSet vengono posizionati sulla base di confronti tra oggetti, in un HashSet in base al loro codice hash. In entrambi i casi una modifica del contenuto degli oggetti senza una successiva riallocazione provoca risultati inattesi.

Lo schema delle principale operazioni, in termini di complessità di tempo sarà:

Classe/Metodo size isEmpty add contains remove
HashSet O(1) O(1) O(1) O(1) O(1)
TreeSet O(1) O(1) O(log n) O(log n) O(log n)

Come si può notare dalla tabella, un TreeSet è potenzialmente sempre più lento rispetto ad un HashSet ed inoltre per costruirlo richiede più operazioni. Questa classe viene utilizzata quando si vogliono sapere direttamente il primo e l’ultimo elemento, o quando si vogliono gli elementi ordinati. Se ordinassimo una lista con il metodo sort avremmo O(n log n), dove n rappresenta gli n inserimenti. Estraendo gli oggetti e convertendoli in un TreeSet avremo O(n log n) ma con il vantaggio che un TreeSet è costantemente ordinamento, quindi eventuali modifiche non danneggiano l’ordine come può accadere per le liste.

Indice Lezione PrecedenteLezione Successiva

Pubblicato in Collezioni, Guide, Java, Programmazione Taggato con: , , , , ,

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *

*