Regola generale per la scelta dell’implementazione di una raccolta Java?

Qualcuno ha una buona regola empirica per scegliere 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?

Ho sempre preso quelle decisioni caso per caso, in base al caso d’uso, come ad esempio:

  • Ho bisogno che l’ordine rimanga?
  • Avrò chiavi / valori Null? DUPS?
  • Sarà accessibile da più thread
  • Ho bisogno di una coppia chiave / valore
  • Avrò bisogno di accesso casuale?

E poi rendo la mia pratica 5th edition Java in poche parole e confronta le circa 20 opzioni. Ha dei bei tavolini nel capitolo cinque per aiutare a capire cosa è appropriato.

Ok, forse se capisco subito che un semplice ArrayList o HashSet farà il trucco non cercherò di dare un’occhiata. 😉 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.

Mi piace molto questo cheat sheet dal blog di Sergiy Kovalchuk:

Cheat Sheet di Java Map / Collection

Più dettagliato è il diagramma di stream di Alexander Zagniotov dal suo sito .

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

Lista :

  1. ArrayList è veloce nel recupero, ma lento nell’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.

Impostato:

  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 di HashMap e TreeMap sono paralleli alle implementazioni dell’insieme.

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

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

In benchmark reali, ArrayList LinkedList anche con elenchi di grandi dimensioni e operazioni come “un sacco di inserimenti in primo piano”. 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. Inizia sempre con ArrayList e HashSet e HashMap (ovvero non LinkedList o TreeMap).
  2. Le dichiarazioni di tipo dovrebbero sempre essere un’interfaccia (ad es. Elenco, Imposta, Mappa), quindi se un profiler o una revisione del codice lo dimostra, puoi cambiare l’implementazione senza rompere nulla.

Sulla tua prima domanda …

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

Per essere un po ‘più concreto:

  • usa List se hai bisogno di una struttura dati di tipo array e devi eseguire un’iterazione sugli elementi
  • usa Map se hai bisogno di qualcosa come un dizionario
  • usa un Set se hai solo bisogno di decidere se qualcosa appartiene all’insieme o no.

Sulla tua seconda domanda …

La principale differenza 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 (si noti che il 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.

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

Vector e Hashtable sono sincronizzati e quindi 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).

Gli elenchi consentono articoli duplicati, mentre i Set consentono solo un’istanza.

Userò una mappa ogni volta che avrò bisogno di effettuare una ricerca.

Per le implementazioni specifiche, ci sono variazioni di conservazione dell’ordine di Maps e Sets, ma in gran parte arriva 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.

Questa pagina ha un sacco di immagini animate insieme al test di codice di esempio LinkedList vs ArrayList se sei interessato a numeri difficili.

EDIT: Spero che i seguenti link dimostrino come queste cose siano davvero solo oggetti in una cassetta degli attrezzi, devi solo pensare a quali sono le tue esigenze: vedi le versioni di Commons, Collections di Map , List e Set .

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

Lista di array:

  • La maggior parte dei casi in cui è necessario archiviare o eseguire iterazioni attraverso un “gruppo di cose” e in seguito scorrere iterate. L’iterazione è più veloce in base all’indice.
  • Ogni volta che si crea un ArrayList, viene assegnata una quantità fissa di memoria e una volta superata, copia l’intero array

Lista collegata:

  • Utilizza l’elenco doppiamente collegato in modo che l’operazione di inserimento e cancellazione sia veloce poiché aggiungerà o rimuoverà un nodo.
  • Il recupero è lento in quanto dovrà scorrere i nodes.

HashSet:

  • Prendere altre decisioni sì-no su un object, ad esempio “l’object è una parola di inglese”, “è l’elemento nel database?” , “è l’articolo in questa categoria?” eccetera.

  • Ricordando “quali oggetti hai già elaborato”, ad es. Quando fai una ricerca per indicizzazione web;

HashMap:

  • Utilizzato nei casi in cui è necessario dire “per una determinata X, qual è la Y”? È spesso utile per implementare cache o indici in memoria, ad esempio coppie di valori chiave Ad esempio: per un dato ID utente, qual è il loro nome in cache / object utente ?.
  • Vai sempre con HashMap per eseguire una ricerca.

Vector e Hashtable sono sincronizzati e quindi un po ‘più lenti e se è necessaria la sincronizzazione, usa Collections.synchronizedCollection (). Controlla questo per le raccolte ordinate. Spero che questo sia successo.

Ho trovato il Pensiero in Java di Bruce Eckel 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.