¿Cuánto cuesta la iteración en un HashSet también depende de la capacidad del mapa de respaldo?

De los JavaDocs de HashSet:¿Cuánto cuesta la iteración en un HashSet también depende de la capacidad del mapa de respaldo?

Esta clase ofrece un rendimiento constante de tiempo para las operaciones básicas (añadir, eliminar, contiene y tamaño), asumiendo la función de dispersión dispersa los elementos correctamente entre los cubos. La iteración sobre este conjunto requiere un tiempo proporcional a la suma del tamaño de la instancia HashSet (el número de elementos) más la "capacidad" de la instancia Backing HashMap (el número de segmentos). Por lo tanto, es muy importante no establecer la capacidad inicial demasiado alta (o el factor de carga demasiado baja) si iteración rendimiento es importante

¿Por qué iteración toma tiempo proporcional a la suma (número de elementos en el conjunto + Capacidad del mapa de respaldo) y no solo a la cantidad de elementos en el conjunto mismo?

Fuente

2012-08-22 Geek

¿Cómo le iterar sobre todos los elementos sin también iterar sobre todos los cubos vacíos? – sepp2k

Relacionados: http://stackoverflow.com/a/11903357/829571 – assylias

También puede [verifique el código] (http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/ 7-b147/java/util/HashSet.java? Av = f # 168) y profundiza para ver qué sucede debajo del capó. – assylias

HashSet se implementa utilizando un HashMap donde los elementos son las teclas del mapa. Como un mapa tiene un número definido de depósitos que pueden contener uno o más elementos, la iteración debe verificar cada segmento, ya sea que contenga elementos o no.

Fuente

2012-08-22 09:20:17 Thomas

¿Cuáles son los valores de ese hashmap? – Geek

@Geek dado que los valores no importan son solo objetos ficticios (o más precisamente, es un objeto ficticio: 'private static final Object PRESENT = new Object();'). – Thomas

El uso de LinkedHashSet sigue la lista de entradas "vinculadas" por lo que el número de espacios en blanco no importa. Normalmente no tendrías un HashSet donde la capacidad es mucho más que el doble del tamaño realmente utilizado. Incluso si lo hace, el escaneo de un millón de entradas, sobre todo null No se necesita mucho tiempo (milisegundos)

Fuente

2012-08-22 09:22:30

2 ms por cada 1 millón de nulos en mi máquina ;-) – assylias

@assylias Suena bien. Iterar sobre un HashSet no va a ser bonito sin importar lo que hagas.Realmente quieres hacer una búsqueda o una colección ordenada en la que solo estás trabajando en algunas entradas si quieres velocidad. –

¿Por qué iteración toma tiempo proporcional a la suma (número de elementos en conjunto + Capacidad de correlación de respaldo) y no solo al número de elementos en el conjunto mismo?

Los elementos están dispersos dentro del subyacente HashMap que está respaldado por una matriz.
Así que no se sabe qué cubetas están ocupadas (pero se sabe cuántos elementos están totalmente disponibles).
Así que para iterar sobre todos los elementos todos cubos deben comprobarse

Fuente

2012-08-22 09:25:45 Cratylus

Si su preocupación es el tiempo que tarda en recorrer todo el conjunto, y está utilizando Java 6 o superior echar un vistazo a esta belleza:

ConcurrentSkipListSet

Fuente

2012-08-22 09:59:07 theINtoy

¿Cuánto cuesta la iteración en un HashSet también depende de la capacidad del mapa de respaldo?

Respuesta

Cuestiones relacionadas