Docs ejecutables de C#: HashSet

Q: ¿Qué es un HashSet en C#?

HashSet es una colección de elementos únicos sin un orden definido. Añadir un elemento que ya está no hace nada, y Contains responde en un tiempo aproximadamente constante sea cual sea el tamaño del conjunto, porque los elementos se guardan por código hash como las claves de un Dictionary.

Q: ¿Qué devuelve HashSet.Add?

Add devuelve true cuando el elemento se añadió y false cuando ya estaba en el conjunto. Eso convierte if (!seen.Add(x)) en una comprobación de duplicados de una línea: añade los elementos nuevos y te avisa de los repetidos en la misma llamada.

Q: ¿Cómo quito los duplicados de una List en C#?

list.Distinct().ToList() devuelve una lista nueva sin duplicados y conserva la primera aparición de cada elemento en su orden original. new HashSet (list) también quita los duplicados, pero un conjunto no tiene un orden garantizado. Para quitarlos en el sitio, usa var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));.

Q: ¿Cuándo debo usar un HashSet en lugar de una List?

Usa un HashSet cuando sobre todo preguntas "¿está este elemento en la colección?" o necesitas que los elementos sean únicos. List .Contains recorre todos los elementos, así que se vuelve más lento a medida que crece la lista, mientras que HashSet .Contains no. Usa una List cuando importan el orden, los duplicados o el acceso por índice.

Q: ¿Por qué mi HashSet contiene objetos duplicados?

Tu clase no sobrescribe Equals ni GetHashCode, así que el conjunto compara referencias y dos objetos con los mismos valores en sus campos cuentan como distintos. Sobrescribe los dos métodos (siempre juntos), o pasa un IEqualityComparer al constructor del conjunto.

Un HashSet<T> es una colección en la que cada elemento aparece como mucho una vez. No tiene índice ni un orden garantizado, y a cambio comprueba la pertenencia en un tiempo aproximadamente constante: encontrar una etiqueta entre un millón tarda más o menos lo mismo que encontrarla entre diez.

Añadir elementos: Add devuelve bool

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var tags = new HashSet<string> { "sale", "new" };

        Console.WriteLine(tags.Add("gift"));  // added
        Console.WriteLine(tags.Add("sale"));  // already present
        Console.WriteLine(tags.Count);

        Console.WriteLine(tags.Contains("new"));
        Console.WriteLine(tags.Remove("new"));
        Console.WriteLine(tags.Remove("used")); // not there: false, no exception
        Console.WriteLine(tags.Count);
    }
}

Salida:

True
False
3
True
True
False
2

Añadir un duplicado no es un error; Add simplemente devuelve false y el conjunto no cambia. Ese valor de retorno es lo más útil del método. Combina "¿lo he visto ya?" y "recuérdalo" en una sola llamada:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        string[] signups = { "ana@x.com", "ben@x.com", "ana@x.com", "cy@x.com", "ben@x.com" };
        var seen = new HashSet<string>();

        foreach (string email in signups)
        {
            if (!seen.Add(email))
            {
                Console.WriteLine("Duplicate: " + email);
            }
        }
        Console.WriteLine(seen.Count + " unique");
    }
}

Salida:

Duplicate: ana@x.com
Duplicate: ben@x.com
3 unique

Por qué Contains es rápido

List<T>.Contains compara el valor con cada elemento por turnos, así que su coste crece con la lista. Un HashSet<T> calcula el código hash del elemento, salta al cubo de ese código y compara solo los pocos elementos guardados ahí. En una prueba de pertenencia dentro de un bucle, eso convierte un paso O(n) en un paso O(1), y un bucle anidado sobre dos listas en una sola pasada:

// Slow on large inputs: Contains scans bannedList for every order.
var flagged = orders.Where(o => bannedList.Contains(o.CustomerId));

// Fast: build the set once, then each lookup is constant time.
var banned = new HashSet<int>(bannedList);
var flagged2 = orders.Where(o => banned.Contains(o.CustomerId));

Construir el conjunto cuesta una pasada por la lista, así que solo compensa cuando buscas más de unas pocas veces.

Quitar duplicados de una lista

