java - HashSet vs ArrayList contiene rendimiento

Question

Al procesar grandes cantidades de datos, a menudo me encuentro haciendo lo siguiente:

HashSet<String> set = new HashSet<String> ();
//Adding elements to the set
ArrayList<String> list = new ArrayList<String> (set);

Algo así como "descargar" el contenido del conjunto en la lista. Normalmente hago esto porque los elementos que agrego a menudo contienen duplicados que quiero eliminar, y esto parece una manera fácil de eliminarlos.

Con solo ese objetivo en mente (evitando duplicados) también podría escribir:

ArrayList<String> list = new ArrayList<String> ();
// Processing here
if (! list.contains(element)) list.add(element);
//More processing here

Y, por lo tanto, no es necesario "dumping" el conjunto en la lista. Sin embargo, estaría haciendo un pequeño control antes de insertar cada elemento (que supongo que también lo hace HashSet)

¿Alguna de las dos posibilidades es claramente más eficiente?

Answer 1

El conjunto dará un rendimiento mucho mejor ( O(n) vs O(n^2) para la lista), y eso es normal porque evitar el duplicado es el verdadero propósito de un conjunto.

Contiene para un HashSet es O(1) comparación con O(n) para una lista, por lo tanto, nunca debe usar una lista si a menudo necesita ejecutar contains .

Answer 2

Si no necesita una lista, solo usaría un conjunto y esta es la colección natural para usar si el orden no importa y quiere ignorar los duplicados.

Puede hacer ambas cosas; necesita una Lista sin duplicados.

private Set<String> set = new HashSet<>();
private List<String> list = new ArrayList<>();
public void add(String str) {
if (set.add(str))
list.add(str);
}

De esta forma, la lista solo contendrá valores únicos, se conservará el orden de inserción original y la operación será O (1).

Answer 3

ArrayList usa una matriz para almacenar los datos. ArrayList.contains tendrá una complejidad O (n). Entonces, esencialmente, buscar en conjunto una y otra vez tendrá O(n^2) complejidad.

Mientras que HashSet usa un mecanismo de hash para almacenar los elementos en sus respectivos cubos. La operación de HashSet será más rápida para una larga lista de valores. Alcanzará el elemento en O(1) .