¿Cuándo debo usar el tipo HashSet <T>?

134

Estoy explorando el HashSet<T>tipo, pero no entiendo dónde se encuentra en las colecciones.

¿Se puede usar para reemplazar a List<T>? Me imagino que el rendimiento de HashSet<T>a será mejor, pero no pude ver el acceso individual a sus elementos.

¿Es solo para enumeración?

Joan Venge
fuente

Respuestas:

228

Lo importante HashSet<T>es el nombre: es un conjunto . Lo único que puede hacer con un solo conjunto es establecer cuáles son sus miembros y verificar si un elemento es miembro.

Preguntar si puede recuperar un solo elemento (por ejemplo set[45]) es malinterpretar el concepto del conjunto. No existe el elemento número 45 de un conjunto. Los artículos en un conjunto no tienen orden. Los conjuntos {1, 2, 3} y {2, 3, 1} son idénticos en todos los aspectos porque tienen la misma membresía, y la membresía es lo único que importa.

Es algo peligroso iterar sobre un HashSet<T>porque hacerlo impone un orden en los elementos del conjunto. Ese orden no es realmente una propiedad del conjunto. No debes confiar en ello. Si ordenar los artículos de una colección es importante para usted, esa colección no es un conjunto.

Los sets son realmente limitados y con miembros únicos. Por otro lado, son realmente rápidos.

Robert Rossney
fuente
1
El hecho de que el marco proporcione una SortedSetestructura de datos contradice lo que usted dice acerca de que el orden no es propiedad de un conjunto, o señala un malentendido del equipo de desarrollo.
Veverke
10
Creo que es más correcto decir que el orden de los elementos en el HashSetno está definido, así que no confíe en el orden del iterador. Si itera el conjunto porque está haciendo algo contra los elementos del conjunto, eso no es peligroso a menos que esté confiando en algo relacionado con el orden. A SortedSettiene todas las propiedades del orden HashSet más , sin embargo, SortedSetno se deriva de HashSet; reformulado, un SortedSet es una colección ordenada de objetos distintos .
Kit
110

Aquí hay un ejemplo real de dónde uso un HashSet<string>:

Parte de mi resaltador de sintaxis para archivos UnrealScript es una nueva característica que resalta los comentarios de estilo Doxygen . Necesito saber si un comando @o \es válido para determinar si mostrarlo en gris (válido) o rojo (no válido). Tengo uno HashSet<string>de todos los comandos válidos, así que cada vez que toco un @xxxtoken en el lexer, lo uso validCommands.Contains(tokenText)como mi verificación de validez O (1). Realmente no me importa nada, excepto la existencia del comando en el conjunto de comandos válidos. Veamos las alternativas que enfrenté:

  • Dictionary<string, ?>: ¿Qué tipo utilizo para el valor? El valor no tiene sentido ya que solo lo voy a usar ContainsKey. Nota: Antes de .NET 3.0, esta era la única opción para las búsquedas O (1): HashSet<T>se agregó para 3.0 y se extendió para implementar ISet<T>para 4.0.
  • List<string>: Si mantengo la lista ordenada, puedo usar BinarySearch, que es O (log n) (no vi este hecho mencionado anteriormente). Sin embargo, dado que mi lista de comandos válidos es una lista fija que nunca cambia, esto nunca será más apropiado que simplemente ...
  • string[]: De nuevo, Array.BinarySearchda el rendimiento O (log n). Si la lista es corta, esta podría ser la mejor opción de rendimiento. Siempre tiene menos sobrecarga de espacio que HashSet, Dictionaryo List. Incluso con BinarySearch, no es más rápido para conjuntos grandes, pero para conjuntos pequeños valdría la pena experimentar. Sin embargo, el mío tiene varios cientos de artículos, así que pasé esto.
Sam Harwell
fuente
24

A HashSet<T>implementa la ICollection<T>interfaz:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
    // Methods
    void Add(T item);
    void Clear();
    bool Contains(T item);
    void CopyTo(T[] array, int arrayIndex);
    bool Remove(T item);

    // Properties
   int Count { get; }
   bool IsReadOnly { get; }
}

A List<T>implementos IList<T>, que extiende elICollection<T>

public interface IList<T> : ICollection<T>
{
    // Methods
    int IndexOf(T item);
    void Insert(int index, T item);
    void RemoveAt(int index);

