¿Estructura de datos más rápida para contains() en Java?

¿Cuál es la estructura de datos en Java que tiene la operación más rápida para contains()?¿Estructura de datos más rápida para contains() en Java?

p. Ej. tengo un conjunto de números {1, 7, 12, 14, 20 ...}

Dado otro número arbitrario x, ¿cuál es la manera más rápida (en promedio) para generar el valor booleano de si x está contenido en el establecer o no? La probabilidad de! Contiene() es aproximadamente 5 veces mayor.

¿Todas las estructuras del mapa proporcionan o (1) operación? ¿Es HashSet la forma más rápida de hacerlo?

Fuente

2010-07-16 codechobo

102

vistazo a las implementaciones basadas en conjunto (Hashset, enumset) y hash (HashMap, linkedhash ..., idnetityhash ..). tienen O (1) para contiene()

This cheatsheet es de gran ayuda.

Fuente

2010-07-16 17:57:43

Por lo que vale la pena, los mapas hash en general no son O (1) en la búsqueda cuando se producen colisiones hash (y pueden suceder muy a menudo, si muy pocos). El peor caso es O (n) en la búsqueda. – Blindy

Estoy de acuerdo con Blindy. El rendimiento de la recolección basada en hash está limitado por el rendimiento de la función hash. – sbidwai

Cuando fui recientemente, el sitio estaba caído. Si esto le sucede, puede utilizar este [enlace] (http://web.archive.org/web/20120105103844/http://www.coderfriendly.com/wp-content/uploads/2009/05/java_collections_v2. pdf) – EasilyBaffled

-2

hash (conjunto de hash) es el mejor con O (1)

Fuente

2010-07-16 18:07:10 Satish

Hay 8 minutos entre su respuesta y la de Pangea. El suyo no agrega ningún valor adicional, entonces, ¿por qué publicarlo? –

@bart conexión de internet lenta real – Will

@ Will, quizás. Si es así, entonces @Satish ya tuvo tiempo suficiente para eliminar su respuesta redundante. Sin embargo, él/ella elige dejarlo colgando. Tal vez con la esperanza de la recopilación de algunos puntos? Tal vez esa era la intención, ¿quién sabe? –

para su caso particular de números con una densidad relativamente alta que haría uso de un BitSet, que será más rápido y mucho más pequeño que un hash conjunto.

Fuente

2010-07-16 22:15:20 starblue

La única estructura de datos más rápida que HashSet es TIntHashSet de Trove4J. Utiliza primitivas que evitan la necesidad de utilizar objetos enteros.

Si el número de enteros es pequeño, puede crear un booleano [] donde cada valor presente se convierte en "verdadero". Este será O (1). Nota: HashSet no se garantiza que sea O (1) y es más probable que sea O (log (log (N))).

Solo obtendrá O (1) para una distribución de hash ideal. Sin embargo, es más probable que obtenga colisiones de segmentos compartidos y algunas búsquedas deberán verificar más de un valor.

Fuente

2010-07-17 07:23:45

¿Estructura de datos más rápida para contains() en Java?

Respuesta

Cuestiones relacionadas