Prestazioni elenco hash e lista array

Question

Ho implementato un metodo che scorre semplicemente attorno a un set di file CSV che contengono dati su un numero di modulo diverso. Questo aggiunge quindi "moduleName" in un hashSet. (Codice mostrato sotto)

Ho usato un hashSet in quanto garantisce che non vengano inseriti duplicati al posto di un ArrayList che dovrebbe usare il metodo contain() e scorrere l'elenco per verificare se è già presente.

Credo che l'utilizzo del set di hash abbia prestazioni migliori rispetto a un elenco di array. Sono corretto affermando che?

Inoltre, qualcuno può spiegare a me:

1. come lavorare le prestazioni per ogni struttura di dati se utilizzati?

2. Qual è la complessità che utilizza la notazione O grande?

   HashSet<String> modulesUploaded = new HashSet<String>(); 
   
   for (File f: marksheetFiles){ 
       try { 
        csvFileReader = new CSVFileReader(f); 
        csvReader = csvFileReader.readFile(); 
        csvReader.readHeaders(); 
   
        while(csvReader.readRecord()){ 
         String moduleName = csvReader.get("Module"); 
   
         if (!moduleName.isEmpty()){ 
          modulesUploaded.add(moduleName); 
         } 
        } 
   
       } catch (IOException e) { 
        e.printStackTrace(); 
       } 
   
       csvReader.close(); 
   } 
   return modulesUploaded; 
   

   }

Answer 1

Sono classi completamente diverse, quindi la domanda è: che tipo di comportamento vuoi?

HashSet assicura che non vi siano duplicati, fornisce un metodo O (1) ma non conserva l'ordine.
ArrayList non garantisce l'assenza di duplicati, è O (n) ma è possibile controllare l'ordine delle voci.

Answer 2

Credo che l'utilizzo del set di hash abbia prestazioni migliori rispetto a un elenco di array. Sono corretto affermando che?

Con molte voci (qualunque cosa significhi), sì. Con dimensioni di dati ridotte, tuttavia, la ricerca lineare lineare potrebbe essere più veloce dell'hashing. Dove esattamente è il break-even, devi solo misurare. Il mio istinto è che con meno di 10 elementi, la ricerca lineare è probabilmente più veloce; con più di 100 elementi l'hashing è probabilmente più veloce, ma questo è solo il mio sentimento ...

La ricerca da un HashSet è un tempo costante, O (1), a condizione che l'implementazione di hashCode degli elementi sia sensata. La ricerca lineare da una lista è il tempo lineare, O (n).

Answer 3

My experiment indica che HashSet è più veloce di un ArrayList a partire da raccolte di 3 elementi inclusi.

A Risultati tabella completa

| Boost | Collection Size | 
| 2x |  3 elements | 
| 3x |  10 elements | 
| 6x |  50 elements | 
| 12x |  200 elements | <= proportion 532-12 vs 10.000-200 elements 
| 532x | 10.000 elements | <= shows linear lookup growth for the ArrayList 

Answer 4

Dipende l'utilizzo della struttura di dati.

Si stanno memorizzando i dati in HashSet e per il caso per la conservazione HashSet è migliore di ArrayList (poiché non si desidera inserire voci duplicate). Ma solo la memorizzazione non è il solito intento.

Dipende da come si desidera leggere ed elaborare i dati memorizzati. Se si desidera che l'accesso sequenziale o l'accesso in base indice casuale quindi ArrayList è meglio o se l'ordinazione non importa poi HashSet è meglio.

Se l'ordine è importante ma si desidera eseguire molte modifiche (aggiunte e cancellazioni), LinkedList è migliore.

Per l'accesso a un particolare elemento HashSet avrà il tempo complessità O (1) e se si sarebbe usato ArrayList sarebbe stato O (N) come lei stesso ha sottolineato che avrebbe dovuto iterate attraverso la lista e vedere se l'elemento non è presente.