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 Precedente – Lezione Successiva |
Lascia un commento