Regola empirica per la scelta dell'implementazione di una raccolta Java?

Question

Chiunque ha una buona regola empirica per la scelta tra diverse implementazioni di interfacce di raccolta Java come Elenco, Mappa o Set?

Ad esempio, in generale, perché o in quali casi preferirei utilizzare un vettore o un arraylist, un hashtable o una hashmap?

Answer 1

ho sempre fatto queste decisioni, caso per caso, a seconda del caso d'uso, come ad esempio:

• ho bisogno l'ordinamento di rimanere?
• Avrò chiave/valori Null? DUPS?
• Sarà accessibile da più thread
• Ho bisogno di una coppia chiave/valore
• Avrò bisogno di accesso casuale?

E poi ho rompere il mio comodo 5a edizione Java in a Nutshell e confrontare il ~ 20 o giù di lì opzioni. Ha dei bei tavolini nel capitolo cinque per aiutare a capire cosa è appropriato.

Ok, forse se so a priori che un semplice ArrayList o HashSet farà il trucco non cercherò tutto. ;) ma se c'è qualcosa di remotamente complesso nel mio uso, indubbiamente, scommetti che sono nel libro. A proposito, pensavo che Vector fosse un "vecchio cappello" - non l'ho usato da anni.

Answer 2

Sulla tua prima domanda ...

Elenco, Mappa e Set servono a scopi diversi. Suggerisco di leggere su Java Collections Framework allo http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

essere un po 'più concreto:

• uso lista se avete bisogno di un array-like e avete bisogno di iterare sugli elementi
• uso Mappa se avete bisogno di qualcosa come un dizionario
• usa un Set se hai solo bisogno di decidere se qualcosa appartiene all'insieme o no.

Circa la seconda domanda ...

La differenza principale tra Vector e ArrayList è che il primo è sincronizzato, quest'ultimo non è sincronizzato. Puoi leggere ulteriori informazioni sulla sincronizzazione in Java Concurrency in Practice.

La differenza tra Hashtable (nota che T non è una lettera maiuscola) e HashMap è simile, il primo è sincronizzato, il secondo non è sincronizzato.

Direi che non esiste una regola empirica per preferire un'implementazione o un'altra, dipende davvero dalle tue esigenze.

Answer 3

Gli elenchi consentono voci duplicate, mentre i Set consentono solo un'istanza.

Utilizzerò una mappa ogni volta che sarà necessario eseguire una ricerca.

Per le implementazioni specifiche, ci sono variazioni di conservazione dell'ordine di Maps e Set, ma in gran parte si riduce alla velocità. Tenderò ad usare ArrayList per Lists e HashSet ragionevolmente piccoli per set ragionevolmente piccoli, ma ci sono molte implementazioni (incluse quelle che scrivi tu stesso). HashMap è piuttosto comune per Maps. Qualunque cosa sia più che 'ragionevolmente piccola' e devi iniziare a preoccuparti della memoria, in modo che sia più specifico algoritmicamente.

This page ha sacco di immagini animate insieme con il campione di prova di codice LinkedList ArrayList vs. se siete interessati a numeri duri.

EDIT: Spero che i seguenti collegamenti dimostrano come queste cose sono in realtà solo gli elementi in una cassetta degli attrezzi, devi solo pensare a ciò che le vostre esigenze sono: Vedere versioni Commons-collezioni di Map, List e Set.

Answer 4

Immagino che tu sappia la differenza tra un elenco, un set e una mappa dalle risposte precedenti. Perché scegliere tra le loro classi di implementazione è un'altra cosa. Ad esempio:

Elenco:

1. ArrayList è pratica sul recupero, ma lenta sull'inserimento. È buono per un'implementazione che legge molto ma non inserisce/rimuove molto. Mantiene i suoi dati in un unico blocco continuo di memoria, quindi ogni volta che deve espandersi, copia l'intero array.
2. LinkedList è lento nel recupero, ma veloce nell'inserimento. È buono per un'implementazione che inserisce/rimuove molto ma non legge molto. Non mantiene l'intero array in un unico blocco di memoria continuo.

Set:

1. HashSet non garantisce l'ordine di iterazione, e quindi è il più veloce dei set. Ha un sovraccarico elevato ed è più lento di ArrayList, quindi non dovresti usarlo se non per una grande quantità di dati quando la sua velocità di hashing diventa un fattore.
2. TreeSet mantiene i dati ordinati, quindi è più lento di HashSet.

Mappa: Le prestazioni e il comportamento dei HashMap TreeMap e sono parallele al SET implementazioni.

