Docs executáveis de C#: HashSet

Q: O que é um HashSet em C#?

HashSet é uma coleção de itens únicos sem ordem definida. Adicionar um item que já está presente não faz nada, e Contains responde em tempo praticamente constante, não importa o tamanho do conjunto, porque os itens são guardados pelo hash code, como as chaves de um Dictionary.

Q: O que o HashSet.Add retorna?

Add retorna true quando o item foi adicionado e false quando ele já estava no conjunto. Isso faz de if (!seen.Add(x)) uma verificação de duplicata em uma linha: adiciona itens novos e avisa sobre os repetidos na mesma chamada.

Q: Como remover duplicados de uma List em C#?

list.Distinct().ToList() retorna uma nova lista sem duplicados e mantém a primeira ocorrência de cada item na ordem original. new HashSet (list) também remove duplicados, mas um conjunto não tem ordem garantida. Para remover duplicados na própria lista, use var seen = new HashSet (); list.RemoveAll(x => !seen.Add(x));.

Q: Quando usar um HashSet em vez de uma List?

Use um HashSet quando você mais pergunta "este item está na coleção?" ou precisa que os itens sejam únicos. List .Contains varre todos os elementos, então fica mais lento à medida que a lista cresce, e HashSet .Contains não. Use uma List quando ordem, duplicatas ou acesso por índice importam.

Q: Por que meu HashSet contém objetos duplicados?

Sua classe não sobrescreve Equals e GetHashCode, então o conjunto compara referências, e dois objetos com os mesmos valores nos campos contam como diferentes. Sobrescreva os dois métodos (sempre juntos), ou passe um IEqualityComparer ao construtor do conjunto.

Um HashSet<T> é uma coleção em que cada item aparece no máximo uma vez. Ele não tem índice nem ordem garantida, e em troca verifica se um item pertence ao conjunto em tempo praticamente constante: achar uma tag entre um milhão leva mais ou menos o mesmo tempo que achá-la entre dez.

Adicionando itens: Add retorna 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);
    }
}

Saída:

True
False
3
True
True
False
2

Adicionar uma duplicata não é um erro; Add simplesmente retorna false e o conjunto não muda. Esse valor de retorno é o que o método tem de mais útil. Ele junta "já vi isto?" e "guarde isto" em uma única chamada:

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

Saída:

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

Por que o Contains é rápido

List<T>.Contains compara o valor com cada elemento, um de cada vez, então o custo cresce com a lista. Um HashSet<T> calcula o hash code do item, pula para o bucket desse código e compara só os poucos itens guardados ali. Para um teste de pertinência dentro de um laço, isso transforma um passo O(n) em um passo O(1), e um laço aninhado sobre duas listas em uma única passada:

// 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));

Montar o conjunto custa uma passada pela lista, então só compensa quando você faz mais do que algumas consultas.

Removendo duplicados de uma lista

Há três formas comuns, e elas diferem no que acontece com a ordem:

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

Saída:

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

Distinct é o padrão certo quando você quer uma lista de volta. A versão que altera a própria lista funciona porque RemoveAll chama o predicado uma vez por elemento, em ordem: seen.Add retorna false para a segunda cópia em diante, então exatamente essas são removidas.

Operações de conjunto: união, interseção, diferença

HashSet<T> tem as operações da teoria dos conjuntos. Os métodos ...With mudam o conjunto em que são chamados e não retornam 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 }));
    }
}

Saída:

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

O argumento pode ser qualquer IEnumerable<T>: um array, uma lista ou outro conjunto. SetEquals ignora a ordem e as duplicatas do argumento. O auxiliar Show ordena antes de imprimir porque a ordem de enumeração de um conjunto não é algo em que se possa confiar.

O LINQ tem métodos equivalentes que retornam uma nova sequência e não mexem nas entradas: monday.Union(tuesday), monday.Intersect(tuesday), monday.Except(tuesday). Use-os quando você não quer alterar um conjunto, ou quando as entradas são listas.

Igualdade própria para suas classes

Um conjunto decide o que é "o mesmo item" com GetHashCode e Equals. Para uma classe que não os sobrescreve, os dois se baseiam na identidade do objeto, então dois objetos com campos iguais são dois itens diferentes:

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

