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

Question

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

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

¿Es sólo para enumeración?

Answer 1

lo importante de HashSet<T> está ahí mismo en 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.

Al preguntar si puede recuperar un elemento individual (por ejemplo, set[45]) no se entiende bien el concepto del conjunto. No existe el elemento 45 de un conjunto. Los elementos 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 HashSet<T> porque al hacerlo impone un orden en los elementos del conjunto. Ese orden no es realmente una propiedad del conjunto. No deberías confiar en eso. Si el orden de los artículos en una colección es importante para usted, esa colección no es un conjunto.

Los conjuntos son muy limitados y tienen miembros únicos. Por otro lado, son realmente rápidos.

Answer 2

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

Si se pregunta qué un conjunto podría ser bueno para: cualquier lugar que desee para deshacerse de los duplicados, obviamente. Como ejemplo ligeramente artificial, digamos que tiene una lista de 10.000 revisiones de proyectos de software y desea saber cuántas personas contribuyeron a ese proyecto. Puede usar un Set<string> e 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.

Answer 3

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

Answer 4

HashSet<T> es una estructura de datos en .NET Framework que es capaz de representar un mathematical set como un objeto. En este caso, utiliza códigos hash (el resultado GetHashCode de cada elemento) para comparar la igualdad de elementos establecidos.

Un conjunto difiere de una lista en la que sólo permite una ocurrencia de un mismo elemento en ella contenidas. HashSet<T> simplemente devolverá false si intenta agregar un segundo elemento idéntico. De hecho, la búsqueda de elementos es muy rápida (O(1) time), ya que la estructura interna de datos es simplemente una tabla hash.

Si usted se pregunta cuál utilizar, tenga en cuenta que el uso de un HashSet<T>, donde es apropiado List<T> no es el error más grande, aunque puede permitir potencialmente a problemas donde hay 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 un cucharón perfecto) en lugar de O(n) tiempo, lo cual es bastante importante en muchos escenarios.

Answer 5

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 set semantics. La estructura de datos está optimizada para implementar operaciones de conjunto (es decir, Unión, Diferencia, Intersección), lo que no se puede hacer tan eficientemente con la implementación de la Lista tradicional.

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

Answer 6

Probablemente el uso más común para hashsets es ver si contienen un elemento determinado, que está cerca de una operación O (1) para ellos (asumiendo una función de hash suficientemente fuerte), en oposición a las listas para las que se busca la inclusión es O (n) (y los conjuntos ordenados para los que es O (log n)). Entonces, si haces muchos controles, si un elemento está en alguna lista, los juegos de hadas pueden ser una mejora en el rendimiento. Si solo itera sobre ellos, no habrá mucha diferencia (iterar sobre todo el conjunto es O (n), lo mismo que con las listas y los conjuntos de claves tienen algo más de sobrecarga al agregar elementos).

Y no, no se 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 el primero, y cuál segundo, etc.

Answer 7

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

Answer 8

Aquí hay un ejemplo real de donde utilizo un HashSet<string>:

Parte de mi resaltador de sintaxis para archivos UnrealScript es una característica nueva que highlights Doxygen-style comments. Necesito poder decir si un comando @ o \ es válido para determinar si se muestra en gris (válido) o rojo (no válido). Tengo un HashSet<string> de todos los comandos válidos, así que cada vez que toco un token @xxx en el lexer, uso validCommands.Contains(tokenText) como mi O (1) verificación de validez. Realmente no me importa nada excepto existencia del comando en el establece de comandos válidos. Veamos las alternativas que enfrenté:

• Dictionary<string, ?>: ¿Qué tipo lo uso para el valor? El valor no tiene sentido ya que solo 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 había agregado para 3.0 y se había extendido para implementar ISet<T> para 4.0.
• List<string>: Si guardo la lista ordenada, puedo usar BinarySearch, que es O (log n) (no he visto este hecho mencionado anteriormente).Sin embargo, desde mi lista de comandos válidos es una lista fija que nunca cambia, esto nunca será más apropiado que simplemente ...
• string[]: Una vez más, Array.BinarySearch da O (log n) el rendimiento. Si la lista es corta, esta podría ser la mejor opción. Siempre tiene menos sobrecarga de espacio que HashSet, Dictionary o List. Incluso con BinarySearch, no es más rápido para juegos grandes, pero para juegos pequeños valdría la pena experimentar. Sin embargo, el mío tiene varios cientos de artículos, así que pasé por esto.

Answer 9

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

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 se extiende la ICollection<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; } 
} 

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

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

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

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

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

Answer 10

HashSet se usaría para eliminar elementos duplicados en una colección IEnumerble. 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 esos códigos se ejecutan, uniqueStrings sostiene { "abc", "ghjr", "YRE", "OBM", "qwrt", "vyeu"};