Vector and Hashtable non deve essere utilizzato. Sono implementazioni sincronizzate, prima del rilascio della nuova gerarchia Collection, quindi lente. Se è necessaria la sincronizzazione, utilizzare Collections.synchronizedCollection().

Answer 5

Ho trovato che Bruce Eckel's Thinking in Java è molto utile. Confronta molto bene le diverse collezioni. Ho usato per mantenere un diagramma che ha pubblicato mostrando l'eredità heirachy sul mio cubo come riferimento rapido. Una cosa che ti suggerisco di fare è tenere a mente la sicurezza del thread. Prestazioni di solito significa non thread-safe.

Answer 6

Per i non ordinati, la scelta migliore, più di nove volte su dieci, sarà: ArrayList, HashMap, HashSet.

Vector e Hashtable sono sincronizzati e pertanto potrebbero essere un po 'più lenti. È raro che desideriate implementazioni sincronizzate e, quando fate le loro interfacce, non sono sufficientemente ricche da rendere la sincronizzazione più utile. Nel caso di Map, ConcurrentMap aggiunge operazioni aggiuntive per rendere l'interfaccia utile. ConcurrentHashMap è una buona implementazione di ConcurrentMap.

LinkedList non è quasi mai una buona idea. Anche se stai facendo un sacco di inserimenti e di rimozione, se stai usando un indice per indicare la posizione, allora è necessario iterare attraverso l'elenco per trovare il nodo corretto. ArrayList è quasi sempre più veloce.

Per Mappa e Imposta, le varianti di hash saranno più veloci di albero/ordinate. Gli algortih di hash tendono ad avere prestazioni O (1), mentre gli alberi saranno O (log n).

Answer 7

In teoria ci sono utili Big-Oh compromessi, ma in pratica questi non hanno quasi mai importanza.

Nei benchmark reali, ArrayList prestazioni eccellenti LinkedList anche con elenchi di grandi dimensioni e con operazioni come "un sacco di inserimenti nella parte anteriore". Gli accademici ignorano il fatto che i veri algoritmi hanno fattori costanti che possono sopraffare la curva asintotica. Ad esempio, gli elenchi concatenati richiedono un'assegnazione di oggetti aggiuntiva per ogni nodo, il che significa che è più lento creare un nodo e caratteristiche di accesso alla memoria decisamente peggiori.

La mia regola è:

1. iniziano sempre con ArrayList e HashSet e HashMap (vale a dire non LinkedList o TreeMap).
2. Le dichiarazioni di tipo devono sempre essere un'interfaccia (ad esempio Elenco, Imposta, Mappa), quindi se una revisione di profiler o codice dimostra che è possibile modificare l'implementazione senza rompere nulla.

Answer 8

Mi piace molto questo foglietto da Sergiy Kovalchuk di blog entry:

più dettagliata Alexander Zagniotov's flowchart from his site.

Answer 9

Come suggerito in altre risposte, esistono diversi scenari per utilizzare la raccolta corretta in base al caso d'uso. Sto elencando alcuni punti,

ArrayList:

• La maggior parte dei casi in cui non vi resta che conservare o scorrere un "mucchio di cose" e poi scorrere attraverso di loro. L'iterazione è più veloce in base all'indice.
• Quando si crea un ArrayList, una quantità fissa di memoria allocata a esso e una volta exceeeded, esso copia l'intera matrice

ListaLinkata:

• Esso utilizza doppiamente lista collegata in modo inserimento e l'operazione di cancellazione sarà veloce poiché aggiungerà o rimuoverà solo un nodo.
• Il recupero è lento in quanto dovrà scorrere i nodi.

HashSet:

• Fare altri sì-no le decisioni su un elemento, ad esempio, "l'elemento è una parola di inglese", "è l'elemento nel database?" , "è l'articolo in questa categoria?" ecc.

• Ricordare "quali articoli sono già stati elaborati", ad es. quando si esegue una scansione Web;

HashMap:

• utilizzato nei casi in cui è necessario dire "per una data X, qual è la Y"? È spesso utile per implementare cache o indici in memoria le coppie di valori chiave Ad esempio: Per un determinato ID utente, qual è il loro nome in cache/oggetto utente ?.
• Sempre andare con HashMap per eseguire una ricerca.

Vector e Hashtable sono sincronizzati e pertanto un bit più lento e Se è necessaria la sincronizzazione, utilizzare Collections.synchronizedCollection(). Controllare This per raccolte ordinate. Spero che questo sia successo.