Hash Set y Array List performances

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 usado un hashSet ya que garantiza que no se inserten duplicados en lugar de un ArrayList que debería usar el método contain () e iterar a través de la lista para verificar si ya está allí.

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

Además, puede alguien explicarme:

  1. ¿Cómo se trabaja el rendimiento para cada estructura de datos si se usa?
  2. ¿Cuál es la complejidad usando la notación de O grande?

    HashSet modulesUploaded = new HashSet(); 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; 

    }

Mi experimento muestra que HashSet es más rápido que ArrayList comienza 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 

Son clases completamente diferentes, entonces la pregunta es: ¿qué tipo de comportamiento quieres?

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

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

Con muchas (lo que quiera decir) 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 de hashing 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 de los elementos hashCode sea correcta. La búsqueda lineal de una lista es tiempo lineal, O (n).

Depende del uso de la estructura de datos.

Está almacenando los datos en HashSet , y para su caso de almacenamiento, HashSet es mejor que ArrayList (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 ArrayList es mejor o si el orden no importa, entonces HashSet es mejor.

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

Para acceder a un elemento en particular, HashSet tendrá una complejidad de tiempo como O (1) y si hubiera utilizado ArrayList , habría sido O (N), como usted mismo señaló, tendría que iterate en la lista y ver si el elemento está no presente.