Hay tres formas habituales, y se diferencian en lo que pasa con el orden:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        var cities = new List<string> { "Lima", "Oslo", "Lima", "Pune", "Oslo", "Kyiv" };

        // 1. LINQ Distinct: new list, first occurrences in original order
        List<string> unique = cities.Distinct().ToList();
        Console.WriteLine(string.Join(", ", unique));

        // 2. A set: unique, but a set has no guaranteed order
        var set = new HashSet<string>(cities);
        Console.WriteLine(set.Count);

        // 3. In place, keeping order: RemoveAll with a seen-set
        var seen = new HashSet<string>();
        cities.RemoveAll(c => !seen.Add(c));
        Console.WriteLine(string.Join(", ", cities));
    }
}

Salida:

Lima, Oslo, Pune, Kyiv
4
Lima, Oslo, Pune, Kyiv

Distinct es la opción por defecto correcta cuando quieres obtener una lista. La versión en el sitio funciona porque RemoveAll llama al predicado una vez por elemento y en orden: seen.Add devuelve false para la segunda copia y las siguientes, así que se eliminan exactamente esas.

Operaciones de conjuntos: unión, intersección, diferencia

HashSet<T> tiene las operaciones de la teoría de conjuntos. Los métodos ...With cambian el conjunto sobre el que se llaman y no devuelven nada.

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string Show(HashSet<string> s)
    {
        return string.Join(", ", s.OrderBy(x => x));
    }

    static void Main()
    {
        string[] monday = { "Ana", "Ben", "Chloe" };
        string[] tuesday = { "Ben", "Chloe", "Dev" };

        var either = new HashSet<string>(monday);
        either.UnionWith(tuesday);             // in either list
        Console.WriteLine("Union:     " + Show(either));

        var both = new HashSet<string>(monday);
        both.IntersectWith(tuesday);           // in both
        Console.WriteLine("Intersect: " + Show(both));

        var onlyMonday = new HashSet<string>(monday);
        onlyMonday.ExceptWith(tuesday);        // in monday, not tuesday
        Console.WriteLine("Except:    " + Show(onlyMonday));

        var oneDay = new HashSet<string>(monday);
        oneDay.SymmetricExceptWith(tuesday);   // in exactly one
        Console.WriteLine("Symmetric: " + Show(oneDay));

        Console.WriteLine(both.IsSubsetOf(monday));
        Console.WriteLine(either.IsSupersetOf(tuesday));
        Console.WriteLine(onlyMonday.Overlaps(tuesday));
        Console.WriteLine(new HashSet<int> { 1, 2 }.SetEquals(new[] { 2, 1, 1 }));
    }
}

Salida:

Union:     Ana, Ben, Chloe, Dev
Intersect: Ben, Chloe
Except:    Ana
Symmetric: Ana, Dev
True
True
False
True

El argumento puede ser cualquier IEnumerable<T>: un array, una lista u otro conjunto. SetEquals ignora el orden y los duplicados del argumento. El método auxiliar Show ordena antes de imprimir porque el orden de enumeración de un conjunto no es algo en lo que se pueda confiar.

LINQ tiene métodos equivalentes que devuelven una secuencia nueva y no tocan las entradas: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Úsalos cuando no quieras modificar un conjunto, o cuando las entradas sean listas.

Igualdad propia para tus clases

Un conjunto decide si dos elementos son "el mismo" con GetHashCode y Equals. En una clase que no los sobrescribe, los dos se basan en la identidad del objeto, así que dos objetos con campos iguales son dos elementos distintos:

using System;
using System.Collections.Generic;

class Point
{
    public int X, Y;
    public Point(int x, int y) { X = x; Y = y; }
}

class Coord
{
    public int X, Y;
    public Coord(int x, int y) { X = x; Y = y; }

    public override bool Equals(object obj)
    {
        var other = obj as Coord;
        return other != null && other.X == X && other.Y == Y;
    }

    public override int GetHashCode()
    {
        unchecked { return X * 397 ^ Y; }
    }
}

class Program
{
    static void Main()
    {
        var points = new HashSet<Point> { new Point(1, 2), new Point(1, 2) };
        Console.WriteLine(points.Count); // 2: compared by reference

        var coords = new HashSet<Coord> { new Coord(1, 2), new Coord(1, 2) };
        Console.WriteLine(coords.Count); // 1: compared by value
        Console.WriteLine(coords.Contains(new Coord(1, 2)));
    }
}

Salida:

2
1
True

