C# HashSet<T>

Às vezes você não quer uma lista, quer um conjunto: as figurinhas que a Ana já tem, os nomes de quem confirmou presença, as palavras que já apareceram num texto. Num conjunto, cada coisa aparece uma vez só, e a pergunta mais importante é "isto está aqui?". O HashSet<T> responde essa pergunta num instante, mesmo com milhões de itens, e ainda faz as contas de conjuntos da escola: união, interseção e diferença.

Todos os programas desta aula rodaram com o .NET 10 na máquina da Ana (usuária ana, computador notebook), na pasta ~/cs, com dotnet run arquivo.cs. Você pode repetir cada um no editor do guia.

A ideia: um álbum de figurinhas

A Ana coleciona figurinhas. No álbum, cada figurinha tem um lugar só: colar a figurinha 7 de novo não cria uma segunda 7, ela vai para o monte de repetidas. E, quando um amigo oferece uma figurinha, a primeira pergunta é: "eu já tenho essa?".

Um HashSet<T> ("conjunto por hash") é esse álbum:

• Não aceita repetidos. Tentar acrescentar um item que já está lá não faz nada (e ele avisa que não fez).
• Não tem posições. Não existe "a figurinha da posição 0". Existe só "tem" ou "não tem".
• Responde "tem?" muito rápido. Numa List, o Contains olha item por item; num HashSet, ele vai direto ao lugar certo, como o Dictionary faz com as chaves.

O T em HashSet<T> é o tipo dos itens, escolhido por você: HashSet<int> guarda números; HashSet<string>, textos (veja Generics).

1. Criar, acrescentar e perguntar

var album = new HashSet<int>();

Console.WriteLine(album.Add(7));
Console.WriteLine(album.Add(12));
Console.WriteLine(album.Add(7));
album.Add(30);

Console.WriteLine($"Figurinhas diferentes: {album.Count}");
Console.WriteLine(album.Contains(12));
Console.WriteLine(album.Contains(99));

Console.WriteLine(album.Remove(12));
Console.WriteLine(album.Remove(12));
Console.WriteLine($"Figurinhas diferentes: {album.Count}");
Console.WriteLine(album);

