Hash-Set und Array-Liste Leistungen

Question

Ich habe eine Methode implementiert, die einfach um eine Reihe von CSV-Dateien, die Daten auf einer Reihe von verschiedenen Modulen enthalten. Dies fügt dann den 'Modulnamen' in ein Hash-Set ein. (Code unten gezeigt)

Ich habe ein HashSet verwendet, da es garantiert, dass keine Duplikate anstelle einer ArrayList eingefügt werden, die die contain() Methode verwenden und die Liste durchlaufen müsste, um zu prüfen, ob sie schon da ist.

Ich glaube, die Verwendung des Hash-Sets hat eine bessere Leistung als eine Array-Liste. Bin ich richtig darin, das zu sagen? wenn verwendet

1. Wie die Leistung für jede Datenstruktur arbeiten:

   Auch kann mir jemand erklären?

2. Was ist die Komplexität mit der Groß-O-Notation?

   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

Sie sind völlig verschiedene Klassen, so ist die Frage: welche Art von Verhalten möchten Sie tun?

HashSet stellt sicher, dass es keine Duplikate gibt, gibt Ihnen eine O (1) Methode, aber nicht die Reihenfolge.
ArrayList stellt nicht sicher, dass es keine Duplikate gibt, ist O (n), aber Sie können die Reihenfolge der Einträge steuern.

Answer 2

Ich glaube, die Verwendung des Hash-Sets hat eine bessere Leistung als eine Array-Liste. Habe ich Recht damit?

Mit vielen (was auch immer es heißt) Einträgen, ja. Bei kleinen Datengrößen könnte die rohe lineare Suche jedoch schneller sein als Hashing. Wo genau der Break-Even ist, muss man nur messen. Mein Bauchgefühl ist, dass mit weniger als 10 Elementen das lineare Nachschlagen wahrscheinlich schneller ist; mit mehr als 100 Elementen Hashing ist wahrscheinlich schneller, aber das ist nur mein Gefühl ...

Lookup von einem HashSet ist konstante Zeit, O (1), vorausgesetzt, dass die HashCode-Implementierung der Elemente ist gesund. Das lineare Nachschlagen aus einer Liste ist die lineare Zeit O (n).

Answer 3

My experiment zeigt, dass HashSet ist schneller als ein ArrayList beginnend bei Sammlungen von 3 Elementen einschließlich.

Eine vollständige Tabelle Ergebnisse

| 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

es auf die Nutzung der Datenstruktur abhängt.

Sie speichern die Daten in HashSet, und für Ihren Fall für den Speicher HashSet ist besser als ArrayList (wie Sie nicht doppelte Einträge wollen). Aber das Speichern ist nicht die übliche Absicht.

Es hängt davon ab, wie Sie die gespeicherten Daten lesen und verarbeiten möchten. Wenn Sie einen sequentiellen Zugriff oder einen wahlfreien indexbasierten Zugriff wünschen, dann ist ArrayList besser oder wenn die Bestellung keine Rolle spielt, dann ist HashSet besser.

Wenn die Bestellung wichtig ist, aber Sie viele Änderungen (Ergänzungen und Löschungen) vornehmen möchten, ist die LinkedList besser.

für ein bestimmtes Element Zugriff auf HashSet wird die Zeit Komplexität O (1) haben, und wenn Sie verwendet haben, würden ArrayList es wäre O (N) haben, wie Sie selbst darauf hingewiesen haben Sie iterate durch die Liste haben würde und sehen wenn das Element nicht vorhanden ist.