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

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?

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.

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.

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".

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.

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.

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"};

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.

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.

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.

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)

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.