HashSet<T>: Conjunto em Rust

O HashSet<T> é a implementação de conjunto (set) da biblioteca padrão do Rust. Ele armazena elementos únicos sem repetição e oferece busca, inserção e remoção em tempo O(1) amortizado. Internamente, é construído sobre um HashMap<T, ()>, aproveitando toda a eficiência da tabela hash.

Quando Usar HashSet

Use HashSet quando:

Precisa garantir que não há duplicatas em uma coleção.
Precisa verificar pertinência rapidamente (“este elemento está no conjunto?”).
Quer realizar operações de conjunto: união, interseção, diferença e diferença simétrica.
A ordem dos elementos não importa.

Se precisar de iteração em ordem, use BTreeSet. Se precisar associar valores às chaves, use HashMap.

Criando e Inicializando

use std::collections::HashSet;

fn main() {
    // Criar vazio
    let mut frutas: HashSet<String> = HashSet::new();

    // Criar com capacidade inicial (evita realocações)
    let mut numeros: HashSet<i32> = HashSet::with_capacity(100);

    // Criar a partir de um array
    let cores = HashSet::from(["vermelho", "verde", "azul"]);

    // Criar a partir de um vetor com collect (remove duplicatas!)
    let dados = vec![1, 2, 3, 2, 1, 4, 3, 5];
    let unicos: HashSet<i32> = dados.into_iter().collect();
    println!("Únicos: {:?}", unicos); // {1, 2, 3, 4, 5}

    // Criar a partir de uma string (caracteres únicos)
    let texto = "abracadabra";
    let letras: HashSet<char> = texto.chars().collect();
    println!("Letras únicas: {:?}", letras); // {'a', 'b', 'r', 'c', 'd'}
}

Tabela de Métodos Comuns

Método	Descrição	Complexidade
`insert(value)`	Insere elemento; retorna `true` se era novo	O(1) amortizado
`remove(&value)`	Remove elemento; retorna `true` se existia	O(1) amortizado
`contains(&value)`	Verifica se o elemento existe	O(1) amortizado
`get(&value)`	Retorna referência ao elemento, se existir	O(1) amortizado
`len()` / `is_empty()`	Tamanho e verificação de vazio	O(1)
`clear()`	Remove todos os elementos	O(n)
`iter()`	Iterador sobre referências `&T`	O(n)
`union(&other)`	Elementos em `self` OU `other`	O(n + m)
`intersection(&other)`	Elementos em `self` E `other`	O(min(n, m))
`difference(&other)`	Elementos em `self` mas NÃO em `other`	O(n)
`symmetric_difference(&other)`	Elementos em `self` OU `other`, mas não em ambos	O(n + m)
`is_subset(&other)`	Verifica se `self` é subconjunto de `other`	O(n)
`is_superset(&other)`	Verifica se `self` é superconjunto de `other`	O(m)
`is_disjoint(&other)`	Verifica se não há elementos em comum	O(min(n, m))
`retain(f)`	Mantém apenas elementos onde `f` retorna `true`	O(n)
`drain()`	Remove e retorna todos os elementos	O(n)

Exemplos Práticos

1. Inserção, Remoção e Verificação

use std::collections::HashSet;

fn main() {
    let mut linguagens: HashSet<&str> = HashSet::new();

    // insert retorna true se o elemento era novo
    assert!(linguagens.insert("Rust"));
    assert!(linguagens.insert("Python"));
    assert!(linguagens.insert("Go"));
    assert!(!linguagens.insert("Rust")); // já existia!

    println!("Total: {} linguagens", linguagens.len()); // 3

    // Verificação de pertinência
    if linguagens.contains("Rust") {
        println!("Rust está no conjunto!");
    }

    // Remoção
    let removido = linguagens.remove("Go");
    println!("Go removido? {}", removido); // true

    // Iteração (ordem não garantida)
    for lang in &linguagens {
        println!("- {}", lang);
    }
}

2. Operações de Conjunto — União, Interseção, Diferença

use std::collections::HashSet;

fn main() {
    let frontend: HashSet<&str> = HashSet::from([
        "JavaScript", "TypeScript", "HTML", "CSS", "Rust",
    ]);

    let backend: HashSet<&str> = HashSet::from([
        "Rust", "Go", "Python", "Java", "TypeScript",
    ]);

    // União: linguagens em frontend OU backend
    let todas: HashSet<&str> = frontend.union(&backend).copied().collect();
    println!("Todas: {:?}", todas);

    // Interseção: linguagens em AMBOS
    let fullstack: HashSet<&str> = frontend.intersection(&backend).copied().collect();
    println!("Fullstack: {:?}", fullstack); // {"Rust", "TypeScript"}

    // Diferença: apenas frontend (não estão em backend)
    let so_frontend: HashSet<&str> = frontend.difference(&backend).copied().collect();
    println!("Só frontend: {:?}", so_frontend); // {"JavaScript", "HTML", "CSS"}

    // Diferença simétrica: em um OU outro, mas não em ambos
    let exclusivas: HashSet<&str> = frontend.symmetric_difference(&backend).copied().collect();
    println!("Exclusivas: {:?}", exclusivas);

    // Usando operadores (requer coletar em novos HashSets)
    let uniao = &frontend | &backend;       // união
    let inter = &frontend & &backend;       // interseção
    let diff = &frontend - &backend;        // diferença
    let sym_diff = &frontend ^ &backend;    // diferença simétrica

    println!("\nCom operadores:");
    println!("  |  união: {:?}", uniao);
    println!("  &  interseção: {:?}", inter);
    println!("  -  diferença: {:?}", diff);
    println!("  ^  simétrica: {:?}", sym_diff);
}

