¿Cuándo debería usar el tipo HashSet ?

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

¿Se puede usar para reemplazar una List ? Me imagino que el rendimiento de un HashSet es mejor, pero no pude ver el acceso individual a sus elementos.

¿Es solo para enumeración?

Lo importante sobre HashSet está ahí 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.

Preguntar si se puede recuperar un elemento individual (por ejemplo, el set[45] ) está malinterpretando 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 un HashSet 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 realmente limitados y con miembros únicos. Por otro lado, son realmente rápidos.

Aquí hay un ejemplo real de donde uso un HashSet :

Parte de mi resaltador de syntax para archivos UnrealScript es una nueva característica que resalta los comentarios estilo Doxygen . 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 de todos los comandos válidos, así que cada vez que @xxx un token @xxx en el lexer, uso validCommands.Contains(tokenText) como mi O (1) verificación de validez. Realmente no me importa nada excepto la existencia del comando en el conjunto de comandos válidos. Veamos las alternativas que enfrenté:

  • Dictionary : ¿Qué tipo de uso utilizo 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 de O (1) – HashSet se agregó para 3.0 y se extendió para implementar ISet para 4.0.
  • List : si guardo la lista ordenada, puedo usar BinarySearch , que es O (log n) (no he visto 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[] : Nuevamente, Array.BinarySearch da el Array.BinarySearch O (log n). Si la lista es corta, esta podría ser la mejor opción. Siempre tiene una sobrecarga de espacio menor 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.

Un HashSet implementa la ICollection :

 public interface ICollection : IEnumerable, 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; } } 

Una List implementa IList , que amplía el ICollection

 public interface IList : ICollection { // 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 la 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 particular.

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

Agregar y recuperar elementos del HashSet siempre es 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) recupera por índice, O (n) find /retirar).

El comportamiento de un HashSet podría compararse con el uso de un Dictionary solo agregando / eliminando claves como valores e ignorando 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”.

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

HashSet es un conjunto implementado por hash. 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 te estás preguntando para qué sirve un conjunto: obviamente, en cualquier lugar que desees eliminar los duplicados. 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 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.

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

 List duplicatedEnumrableStrings = new List {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"}; HashSet 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 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 listas para las que la inclusión es O ( n) (y conjuntos ordenados para los cuales 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 el segundo, etc.

List se usa para almacenar conjuntos de información ordenados. 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 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 es una estructura de datos que implementa la semántica establecida . 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 tradicional de la Lista.

Por lo tanto, elegir qué tipo de datos usar realmente depende de lo que esté intentando 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 . De lo contrario, considere usar List u otra estructura de datos adecuada.

HashSet es una estructura de datos en .NET Framework que es capaz de representar un conjunto matemático 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 que solo permite una ocurrencia del mismo elemento contenido en él. HashSet simplemente devolverá false si 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 interna de datos es simplemente una tabla hash.

Si se pregunta qué usar, tenga en cuenta que usar una List donde HashSet es apropiado no es el mayor error, aunque puede permitir problemas donde tiene elementos duplicados indeseables en su colección. Además, la búsqueda (recuperación de elementos) es mucho más eficiente, idealmente O(1) (para un ciclo perfecto) en lugar de O(n) tiempo, lo cual es bastante importante en muchos escenarios.

En resumen: cada vez que sienta la tentación de usar un diccionario (o un diccionario en el que S es propiedad de T), debería considerar un HashSet (o HashSet + que implementa IEquatable en T, que equivale a S)