Definir: ¿Qué es un HashSet?

420

HashSet La estructura de datos C # HashSet se introdujo en .NET Framework 3.5. Puede encontrar una lista completa de los miembros implementados en la página HashSet MSDN .

  1. Donde se usa
  2. ¿Por qué querrías usarlo?
c# hashset 001
fuente
44
en.wikipedia.org/wiki/Set_(computer_science)
Claus Jørgensen
3
posible duplicado de ¿ Cuándo debo usar el tipo HashSet <T>?
nawfal
Utiliza una tabla hash internamente. Si tiene una buena implementación de tabla hash (por ejemplo, Diccionario <T>) puede implementar HashSet usted mismo fácilmente.
Raz Megrelidze

Respuestas:

614

    1. A HashSetcontiene un conjunto de objetos, pero de una manera que le permite determinar fácil y rápidamente si un objeto ya está en el conjunto o no. Lo hace administrando internamente una matriz y almacenando el objeto utilizando un índice que se calcula a partir del código hash del objeto. Mira aquí

    2. HashSetes una colección desordenada que contiene elementos únicos. Tiene las operaciones de recopilación estándar Agregar, Eliminar, Contiene, pero dado que utiliza una implementación basada en hash, estas operaciones son O (1). (A diferencia de List, por ejemplo, que es O (n) para Contiene y Eliminar.) HashSetTambién proporciona operaciones de conjuntos estándar como unión , intersección y diferencia simétrica . Mira aquí

  2. Hay diferentes implementaciones de conjuntos. Algunos hacen que las operaciones de inserción y búsqueda sean súper rápidas mediante elementos hash. Sin embargo, eso significa que se pierde el orden en que se agregaron los elementos. Otras implementaciones preservan el orden agregado a costa de tiempos de ejecución más lentos.

La HashSetclase en C # va para el primer enfoque, por lo tanto no conserva el orden de los elementos. Es mucho más rápido que un regular List. Algunos puntos de referencia básicos mostraron que HashSet es decentemente más rápido cuando se trata de tipos primarios (int, double, bool, etc.). Es mucho más rápido cuando se trabaja con objetos de clase. Entonces ese punto es que HashSet es rápido.

El único inconveniente HashSetes que no hay acceso por índices. Para acceder a los elementos, puede usar un enumerador o la función incorporada para convertirlo HashSeten Listay iterar a través de eso. Mira aquí

kamaci
fuente
13
Dos cosas, hashset y similares son .NET, no C #. También HashSet no conserva el orden. Intente agregar y eliminar elementos de un conjunto de hash, sabrá si itera más tarde ..
nawfal
13

A HashSettiene una estructura interna (hash), donde los elementos se pueden buscar e identificar rápidamente. La desventaja es que iterar a través de HashSet(u obtener un elemento por índice) es bastante lento.

Entonces, ¿por qué alguien querría saber si ya existe una entrada en un conjunto?

Una situación en la que a HashSetes útil es obtener valores distintos de una lista donde pueden existir duplicados. Una vez que se agrega un elemento HashSet, es rápido determinar si existe ( Containsoperador).

Otras ventajas de la HashSetson las operaciones Set: IntersectWith, IsSubsetOf, IsSupersetOf, Overlaps, SymmetricExceptWith, UnionWith.

Si está familiarizado con el lenguaje de restricción de objetos , identificará estas operaciones de conjunto. También verá que está un paso más cerca de una implementación de UML ejecutable.

k rey
fuente
20
Re: desventaja. No, iterar a través de un HashSet es perfectamente rápido. En segundo lugar, no es posible obtener un artículo por índice. De hecho, los elementos se almacenan sin ordenar.
Nigel Touch
@Nigel Touch. La iteración es rápida si no le importa el índice (orden en que se agregaron). Sin embargo, si le preocupa el índice, el índice debe almacenarse con cada clave hash y, por lo tanto, puede ser bastante lento porque la lista debe buscarse exhaustivamente para recuperar el elemento correcto. Este comportamiento es muy diferente a una lista en la que los elementos se indexan por el orden en que se agregan.
k rey
Tiene sentido por qué sería rápido, porque no hay dos hash iguales. Permitir que la consulta aproveche un enfoque de "cortocircuito", descartando rápidamente ciertos criterios.
Chef_Code
8

Simplemente dicho y sin revelar los secretos de la cocina: un conjunto en general, es una colección que no contiene elementos duplicados, y cuyos elementos no están en ningún orden en particular. Entonces, A HashSet<T>es similar a un genérico List<T>, pero está optimizado para búsquedas rápidas (a través de tablas hash, como su nombre lo indica) a costa de perder el orden.

Apilado
fuente
1
Pero, ¿puede un HashSet <T> almacenar dos objetos que tienen los mismos datos, como dos clases de Producto que tienen las mismas propiedades con el mismo contenido?
Johan Herstad
Supongo que nunca lo sabremos
Denny
@JohanHerstad Asumiendo que EqualityComparer para su clase se preocupa por esas propiedades o construye el HashSet con un IEqualityComparer que se preocupa por esas propiedades, no veo por qué no lo haría. La documentación de HashSet deja en claro que se basa en uno u otro para determinar la unicidad.
Bacon Bits
2

Desde la perspectiva de la aplicación, si uno solo necesita evitar duplicados, entonces HashSetes lo que está buscando, ya que las complejidades de Buscar, Insertar y Eliminar son O (1): constante . Lo que esto significa es que no importa cuántos elementos HashSettenga, llevará la misma cantidad de tiempo verificar si existe ese elemento o no, además, dado que también está insertando elementos en O (1), lo hace perfecto para este tipo de cosas.

Matas Vaitkevicius
fuente