    // Properties
    T this[int index] { get; set; }
}

Un HashSet ha establecido una semántica, implementada internamente a través de una tabla hash:

Un conjunto es una colección que no contiene elementos duplicados y cuyos elementos no están en ningún orden en particular.

¿Qué gana el HashSet si pierde el comportamiento del índice / posición / lista?

Agregar y recuperar elementos del HashSet siempre es por el objeto en sí, no a través de un indexador, y cerca de una operación O (1) (La lista es O (1) add, O (1) recupera por índice, O (n) find /eliminar).

El comportamiento de un HashSet podría compararse con el uso Dictionary<TKey,TValue>de a solo agregando / eliminando claves como valores e ignorando los valores del diccionario. Es de esperar que las claves en un diccionario no tengan valores duplicados, y ese es el punto de la parte "Establecer".

Kenan EK
fuente
14

El rendimiento sería una mala razón para elegir HashSet sobre List. En cambio, ¿qué mejor captura tu intención? Si el orden es importante, entonces Set (o HashSet) está fuera. Si se permiten duplicados, del mismo modo. Pero hay muchas circunstancias en las que no nos importa el orden, y preferimos no tener duplicados, y ahí es cuando quieres un Set.

Carl Manaster
fuente
21
Performance would be a bad reason to choose HashSet over List: Simplemente no estoy de acuerdo contigo. Es como decir que elegir un Dictionray en lugar de dos Listas no ayuda en el rendimiento. Eche un vistazo al siguiente artículo
Oscar Mederos
11
@Oscar: No dije que los sets no son más rápidos, dije que sería una mala base para elegirlos. Si está tratando de representar una colección ordenada, un conjunto simplemente no funcionará y sería un error intentar calzarlo; Si la colección que desea no tiene orden, un conjunto es perfecto y rápido. Pero lo importante es la primera pregunta: ¿qué estás tratando de representar?
Carl Manaster
2
Pero piénsalo. Si desea seguir verificando si las cadenas dadas son miembros de una colección de 10,000 cadenas, técnicamente, string[].Containsy HashSet<string>.Containsexpresa su intención igualmente bien; La razón para elegir el HashSet es que se ejecutará mucho más rápido.
Casey
12

HashSet es un conjunto implementado por hashing. Un conjunto es una colección de valores que no contienen elementos duplicados. Los valores en un conjunto también suelen estar desordenados. Entonces, no, un conjunto no se puede usar para reemplazar una lista (a menos que debiera haber usado un conjunto en primer lugar).

Si se pregunta para qué podría ser bueno un conjunto: en cualquier lugar donde desee deshacerse de los duplicados, obviamente. Como un ejemplo levemente inventado, supongamos que tiene una lista de 10.000 revisiones de proyectos de software y desea averiguar cuántas personas contribuyeron a ese proyecto. Puede usar Set<string>ay iterar sobre la lista de revisiones y agregar el autor de cada revisión al conjunto. Una vez que haya terminado de iterar, el tamaño del conjunto es la respuesta que estaba buscando.

conde
fuente
¿Pero Set no permite la recuperación de elementos individuales? ¿Te gusta el set [45]?
Joan Venge
2
Para eso, iterarías sobre los miembros del conjunto. Otras operaciones típicas son verificar si el conjunto contiene un elemento u obtener el tamaño del conjunto.
earl
11

HashSet se usaría para eliminar elementos duplicados en una colección IEnumerable. Por ejemplo,

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

después de ejecutar esos códigos, uniqueStrings contiene {"abc", "ghjr", "yre", "obm", "qwrt", "vyeu"};

Thomas.Benz
fuente
6

Probablemente, el uso más común para los hashsets es ver si contienen un determinado elemento, que está cerca de una operación O (1) para ellos (suponiendo una función hash lo suficientemente fuerte), en oposición a las listas para las cuales la verificación de inclusión es O ( n) (y conjuntos ordenados para los que es O (log n)). Entonces, si realiza muchas verificaciones, si un elemento está contenido en alguna lista, los hahssets podrían ser una mejora del rendimiento. Si solo itera sobre ellos, no habrá mucha diferencia (iterar sobre todo el conjunto es O (n), igual que con las listas y los hashsets tienen algo más de sobrecarga al agregar elementos).