Saída:

2
1
True

A regra: objetos que são Equals precisam retornar o mesmo GetHashCode. Sobrescreva só o Equals e o conjunto procura no bucket errado e continua aceitando duplicatas. No .NET Core 2.1 em diante, HashCode.Combine(X, Y) gera um bom hash code sem a aritmética escrita à mão.

Quando você não pode mudar a classe, ou precisa de outra noção de "o mesmo" para um conjunto específico, passe um IEqualityComparer<T> ao construtor. Strings já vêm com comparadores prontos:

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

Saída:

True
False
2

No C# 9 em diante, um record gera Equals e GetHashCode baseados em valor para você, então record Point(int X, int Y); funciona em um conjunto sem código extra.

Nunca mude um campo usado no GetHashCode enquanto o objeto estiver em um conjunto. O objeto continua no bucket do hash antigo, então Contains e Remove deixam de encontrá-lo.

Ordem e SortedSet

Um HashSet<T> é enumerado em uma ordem que você deve tratar como arbitrária. Se você precisa dos itens ordenados, ordene ao imprimir (set.OrderBy(x => x)) ou use SortedSet<T>, que mantém os itens sempre ordenados e adiciona Min, Max e consultas por intervalo a O(log n) por operação:

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

HashSet vs List vs Dictionary

Necessidade	Use
Itens únicos, "está aqui?" rápido	`HashSet<T>`
Itens únicos, sempre ordenados	`SortedSet<T>`
Ordem, duplicatas, acesso por índice	`List<T>`
Um valor guardado sob cada chave	`Dictionary<TKey, TValue>`

Um conjunto é um dicionário com chaves e sem valores. Se você se pegar escrevendo Dictionary<string, bool> só para registrar pertinência, um HashSet<string> diz a mesma coisa com mais clareza.

Erros comuns

Esperar uma ordem. Um conjunto não tem uma ordem confiável; ordene, ou use SortedSet<T>.
Classes próprias sem Equals e GetHashCode. Objetos que parecem iguais viram itens separados.
Sobrescrever só o Equals. Sempre sobrescreva o GetHashCode junto.
Alterar um item depois de adicioná-lo. O conjunto não consegue mais encontrá-lo.
Acessar um conjunto por índice. set[0] não compila; não existe índice. Converta com ToList() se precisar de posições.

Perguntas frequentes

O que é um HashSet em C#?

HashSet<T> é uma coleção de itens únicos sem ordem definida. Adicionar um item que já está presente não faz nada, e Contains responde em tempo praticamente constante, não importa o tamanho do conjunto, porque os itens são guardados pelo hash code, como as chaves de um Dictionary.

O que o HashSet.Add retorna?

Add retorna true quando o item foi adicionado e false quando ele já estava no conjunto. Isso faz de if (!seen.Add(x)) uma verificação de duplicata em uma linha: adiciona itens novos e avisa sobre os repetidos na mesma chamada.

Como remover duplicados de uma List em C#?

list.Distinct().ToList() retorna uma nova lista sem duplicados e mantém a primeira ocorrência de cada item na ordem original. new HashSet<T>(list) também remove duplicados, mas um conjunto não tem ordem garantida. Para remover duplicados na própria lista, use var seen = new HashSet<T>(); list.RemoveAll(x => !seen.Add(x));.

Quando usar um HashSet em vez de uma List?

Use um HashSet<T> quando você mais pergunta "este item está na coleção?" ou precisa que os itens sejam únicos. List<T>.Contains varre todos os elementos, então fica mais lento à medida que a lista cresce, e HashSet<T>.Contains não. Use uma List<T> quando ordem, duplicatas ou acesso por índice importam.

Por que meu HashSet contém objetos duplicados?

Sua classe não sobrescreve Equals e GetHashCode, então o conjunto compara referências, e dois objetos com os mesmos valores nos campos contam como diferentes. Sobrescreva os dois métodos (sempre juntos), ou passe um IEqualityComparer<T> ao construtor do conjunto.

Conceitos relacionados