Su un altro forum ho incominciato a parlare di alcuni comandi di java che si assomigliano e dopo diverse discussioni ho provato a fare un riassunto di tutto quanto ma nessuno si è sentito di confermare. Posso chiedervi di leggere e di correggere eventuali sviste o mie incomprensioni? Vorrei stampare la paginetta ed allegarla al mio manuale.
A presto e grazie
ArrayList
ArrayList è un array dinamico ovvero una struttura dati array che può essere ridimensionata e consente di aggiungere o rimuovere elementi.
ArrayList memorizza i suoi elementi in un semplice array per cui l'accesso e la lettura sono diretti e costano O(1). Se non si deve ridimensionare l’array e quindi riallocare ogni valore l’interazione con gli elementi del vettore è la più rapida possibile. O(1) è infatti una costante e non dipende dalla dimensione “n” del vettore.
PROBLEMA 1: Essendo l'array non infinito, prima o poi bisogna allargarlo e ricopiarci dentro i valori precedenti.
PROBLEMA 2: La cancellazione. Se si cancella il primo elemento di un ArrayList di 100000 elementi, tutti gli elementi devono essere spostati a sinistra di uno.
VANTAGGI: ArrayList tipicamente è quello che si usa di più, proprio per la sua semplicità. Se tutto quello che si deve fare è memorizzare una sequenza di oggetti uno dopo l'altro e accedere a qualunque indice con rapidità (che è quello che serve nel 90% dei casi) l'ArrayList è la soluzione migliore.
LinkedList
LinkedList non usa un array ma ogni elemento è un "nodo" collegato al nodo precedente e a quello successivo.
PROBLEMA: Se si deve inserire un elemento in posizione i devo prima scorrere la struttura dati fino ad i. Costa O(n) e quindi il processo è decisamente lento in quanto la velocità di accesso è funzione della dimensione “n” del vettore. Chiaramente se si deve accedere al primo elemento della lista la differenza tra LinkedList e ArrayList non sussiste.
VANTAGGI: La cancellazione non deve spostare nulla, solo cambiare due puntatori, costa sempre O(n). Il processo non è istantaneo ed è ancora funzione della dimensione del vettore ma è sempre e comunque più veloce del processo di cancellazione di un valore dall’ArrayList quando si richiede il riallocamento. Quindi se devo cancellare l’ultimo elemento di una struttura dati si impiega meno tempo sull’ArrayList che sul LinkedList mentre per il primo vale il viceversa.
HashSet
HashSet sostituisce all’indice del vettore il valore associato a quella precisa chiave trasformandolo prima in codice hash, in questo modo si perde l’indice dell’array (l’ordine con cui si aggiungono elementi non coincide con quello con cui suddetti elementi vengono letti da un iteratore) ovvero si ottiene una collection non ordinabile (QUESTO E’ UN PROBLEMA) ma si ha un accesso più rapido agli elementi di un vettore perché il confronto di codici hash è veloce, ovvero faccio prima a verificare la presenza di un elemento all’interno di un vettore (QUESTO E’ UN VANTAGGIO), è faccio prima ad aggiungere elementi perché HashSet è un array dinamico senza indice e quindi l’inserimento di nuovi valori avviene senza dover scorrere tutto il vettore (QUESTO E’ UN VANTAGGIO). HashSet, per questo motivo, è più veloce di ArrayList ma come quest’ultimo in alcuni casi (riallocamento) è più lento di LinkedList. HashSet è infatti una struttura costruita sopra un array dinamico, per cui, quando la capacità si esaurisce, va ingrandito (è necessaria una nuova allocazione, re-inserimento degli elementi nella nuova hashtable, deallocazione della hashtable vecchia), esattamente come accade per un array dinamico (anzi, l'ingrandimento è un po' più lento perché nel caso del vettore si fa una copia brutale degli elementi, qui bisogna infatti ricalcolare tutti gli hash). HashSet è più veloce di ArrayList solo quando deve aggiungere valori senza riallocare dati in un nuovo array a causa del superamento della dimensione massima del vettore dinamico. Aggiungere un elemento in coda ad un array non è un'operazione costosa - finché c'è spazio - dato che l'accesso a qualunque posizione è estremamente veloce (O(1), ovvero è un'operazione teoricamente a costo costante), e in un array dinamico si tiene sempre l'indice dell'ultimo posto non occupato, in modo appunto da poter aggiungere elementi in coda "a colpo".
(NOTA: Nella terminologia utilizzata a scanso di equivoci chiave = indice.)
LinkedHashSet
LinkedHashSet è simile ad HashSet ma ad ogni entità del vettore (valore + codice hash al posto dell’indice) ha anche una lista che ne permette l’indicizzazione come in un array semplice. PROBLEMA: Se devo inserire un elemento in posizione i devo scorrere fino ad i. VANTAGGIO: A differenza di LinkedList impiego meno tempo a cercare valori in un array perché posso confrontare codici hash invece di valori stringa.
Per molti aspetti LinkedHashSet è preferibile rispetto a LinkedList ma se tutto quello che serve è un contenitore ordinato con inserimento efficiente in qualunque punto l' LinkedHashSet è una complicazione inutile, una LinkedList basta e avanza.
TreeSet
Crea una collection i cui elementi sono messi in ordine ascendente. Non funziona come un array dinamico, ovvero non deve mai riallocare vettori, ma come una struttura “ad albero” ovvero come una successione di oggetti agganciabili automaticamente ai precedenti in senso decrescente e continuo senza limiti di dimensioni. Ha la particolarità che quando si aggiungono valori alla collection si impiega molto tempo perché essi devono essere messi in ordine, pertanto è più lento di ArrayList e LinkedList ma è più rapido di LinkedList, HashSet e LinkedHashSet quando si deve andare a catturare un valore in quanto si conosce già l’esatta posizione. La velocità di ricerca di un valore è infatti pari a log(n). A titolo informativo si ricordi che O(1) significa che il tempo di esecuzione è costante qualsiasi sia la lunghezza del dato;
O(n) significa che il massimo tempo di esecuzione dipende linearmente con n.
Al di sotto di O(n) si trovano come ordini di complessità log(n) e log(log(n)).
PriorityQueue
E’ un array dinamico capace di ordinare in automatico gli elementi. E’ più veloce di TreeSet nell’andare a recuperare un valore ma quando si deve ridimensionare l’array dinamico per ottenerne uno più grande con i valori ordinati è ancora più lento di TreeSet.
ArrayDeque
E’ identico a PriorityQueue ma ordina i valori in senso decrescente ma forse un pochetto più veloce del precedente quando deve aggiungere un valore senza necessità di riallocazione in quanto il vettore ha due code libere.
EnumSet
E’ usato specificatamente per gestire chiavi di tipo enum ovvero viene adoperato quando si ha a che fare con le enumerazioni.