$ dotnet run album.cs
True                              « a 7 entrou
True                              « a 12 entrou
False                             « a 7 já estava: não entrou de novo
Figurinhas diferentes: 3          « 7, 12 e 30
True
False
True                              « tirou a 12
False                             « a 12 já não estava lá
Figurinhas diferentes: 2
System.Collections.Generic.HashSet`1[System.Int32]

new HashSet<int>()

Cria um conjunto vazio de números inteiros.

album.Add(7)

Add = acrescentar. Devolve um bool: true se o item entrou, false se ele já estava no conjunto. Diferente do Add do Dictionary, aqui um repetido não lança exceção.

album.Add(30);

Você pode ignorar o bool quando não precisa dele.

album.Count

Quantos itens diferentes o conjunto tem.

album.Contains(12)

Contains = contém. "A 12 está no álbum?" É a pergunta que o HashSet responde mais rápido.

album.Remove(12)

Tira o item. Devolve true se ele estava lá e false se não estava (sem exceção).

Console.WriteLine(album)

Como o Dictionary, o conjunto não mostra o conteúdo: aparece só o nome do tipo. Para ver os itens, use foreach ou string.Join.

O bool do Add trabalha para você

Como o Add já diz se o item é novo, você não precisa de um Contains antes. Este laço acha as figurinhas repetidas de um pacote numa passada só:

int[] pacote = [5, 18, 5, 40, 18, 5];
var album = new HashSet<int>();

foreach (int fig in pacote)
{
    if (!album.Add(fig))
        Console.WriteLine($"Repetida: {fig}");
}
Console.WriteLine($"Coladas: {album.Count}");

$ dotnet run pacote.cs
Repetida: 5
Repetida: 18
Repetida: 5
Coladas: 3

Leia if (!album.Add(fig)) como "se não deu para colar". O ! é o "não" de Operadores Lógicos. O Add sempre tenta colar; quando devolve false, a figurinha era repetida.

Criar já com itens

Dá para criar o conjunto com itens entre chaves (o inicializador) ou a partir de outra coleção. Repetidos são ignorados nas duas formas:

var cores = new HashSet<string> { "azul", "verde", "azul" };
int[] numeros = [3, 1, 3, 2];
var semRepetir = new HashSet<int>(numeros);
HashSet<char> vogais = ['a', 'e', 'i', 'o', 'u'];

A última linha usa a expressão de coleção [ … ] C# 12, que também funciona com HashSet quando o tipo está escrito à esquerda.

2. Tirar os repetidos de uma lista

A Ana anotou quem confirmou presença na festa, mas algumas pessoas confirmaram duas vezes. Quantas pessoas vêm de verdade?

string[] convidados = ["Ana", "Bruno", "Ana", "Carla", "Bruno", "Ana"];

var semRepetir = new HashSet<string>(convidados);

Console.WriteLine($"Nomes na lista: {convidados.Length}");
Console.WriteLine($"Pessoas diferentes: {semRepetir.Count}");

foreach (string nome in semRepetir)
{
    Console.WriteLine(nome);
}

$ dotnet run repetidos.cs
Nomes na lista: 6
Pessoas diferentes: 3
Ana
Bruno
Carla

A linha new HashSet<string>(convidados) passa todos os nomes do array para o conjunto, e os repetidos simplesmente não entram. O foreach percorre o conjunto como percorreria uma lista.

string[] telefones = ["99001-0001", "99001-0002", "99001-0001", "99001-0003",
                      "99001-0002", "99001-0004", "99001-0001"];

Console.WriteLine($"Telefones diferentes: {telefones.Length}");

string[] telefones = ["99001-0001", "99001-0002", "99001-0001", "99001-0003",
                      "99001-0002", "99001-0004", "99001-0001"];

var diferentes = new HashSet<string>(telefones);
Console.WriteLine($"Telefones diferentes: {diferentes.Count}");

A ordem de um HashSet

Os convidados saíram na ordem em que foram anotados, mas não conte com isso. O HashSet não promete nenhuma ordem: ele guarda cada item no lugar que o hash code do item indica (uma "impressão digital" numérica; veja A Classe object), e, quando um item sai, o próximo que entra pode ocupar o lugar vago:

var cores = new HashSet<string> { "azul", "verde", "vermelho", "amarelo" };
Console.WriteLine(string.Join(", ", cores));

cores.Remove("verde");
cores.Add("roxo");
Console.WriteLine(string.Join(", ", cores));

var ordenado = new SortedSet<string>(cores);
Console.WriteLine(string.Join(", ", ordenado));

$ dotnet run ordem.cs
azul, verde, vermelho, amarelo
azul, roxo, vermelho, amarelo      « o roxo entrou por último, mas ficou no lugar do verde
amarelo, azul, roxo, vermelho      « SortedSet: sempre em ordem

3. Operações de conjunto

Lembra dos diagramas de Venn da escola, com dois círculos que se cruzam? O HashSet faz essas contas. A Ana e o Bruno escolheram matérias para a monitoria:

  Ana:    Matemática  Física  Química
  Bruno:              Física  Química  História

var ana = new HashSet<string> { "Matemática", "Física", "Química" };
var bruno = new HashSet<string> { "Física", "História", "Química" };

var juntas = new HashSet<string>(ana);
juntas.UnionWith(bruno);
Console.WriteLine($"União: {string.Join(", ", juntas.Order())}");

var comum = new HashSet<string>(ana);
comum.IntersectWith(bruno);
Console.WriteLine($"Interseção: {string.Join(", ", comum.Order())}");

var soAna = new HashSet<string>(ana);
soAna.ExceptWith(bruno);
Console.WriteLine($"Só a Ana: {string.Join(", ", soAna.Order())}");

var soUm = new HashSet<string>(ana);
soUm.SymmetricExceptWith(bruno);
Console.WriteLine($"Só um dos dois: {string.Join(", ", soUm.Order())}");

Console.WriteLine($"ana continua com {ana.Count}");

$ dotnet run operacoes.cs
União: Física, História, Matemática, Química
Interseção: Física, Química
Só a Ana: Matemática
Só um dos dois: História, Matemática
ana continua com 3

Perguntas sobre dois conjuntos

var turma = new HashSet<string> { "Ana", "Bruno", "Carla", "Davi" };
var time = new HashSet<string> { "Ana", "Carla" };
var outros = new HashSet<string> { "Eva", "Fábio" };

Console.WriteLine(time.IsSubsetOf(turma));
Console.WriteLine(turma.IsSupersetOf(time));
Console.WriteLine(turma.Overlaps(outros));
Console.WriteLine(time.SetEquals(new[] { "Carla", "Ana", "Ana" }));

$ dotnet run perguntas.cs
True                « todo mundo do time está na turma
True                « a turma contém o time
False               « a turma e os outros não têm ninguém em comum
True                « os mesmos itens; a ordem e os repetidos não contam

4. Maiúsculas e minúsculas

Para o HashSet<string>, "CSharp" e "csharp" são itens diferentes. Como no Dictionary, um comparador na criação muda isso:

var tags = new HashSet<string>(StringComparer.OrdinalIgnoreCase) { "CSharp", "csharp", "CSHARP", "dotnet" };
Console.WriteLine(tags.Count);
Console.WriteLine(tags.Contains("DotNet"));

$ dotnet run caixa.cs
2                « as três formas de "csharp" contaram como uma só
True

5. Conjuntos de objetos seus: class × record

Para saber se um item "já está lá", o HashSet precisa comparar itens. Com números e textos, ele compara o conteúdo. Com objetos de uma class sua, o padrão é comparar a identidade: dois objetos criados com new são dois objetos diferentes, mesmo com os mesmos dados (veja Valor × Referência).

var pontosClasse = new HashSet<PontoClasse>();
pontosClasse.Add(new PontoClasse { X = 1, Y = 2 });
pontosClasse.Add(new PontoClasse { X = 1, Y = 2 });
Console.WriteLine($"class: {pontosClasse.Count}");

var pontosRecord = new HashSet<PontoRecord>();
pontosRecord.Add(new PontoRecord(1, 2));
pontosRecord.Add(new PontoRecord(1, 2));
Console.WriteLine($"record: {pontosRecord.Count}");

class PontoClasse
{
    public int X { get; set; }
    public int Y { get; set; }
}

record PontoRecord(int X, int Y);

$ dotnet run objetos.cs
class: 2               « dois objetos diferentes, mesmo com X = 1 e Y = 2
record: 1              « o record compara os dados: é o mesmo ponto

Um record já vem com Equals e GetHashCode que comparam os dados, por isso o segundo ponto (1, 2) não entrou. Numa class, você teria de escrever esses dois métodos (aula A Classe object). Regra prática: para guardar objetos "de dados" num HashSet ou usá-los como chave de um Dictionary, prefira record.

6. Mudar o conjunto dentro do foreach

Como no Dictionary, você não pode acrescentar itens no conjunto que o foreach está percorrendo:

var album = new HashSet<int> { 7, 12, 30 };

foreach (int fig in album)
{
    album.Add(fig + 100);
}

$ dotnet run foreach.cs
Unhandled exception. System.InvalidOperationException: Collection was modified; enumeration operation may not execute.
   at System.Collections.Generic.HashSet`1.Enumerator.MoveNext()
   at Program.<Main>$(String[] args) in /home/ana/cs/foreach.cs:line 3
