19
Basta chiedersi quali sono i pro e i contro di un TreeSet, se qualcuno potesse dirmi per favore? Grazie!Quali sono i pro e i contro di un TreeSet
A
risposta
23
Una delle classi Collection. Ti consente di accedere agli elementi della tua collezione per chiave, o in sequenza per chiave. Ha un sovraccarico considerevolmente maggiore rispetto a ArrayList o HashMap. Utilizzare HashSet quando non è necessario l'accesso sequenziale, è sufficiente cercare per chiave. Utilizzare un ArrayList e utilizzare matrici. ordina se vuoi solo gli elementi in ordine. TreeSet mantiene gli elementi in ordine in ogni momento. Con ArrayList devi solo ordinare quando è necessario. Con TreeSets, la chiave deve essere incorporata nell'oggetto archiviato nella raccolta. Spesso potresti avere TreeSet of Strings. Tutto quello che puoi fare è dire se una determinata stringa è nel Set. Non ti troverà un oggetto associato come farà un Treemap. Con una TreeMap le chiavi e gli oggetti a cui sono associati sono separate.
TreeSet e suo fratello TreeMap stranamente non hanno nulla a che fare con la rappresentazione degli alberi. Internamente usano un'organizzazione di alberi per darti un Set/Mappa in ordine alfabetico, ma non hai alcun controllo sui collegamenti tra genitori e figli.
Internamente TreeSet utilizza alberi rosso-nero. Non è necessario preselezionare i dati per ottenere un albero ben bilanciato. D'altra parte, se i dati sono ordinati (in ordine ascendente o discendente), non saranno danneggiati come con altri tipi di albero.
Se non si fornisce un comparatore per definire l'ordine desiderato, TreeSet richiede un'implementazione comparabile sulla classe articolo per definire l'ordine naturale.
+4
Caso di utilizzo tipico: Prendi un testo, rilascia tutte le parole da questo testo in un TreeSet
+0
"Usa HashSet quando non hai bisogno di un accesso sequenziale, cerca solo per chiave." - Intendi quando non hai bisogno di ricerca per chiave (che è ciò che fornisce una mappa)? –
+0
Se è necessario un accesso sequenziale specifico ma nessun ordinamento, è possibile utilizzare LinkedHashSet che conserva l'ordine dei dati di input. Anche TreeSet ha rimosso l'ordine di logn mentre PriorityQueue rimuove l'ordine è O (n) –
3
TreeSet:
Pro: ordinato, basato su un algoritmo albero rosso/nero, fornisce la complessità O (log (N)) per le operazioni.
Contro: il valore deve essere comparabile oppure è necessario fornire Comparatore nel costruttore. Inoltre, l'implementazione di HashSet fornisce prestazioni migliori in quanto fornisce la complessità di O (1).
+0
Grazie mille! – Rifk
+0
Sembra strano a "basato su un algoritmo albero rosso/nero" come un "pro". Sembra anche un po 'strano menzionare la complessità di O (log (N)) come un professionista quando la cosa ovvia per confrontare TreeSet è HashSet che (come hai detto) ha una maggiore complessità temporale. –
+1
@Laurence: 1) L'inserimento in una lista è O (N) se si include il controllo dell'unicità, quindi O (log (N)) è un "pro" relativo. 2) un HashSet è solo O (1) se usi una decente funzione di hash e permetti alla tabella hash di crescere. –
0
Suppongo che questa struttura di dati utilizzi l'albero binario per conservare i dati in modo che sia possibile il recupero dell'ordine in ordine ascendente. In tal caso, se tenta di mantenere l'albero in equilibrio, l'operazione di rimozione sarebbe un po 'costosa.
+1
-1: HashSet utilizza un albero rosso-nero. Secondo [questa pagina] (http://www.eli.sdsu.edu/courses/fall95/cs660/notes/RedBlackTree/RedBlack.html) la complessità dell'eliminazione è O (log (N)) –
9
Contro: Una trappola con TreeSet è che implementa l'interfaccia Set in modo inaspettato. Se un TreeSet contiene l'oggetto a, l'oggetto b viene considerato parte del set se a.compareTo (b) restituisce 0, anche se a.equals (b) è falso, quindi se compareTo e uguale non è implementato in un coerente modo, sei in una brutta corsa.
Questo è particolarmente un problema quando un metodo restituisce un Set e non si sa se l'implementazione è un TreeSet o, per esempio, un HashSet.
La lezione da apprendere qui è sempre evitare di implementare compareTo ed eguaglia in modo incoerente. Se è necessario ordinare oggetti in modo non coerente con gli uguali, utilizzare un comparatore.
+1
forse volevi dire "se a.compareTo (b) restituisce zero"? –
+1
Wow. Feedback costruttivo su un post di 4 anni. Grazie, l'ho risolto – Buhb
2
TreeSet frammenti di memoria e ha overhead di memoria aggiuntivi. Puoi guardare le fonti e calcolare la quantità di memoria aggiuntiva e la quantità di oggetti aggiuntivi che crea. Naturalmente dipende dalla natura degli oggetti memorizzati e puoi anche sospettare che io sia paranoico riguardo alla memoria :) ma è meglio non spenderli qua e là - tu hai GC, hai problemi di cache e tutte queste cose sono slooow.
Spesso è possibile utilizzare PriorityQueue anziché TreeSet. E nel tuo tipico caso d'uso è meglio solo ordinare l'array di stringhe.
queste domande e le risposte corrispondenti meritano di essere là fuori. molto utile! grazie! – mtical