3. Subconjuntos e Disjunção

use std::collections::HashSet;

fn main() {
    let animais: HashSet<&str> = HashSet::from([
        "gato", "cachorro", "pássaro", "peixe", "hamster",
    ]);

    let domesticos: HashSet<&str> = HashSet::from([
        "gato", "cachorro",
    ]);

    let selvagens: HashSet<&str> = HashSet::from([
        "leão", "tigre", "elefante",
    ]);

    // Subconjunto
    println!("domésticos ⊆ animais? {}", domesticos.is_subset(&animais));
    // true

    // Superconjunto
    println!("animais ⊇ domésticos? {}", animais.is_superset(&domesticos));
    // true

    // Disjuntos (sem elementos em comum)
    println!("domésticos ∩ selvagens = ∅? {}", domesticos.is_disjoint(&selvagens));
    // true

    println!("animais ∩ domésticos = ∅? {}", animais.is_disjoint(&domesticos));
    // false
}

4. Removendo Duplicatas de um Vetor

use std::collections::HashSet;

fn main() {
    let emails = vec![
        "ana@email.com",
        "bruno@email.com",
        "ana@email.com",     // duplicata
        "carla@email.com",
        "bruno@email.com",   // duplicata
        "diana@email.com",
    ];

    // Abordagem 1: converter para HashSet (perde a ordem)
    let unicos: HashSet<&str> = emails.iter().copied().collect();
    println!("Únicos (sem ordem): {:?}", unicos);

    // Abordagem 2: manter a ordem original (usar HashSet como auxiliar)
    let mut vistos = HashSet::new();
    let sem_duplicatas: Vec<&str> = emails
        .iter()
        .copied()
        .filter(|email| vistos.insert(*email))
        .collect();

    println!("Sem duplicatas (ordem mantida): {:?}", sem_duplicatas);
    // ["ana@email.com", "bruno@email.com", "carla@email.com", "diana@email.com"]
}

5. HashSet com Tipos Customizados

use std::collections::HashSet;

#[derive(Debug, PartialEq, Eq, Hash)]
struct Ponto {
    x: i32,
    y: i32,
}

fn main() {
    let mut pontos: HashSet<Ponto> = HashSet::new();

    pontos.insert(Ponto { x: 0, y: 0 });
    pontos.insert(Ponto { x: 1, y: 2 });
    pontos.insert(Ponto { x: 0, y: 0 }); // duplicata, não será inserido

    println!("Total de pontos: {}", pontos.len()); // 2

    let busca = Ponto { x: 1, y: 2 };
    println!("Contém (1,2)? {}", pontos.contains(&busca)); // true

    // retain: manter apenas pontos com x positivo
    pontos.retain(|p| p.x > 0);
    println!("Após filtro: {:?}", pontos);
}

Características de Desempenho

Operação	Complexidade
`insert`	O(1) amortizado
`remove`	O(1) amortizado
`contains`	O(1) amortizado
`union`	O(n + m)
`intersection`	O(min(n, m))
`difference`	O(n)
`symmetric_difference`	O(n + m)
`is_subset`	O(n)
`is_disjoint`	O(min(n, m))

Pior caso: O(n) para operações individuais — ocorre quando muitas chaves colidem no hash. Na prática, o hasher padrão (SipHash) distribui bem as chaves.

Memória: O HashSet aloca uma tabela hash, então usa mais memória que um Vec com os mesmos elementos. Use with_capacity() quando souber o tamanho aproximado.

HashSet vs BTreeSet

Critério	HashSet	BTreeSet
Ordem de iteração	Não determinística	Crescente
Requisito do tipo	`Eq + Hash`	`Ord`
Busca/Inserção/Remoção	O(1) amortizado	O(log n)
Range queries	Não	Sim
Operações de conjunto	Sim	Sim
Uso de memória	Maior	Menor

Veja Também

HashMap em Rust — mapa chave-valor baseado na mesma tabela hash
BTreeSet: Conjunto Ordenado — conjunto com iteração em ordem
BTreeMap: Mapa Ordenado — mapa com chaves ordenadas
Como Usar HashMap — receita prática com HashMap
Filtrar Vetor em Rust — técnicas de filtragem de coleções
Traits e Generics — entendendo Eq, Hash e Ord