Funciones del conjunto hash y lista de arreglos

Question

Implementé un método que simplemente gira alrededor de un conjunto de archivos CSV que contienen datos en un número de módulos diferentes. Esto luego agrega el 'moduleName' en un hashSet. (Código que se muestra a continuación)

He utilizado un hashSet, ya que garantiza que no se inserten duplicados en lugar de un ArrayList que tendría que usar el método contain() e iterar por la lista para comprobar si ya está allí.

Creo que el uso del conjunto hash tiene un mejor rendimiento que una lista de matriz. ¿Estoy en lo correcto al afirmar eso?

Además, alguien puede explicar a mí:

1. Cómo funciona el rendimiento para cada estructura de datos si se utiliza?

2. ¿Cuál es la complejidad con la notación de 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

Son completamente diferentes clases, así que la pregunta es: ¿qué tipo de comportamiento es lo que quieres?

HashSet asegura que no hay duplicados, le da un método O (1) pero no conserva el orden.
ArrayList no garantiza que no haya duplicados, es O (n) pero puede controlar el orden de las entradas.

Answer 2

Creo que el uso del conjunto de hash tiene un mejor rendimiento que una lista de matriz. ¿Estoy en lo correcto al decir eso?

Con muchas (lo que quiera que sea) entradas, sí. Sin embargo, con pequeños tamaños de datos, la búsqueda lineal sin procesar podría ser más rápida que el hash. Donde exactamente está el punto de equilibrio, solo tienes que medir. Mi intuición es que con menos de 10 elementos, la búsqueda lineal es probablemente más rápida; con más de 100 elementos hash es probablemente más rápido, pero esa es solo mi sensación ...

La búsqueda desde un HashSet es un tiempo constante, O (1), siempre que la implementación hashCode de los elementos sea correcta. La búsqueda lineal de una lista es tiempo lineal, O (n).

Answer 3

My experiment muestra que HashSet es más rápido que ArrayList comenzando en colecciones de 3 elementos inclusive.

una tabla de resultados 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

Depende del uso de la estructura de datos.

Está almacenando los datos en HashSet, y para su caso de almacenamiento HashSet es mejor que (ya que no desea entradas duplicadas). Pero solo almacenar no es la intención habitual.

Depende de cómo desee leer y procesar los datos almacenados. Si desea acceso secuencial o acceso basado en un índice aleatorio, entonces es mejor ArrayList o si el orden no importa, entonces HashSet es mejor.

Si el pedido es importante pero desea hacer muchas modificaciones (adiciones y eliminaciones), LinkedList es mejor.

Para acceder a un elemento particular HashSet tendrá complejidad del tiempo como O (1) y si que habría utilizado ArrayList habría sido O (N), como usted mismo ha señalado que tendría que iterate por la lista y ver si el elemento no está presente