$ echo $?
134

"A coleção foi modificada; o percurso não pode continuar." A linha apontada é a 3, a do foreach: o Add funcionou, mas o foreach percebeu a mudança quando foi buscar o próximo item (MoveNext). Para acrescentar, junte os itens novos em outra coleção e acrescente depois do laço. E, para tirar todos os itens que cumprem uma condição, o HashSet tem um método pronto, o RemoveWhere ("remover onde"):

var album = new HashSet<int> { 7, 12, 30, 41, 50 };
int tirados = album.RemoveWhere(n => n % 2 == 0);
Console.WriteLine($"Tirados: {tirados}");
Console.WriteLine(string.Join(", ", album.Order()));

$ dotnet run removewhere.cs
Tirados: 3
7, 41

O n => n % 2 == 0 é uma lambda: uma minifunção que recebe cada número n e diz se ele deve sair (aqui, os pares: resto 0 na divisão por 2). O RemoveWhere devolve quantos itens tirou.

Qual coleção usar?

Quando dá errado

$ dotnet run indice.cs
/home/ana/cs/indice.cs(2,19): error CS0021: Não é possível aplicar a indexação com [] a uma expressão do tipo "HashSet<int>"

Ocorreu uma falha no build. Corrija os erros de build e execute novamente.

Referência rápida

Exercícios

Missão final: troca de figurinhas

Bruno pode dar: 3, 8
Os dois têm: 2, 5, 9
A Ana continua com 5

var ana = new HashSet<int> { 1, 2, 4, 5, 9 };
var bruno = new HashSet<int> { 2, 3, 5, 8, 9 };

// 1. copie o conjunto do Bruno e tire o que a Ana já tem

// 2. copie o conjunto da Ana e fique só com o que o Bruno também tem

Console.WriteLine($"A Ana continua com {ana.Count}");

var ana = new HashSet<int> { 1, 2, 4, 5, 9 };
var bruno = new HashSet<int> { 2, 3, 5, 8, 9 };

var podeDar = new HashSet<int>(bruno);
podeDar.ExceptWith(ana);
Console.WriteLine($"Bruno pode dar: {string.Join(", ", podeDar.Order())}");

var emComum = new HashSet<int>(ana);
emComum.IntersectWith(bruno);
Console.WriteLine($"Os dois têm: {string.Join(", ", emComum.Order())}");

Console.WriteLine($"A Ana continua com {ana.Count}");

Resumo

• Um HashSet<T> é um conjunto: sem repetidos, sem posições e com um Contains muito rápido.
• Add devolve true se o item entrou e false se ele já estava (sem exceção). Remove devolve se tirou.
• new HashSet<T>(lista) tira os repetidos de uma lista em uma linha.
• A ordem não é garantida (muda depois de remoções). Para ordem, use SortedSet<T> ou .Order() ao mostrar.
• UnionWith, IntersectWith, ExceptWith e SymmetricExceptWith mudam o conjunto: copie antes se precisar do original.
• Objetos de uma class são comparados pela identidade; os de um record, pelos dados.
• conjunto[0] dá CS0021; acrescentar dentro do foreach dá InvalidOperationException.