¿Cómo funcionan los HashSets en Java?

Duplicar posible:
How does Java hashmap work?¿Cómo funcionan los HashSets en Java?

Puede alguien explicar a mí cómo HashSets en el trabajo de Java y por qué son más rápido que usar ArrayLists?

2012-02-02 madCode

Si es más rápido depende completamente de para qué lo usa. Un HashMap nunca podrá buscar cosas por índice más rápido que un ArrayList , por ejemplo. Es la manipulación de la colección que * puede ser * más rápida, pero incluso eso depende de cómo se agreguen cosas. – cHao

Busque un buen libro sobre estructuras de datos y algoritmos, como * Introducción a Algoritmos *, y lea sobre tablas hash. –

http://docs.oracle.com/javase/tutorial/collections/ – JSager

En primer lugar, HashSet, a diferencia de ArrayList es un Set: No puede contener duplicados mientras ArrayList puede - por lo que se construyen para diferentes propósitos. Tampoco garantiza el orden, nuevamente, a diferencia de una lista.

En segundo lugar, un HashSet se basa en la estructura de datos hash table, que permite O(1) buscar tiempo para un elemento.

Tenga en cuenta que muchas veces, una HashSet es lento a continuación, un ArrayList - si quieres iterate sobre los elementos, por ejemplo - por lo general lo hace en un ArrayList será más rápido que en un HashSet [debido al mal rendimiento de la caché de hachís, entre otras razones]

Fuente

2012-02-02 20:56:32 amit

A HashSet es en realidad un HashMap donde el valor siempre es el mismo.

La forma en que trabaja HashMap se describe en muchos lugares (también se la conoce como "hashtable"). En resumen: genera hashes de claves (objetos) y los posiciona en una tabla. Luego, cada vez que busca una clave, se calcula su hash y se hace referencia directamente al depósito de la tabla. Esto significa que tiene una sola operación (el mejor de los casos) para acceder al mapa.

El HashSet simplemente contiene las claves, por lo que .contains(..) es O(1). Eso y remove(..) son las únicas operaciones que HashSet es más rápido que ArrayList (que es O (n)). La iteración es la misma, la adición es la misma.

Fuente

2012-02-02 20:56:03 Bozho

Solo para agregar a la respuesta descriptiva, la iteración debe ser O (n) y la adición debe ser de O (1) complejidad de tiempo, al igual que un HashMap. Un buen concepto para verificar es rehacer hash donde se almacenan más datos en la estructura de datos (verificados con factor de carga) y, por lo tanto, se debe crear una tabla más grande para el mismo, lo que resulta en un aumento del tiempo promedio de inserción. –

Como cuestión de hecho, por ejemplo iterando sobre y anexas a un ArrayList es más rápido.

Y diablos, ni siquiera puede ordenar a HashSet.

Pero el más rápido de todos es el NoOp. No hay nada tan remotamente tan rápido como el NoOp. De acuerdo, no hace mucho, el NoOp. ¡Pero es realmente rápido en eso!

Debe ser más preciso en lo que considera que es "más rápido que".

Fuente

2012-02-02 21:01:59

Estas son 2 estructuras de datos diferentes.

El concepto detrás de HashSet es la comprobación de teclas.
I.e. Utiliza una transformación de la clave de entrada para obtener un índice de la ubicación del valor en una matriz.
Esto es una operación constante O(1) ya que una matriz permite el acceso aleatorio.

El arraylist es también operación de acceso O(1) ya que también está respaldado por una matriz. Pero solo para acceso aleatorio e inserción.

El búsqueda aunque es O(N) operación de un ArrayList ya que hay que buscar a través de todos los elemements en la lista para llegar al valor de la diferencia de HashSet donde se acaba de transformar la llave y acceder a la matriz. Busque en un HashSet es O(1)

Fuente

2012-02-02 21:03:45 Cratylus

¿Cómo funcionan los HashSets en Java?

Respuesta

Cuestiones relacionadas