La regla: los objetos que son Equals deben devolver el mismo GetHashCode. Si solo sobrescribes Equals, el conjunto busca en el cubo equivocado y sigue informando de duplicados. En .NET Core 2.1 y posteriores, HashCode.Combine(X, Y) construye un buen código hash sin aritmética escrita a mano.

Cuando no puedes cambiar la clase, o necesitas otra noción de "el mismo" para un conjunto concreto, pasa un IEqualityComparer<T> al constructor. Los strings traen comparadores ya hechos:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var extensions = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { ".jpg", ".png" };
        Console.WriteLine(extensions.Contains(".JPG"));
        Console.WriteLine(extensions.Add(".PNG"));
        Console.WriteLine(extensions.Count);
    }
}

Salida:

True
False
2

En C# 9 y posteriores, un record genera por ti Equals y GetHashCode basados en el valor, así que record Point(int X, int Y); funciona en un conjunto sin código extra.

Nunca cambies un campo que interviene en GetHashCode mientras el objeto está en un conjunto. El objeto se queda en el cubo de su hash antiguo, así que Contains y Remove dejan de encontrarlo.

Orden y SortedSet

Un HashSet<T> se enumera en un orden que debes tratar como arbitrario. Si necesitas los elementos ordenados, ordena al imprimir (set.OrderBy(x => x)) o usa SortedSet<T>, que mantiene los elementos ordenados en todo momento y añade Min, Max y consultas por rango con un coste O(log n) por operación:

var ranks = new SortedSet<int> { 30, 10, 20 };
Console.WriteLine(string.Join(", ", ranks)); // 10, 20, 30
Console.WriteLine(ranks.Min);                // 10

HashSet frente a List frente a Dictionary

Necesidad	Usa
Elementos únicos, "¿está?" rápido	`HashSet<T>`
Elementos únicos, siempre ordenados	`SortedSet<T>`
Orden, duplicados, acceso por índice	`List<T>`
Un valor guardado bajo cada clave	`Dictionary<TKey, TValue>`

Un conjunto es un diccionario con claves y sin valores. Si te encuentras escribiendo Dictionary<string, bool> solo para llevar la cuenta de la pertenencia, un HashSet<string> dice lo mismo con más claridad.

Errores comunes

Esperar un orden. Un conjunto no tiene ninguno fiable; ordena, o usa SortedSet<T>.
Clases propias sin Equals ni GetHashCode. Objetos que parecen iguales se convierten en elementos distintos.
Sobrescribir solo Equals. Sobrescribe siempre GetHashCode junto con él.
Modificar un elemento después de añadirlo. El conjunto ya no puede encontrarlo.
Indexar un conjunto. set[0] no compila; no hay índice. Convierte con ToList() si necesitas posiciones.

Preguntas frecuentes

¿Qué es un HashSet en C#?

HashSet<T> es una colección de elementos únicos sin un orden definido. Añadir un elemento que ya está no hace nada, y Contains responde en un tiempo aproximadamente constante sea cual sea el tamaño del conjunto, porque los elementos se guardan por código hash como las claves de un Dictionary.

¿Qué devuelve HashSet.Add?

Add devuelve true cuando el elemento se añadió y false cuando ya estaba en el conjunto. Eso convierte if (!seen.Add(x)) en una comprobación de duplicados de una línea: añade los elementos nuevos y te avisa de los repetidos en la misma llamada.

¿Cómo quito los duplicados de una List en C#?

list.Distinct().ToList() devuelve una lista nueva sin duplicados y conserva la primera aparición de cada elemento en su orden original. new HashSet<T>(list) también quita los duplicados, pero un conjunto no tiene un orden garantizado. Para quitarlos en el sitio, usa var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));.

¿Cuándo debo usar un HashSet en lugar de una List?

Usa un HashSet<T> cuando sobre todo preguntas "¿está este elemento en la colección?" o necesitas que los elementos sean únicos. List<T>.Contains recorre todos los elementos, así que se vuelve más lento a medida que crece la lista, mientras que HashSet<T>.Contains no. Usa una List<T> cuando importan el orden, los duplicados o el acceso por índice.

¿Por qué mi HashSet contiene objetos duplicados?

Tu clase no sobrescribe Equals ni GetHashCode, así que el conjunto compara referencias y dos objetos con los mismos valores en sus campos cuentan como distintos. Sobrescribe los dos métodos (siempre juntos), o pasa un IEqualityComparer<T> al constructor del conjunto.

Conceptos relacionados