Y no, no puede indexar un conjunto, lo que no tendría sentido de todos modos, porque los conjuntos no están ordenados. Si agrega algunos elementos, el conjunto no recordará cuál fue primero, qué segundo, etc.

sepp2k
fuente
Si solo itera sobre ellos, entonces el método HashSet agrega bastante uso de memoria en comparación con la Lista.
SamuelWarren
5

HashSet<T>es una estructura de datos en el marco .NET que es capaz de representar un conjunto matemático como un objeto. En este caso, utiliza códigos hash (el GetHashCoderesultado de cada elemento) para comparar la igualdad de los elementos establecidos.

Un conjunto difiere de una lista en que solo permite una aparición del mismo elemento contenido en él. HashSet<T>solo volverá falsesi intenta agregar un segundo elemento idéntico. De hecho, la búsqueda de elementos es muy rápida (O(1) tiempo), ya que la estructura de datos interna es simplemente una tabla hash.

Si se pregunta cuál usar, tenga en cuenta que el uso de un List<T>lugar HashSet<T>apropiado no es el mayor error, aunque puede permitir problemas en los que tenga elementos duplicados no deseados en su colección. Lo que es más, la búsqueda (recuperación de elementos) es mucho más eficiente, idealmente O(1)(para el almacenamiento perfecto) en lugar del O(n)tiempo, lo cual es bastante importante en muchos escenarios.

Noldorin
fuente
1
Agregar un elemento existente a un conjunto no arrojará una excepción. Agregar simplemente devolverá falso. Además: técnicamente, la búsqueda de hash es O (n), no O (1), a menos que tenga una función de hash perfecta. Por supuesto, en la práctica, se saldrá con la suposición de que es O (1) a menos que la función de hash sea realmente mala.
sepp2k
1
@ sepp2k: Sí, por lo que devuelve un valor booleano ... El punto es que te notifica. Y el hash look up es el peor de los casos, O (n) si estás haciendo un bucketing es terrible, está mucho más cerca de O (1) en general.
Noldorin
4

List<T>se utiliza para almacenar conjuntos ordenados de información. Si conoce el orden relativo de los elementos de la lista, puede acceder a ellos en tiempo constante. Sin embargo, para determinar dónde se encuentra un elemento en la lista o para verificar si existe en la lista, el tiempo de búsqueda es lineal. Por otro lado, HashedSet<T>no garantiza el orden de los datos almacenados y, en consecuencia, proporciona un tiempo de acceso constante para sus elementos.

Como su nombre lo indica, HashedSet<T>es una estructura de datos que implementa una semántica establecida . La estructura de datos está optimizada para implementar operaciones de conjunto (es decir, Unión, Diferencia, Intersección), que no se puede hacer de manera tan eficiente con la implementación tradicional de la Lista.

Por lo tanto, elegir qué tipo de datos usar realmente depende de lo que intente hacer con su aplicación. Si no le importa cómo se ordenan sus elementos en una colección y solo desea resumir o verificar la existencia, úselo HashSet<T>. De lo contrario, considere usar List<T>u otra estructura de datos adecuada.

Steve Guidi
fuente
2
Otra advertencia: los conjuntos generalmente permiten solo una aparición de un elemento.
Steve Guidi
1

En resumen: cada vez que sienta la tentación de usar un diccionario (o un diccionario donde S es una propiedad de T), entonces debe considerar un HashSet (o HashSet + implementando IEquatable en T que equivale a S)

Addys
fuente
55
A menos que le importe la clave, debe usar el diccionario.
Hardwareguy
1

En el escenario básico previsto, HashSet<T>debe usarse cuando desee operaciones de conjuntos más específicas en dos colecciones de las que proporciona LINQ. Métodos de LINQ como Distinct, Union, Intersecty Exceptson suficientes en la mayoría de las situaciones, pero a veces es posible que necesite más operaciones de grano fino, y HashSet<T>dispone lo siguiente:

  • UnionWith
  • IntersectWith
  • ExceptWith
  • SymmetricExceptWith
  • Overlaps
  • IsSubsetOf
  • IsProperSubsetOf
  • IsSupersetOf
  • IsProperSubsetOf
  • SetEquals

Otra diferencia entre LINQ y HashSet<T>los métodos "superpuestos" es que LINQ siempre devuelve uno nuevo IEnumerable<T>, y los HashSet<T>métodos modifican la colección de origen.

c_buk
fuente