HashSet în Rust

use std::collections::HashSet;

let mut s: HashSet<T> = HashSet::new();
let s = HashSet::from([a, b, c]);
let s: HashSet<T> = iterator.collect();
pub fn len(&self) -> usize

Ce face HashSet

HashSet<T> este ca un HashMap care are doar chei, fără valori. Fiecare element apare cel mult o dată: dacă adaugi din nou o valoare existentă, nu se schimbă nimic. Verificarea „există?” (contains) este aproape instantă, oricât de mare e mulțimea.

Se folosește pentru eliminarea duplicatelor, pentru „am mai văzut asta?” și pentru operații cu mulțimi: reuniune, intersecție, diferență. HashSet::new() creează o mulțime goală, HashSet::from([..]) sau collect() una cu elemente, iar len() spune câte elemente distincte are.

Elementele trebuie să implementeze Eq și Hash (numere întregi, texte, char, tupluri, structuri cu #[derive(PartialEq, Eq, Hash)]). Ca la HashMap, ordinea elementelor este aleatorie; pentru o mulțime mereu sortată folosește BTreeSet.

Ce returnează

HashSet::new() returnează o mulțime goală; len() numărul de elemente distincte.

Exemple

Exemplul 1: Vizitatori unici

use std::collections::HashSet;

fn main() {
    let vizite = ["ana", "mihai", "ana", "ioana", "mihai", "ana"];
    let mut unici = HashSet::new();
    for v in vizite {
        unici.insert(v);
    }
    println!("{} vizite, {} vizitatori unici", vizite.len(), unici.len());

    let mut sortati: Vec<_> = unici.into_iter().collect();
    sortati.sort();
    println!("{:?}", sortati);
}

Rezultat

6 vizite, 3 vizitatori unici
["ana", "ioana", "mihai"]

Exemplul 2: Are duplicate? Primul duplicat

insert returnează false când valoarea exista deja; all se oprește la primul false.

use std::collections::HashSet;

fn are_duplicate(v: &[i32]) -> bool {
    let mut vazute = HashSet::new();
    !v.iter().all(|x| vazute.insert(x))
}

fn main() {
    println!("{}", are_duplicate(&[1, 2, 3, 4]));
    println!("{}", are_duplicate(&[4, 8, 15, 8, 42]));

    let numere = [4, 8, 15, 16, 8, 42, 4];
    let mut vazute = HashSet::new();
    if let Some(d) = numere.iter().find(|&&n| !vazute.insert(n)) {
        println!("primul duplicat: {d}");
    }
}

Rezultat

false
true
primul duplicat: 8

Exemplul 3: Structuri proprii într-o mulțime

Cu #[derive(PartialEq, Eq, Hash)], două puncte cu aceleași coordonate sunt considerate același element.

use std::collections::HashSet;

#[derive(PartialEq, Eq, Hash, Clone, Copy)]
struct Punct {
    x: i32,
    y: i32,
}

fn main() {
    let traseu = [Punct { x: 0, y: 0 }, Punct { x: 1, y: 0 }, Punct { x: 1, y: 1 }, Punct { x: 0, y: 0 }];
    let vizitate: HashSet<Punct> = traseu.into_iter().collect();
    println!("{} pași, {} puncte distincte", traseu.len(), vizitate.len());
    let p = Punct { x: 1, y: 1 };
    println!("am trecut prin ({}, {})? {}", p.x, p.y, vizitate.contains(&p));
}

Rezultat

4 pași, 3 puncte distincte
am trecut prin (1, 1)? true

Greșeli frecvente

• Te bazezi pe ordinea elementelor la afișare: se schimbă la fiecare rulare. Sortează sau folosește BTreeSet.
• Pui f64 într-un HashSet: the trait bound `f64: Hash` is not satisfied. Folosește întregi (de exemplu prețuri în bani) sau sortează un Vec și aplică dedup.
• Structură proprie fără derive: the trait bound `Punct: Hash` is not satisfied. Adaugă #[derive(PartialEq, Eq, Hash)].

Comenzi înrudite

• HashSet::insert: insert adaugă o valoare (true dacă era nouă), contains verifică dacă există, remove o scoate (true dacă exista).
• HashSet::union: Operațiile cu mulțimi: reuniune (în oricare), intersecție (în ambele), diferență (doar în prima), diferență simetrică (în exact una).
• HashSet::iter: Parcurge elementele mulțimii prin referință, într-o ordine aleatorie; pentru afișare stabilă, colectează și sortează.
• BTreeSet: Mulțime cu elementele mereu sortate: fără duplicate, ca HashSet, dar parcurgerea este în ordine crescătoare.
• HashMap: Dicționarul din Rust: asociază fiecărei chei o valoare și o găsește foarte repede după cheie. Ordinea nu este garantată.
• Vec::dedup: Șterge elementele egale aflate unul după altul; dedup_by_key compară după o cheie calculată din fiecare element.