Hash Trait em Rust | Rust Brasil

O que é o Trait Hash?

O trait Hash permite que um valor seja transformado em um número inteiro (hash) que o identifica de forma eficiente. Esse hash é usado por estruturas de dados como HashMap e HashSet para armazenar e buscar elementos em tempo O(1) na média.

Quando você insere uma chave em um HashMap, o Rust:

Calcula o hash da chave usando Hash
Usa o hash para determinar em qual bucket armazenar o par chave-valor
Na busca, recalcula o hash para encontrar o bucket correto
Usa Eq para confirmar que encontrou a chave exata (tratando colisões)

Por isso, Hash e Eq trabalham juntos com um contrato que nunca deve ser violado.

Definição do Trait

// std::hash::Hash
pub trait Hash {
    fn hash<H: Hasher>(&self, state: &mut H);

    // Implementação padrão baseada em hash()
    fn hash_slice<H: Hasher>(data: &[Self], state: &mut H)
    where
        Self: Sized,
    { ... }
}

// std::hash::Hasher (simplificado)
pub trait Hasher {
    fn finish(&self) -> u64;
    fn write(&mut self, bytes: &[u8]);

    // Métodos auxiliares com implementação padrão
    fn write_u8(&mut self, i: u8) { ... }
    fn write_u16(&mut self, i: u16) { ... }
    fn write_u32(&mut self, i: u32) { ... }
    fn write_u64(&mut self, i: u64) { ... }
    fn write_usize(&mut self, i: usize) { ... }
    fn write_i8(&mut self, i: i8) { ... }
    fn write_i16(&mut self, i: i16) { ... }
    fn write_i32(&mut self, i: i32) { ... }
    fn write_i64(&mut self, i: i64) { ... }
    fn write_isize(&mut self, i: isize) { ... }
    // ...
}

O método hash recebe um Hasher mutável e alimenta-o com os dados do valor. O hasher acumula esses dados e produz um u64 final via finish().

O Contrato Hash + Eq

Este é o contrato mais importante a respeitar:

Se a == b (via Eq), então hash(a) == hash(b).

A violação desse contrato corrompe HashMap e HashSet, causando comportamentos imprevisíveis (chaves que “desaparecem”, buscas que falham).

Note que o inverso não é obrigatório: dois valores diferentes podem ter o mesmo hash (colisão). Isso é normal e esperado.

use std::hash::{Hash, Hasher};
use std::collections::hash_map::DefaultHasher;

fn calcular_hash<T: Hash>(valor: &T) -> u64 {
    let mut hasher = DefaultHasher::new();
    valor.hash(&mut hasher);
    hasher.finish()
}

fn main() {
    let a = "olá";
    let b = "olá";
    let c = "mundo";

    // a == b, então hash(a) == hash(b)
    assert_eq!(a, b);
    assert_eq!(calcular_hash(&a), calcular_hash(&b));

    // a != c, hashes provavelmente diferentes (mas não garantido)
    assert_ne!(a, c);
    println!("hash('olá')   = {}", calcular_hash(&a));
    println!("hash('mundo') = {}", calcular_hash(&c));
}

Como Implementar: derive vs impl manual

Hash com #[derive]

A forma mais comum e recomendada:

#[derive(Debug, Hash, PartialEq, Eq)]
struct Produto {
    codigo: String,
    nome: String,
    categoria: u32,
}

fn main() {
    use std::collections::HashSet;

    let mut catalogo = HashSet::new();

    catalogo.insert(Produto {
        codigo: String::from("PRD-001"),
        nome: String::from("Teclado"),
        categoria: 1,
    });

    catalogo.insert(Produto {
        codigo: String::from("PRD-002"),
        nome: String::from("Mouse"),
        categoria: 1,
    });

    println!("Produtos no catálogo: {}", catalogo.len()); // 2
}

Quando derivado, Hash alimenta o hasher com cada campo na ordem de declaração. Para funcionar, todos os campos devem implementar Hash.

Hash com implementação manual

Quando você quer que apenas alguns campos participem do hash (por exemplo, uma chave natural):

use std::hash::{Hash, Hasher};

#[derive(Debug)]
struct Funcionario {
    cpf: String,      // Identificador único
    nome: String,
    salario: f64,     // f64 NÃO implementa Hash!
    departamento: String,
}

// Hash e Eq baseados apenas no CPF
impl Hash for Funcionario {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.cpf.hash(state);
    }
}

impl PartialEq for Funcionario {
    fn eq(&self, other: &Self) -> bool {
        self.cpf == other.cpf
    }
}

impl Eq for Funcionario {}

fn main() {
    use std::collections::HashMap;

    let mut equipe = HashMap::new();

    equipe.insert(
        Funcionario {
            cpf: String::from("123.456.789-00"),
            nome: String::from("Ana"),
            salario: 8000.0,
            departamento: String::from("Engenharia"),
        },
        "Desenvolvedora Sênior",
    );

    // Busca pelo CPF — outros campos são irrelevantes para Hash/Eq
    let busca = Funcionario {
        cpf: String::from("123.456.789-00"),
        nome: String::new(),      // Irrelevante para busca
        salario: 0.0,
        departamento: String::new(),
    };

    if let Some(cargo) = equipe.get(&busca) {
        println!("Cargo: {}", cargo);
    }
}

Exemplos Práticos

Exemplo 1: HashMap com chave customizada

use std::collections::HashMap;

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

impl Coordenada {
    fn nova(x: i32, y: i32) -> Self {
        Coordenada { x, y }
    }
}

fn main() {
    let mut mapa: HashMap<Coordenada, String> = HashMap::new();

    mapa.insert(Coordenada::nova(0, 0), "Origem".into());
    mapa.insert(Coordenada::nova(1, 0), "Leste".into());
    mapa.insert(Coordenada::nova(0, 1), "Norte".into());
    mapa.insert(Coordenada::nova(-1, 0), "Oeste".into());

    let posicao = Coordenada::nova(0, 0);
    if let Some(nome) = mapa.get(&posicao) {
        println!("Posição (0,0): {}", nome); // Origem
    }

    // Iterar sobre todas as entradas
    for (coord, nome) in &mapa {
        println!("({}, {}) = {}", coord.x, coord.y, nome);
    }
}

Exemplo 2: HashSet para deduplicação

use std::collections::HashSet;

#[derive(Debug, Hash, PartialEq, Eq)]
struct Tag {
    nome: String,
}

impl Tag {
    fn nova(nome: impl Into<String>) -> Self {
        Tag { nome: nome.into().to_lowercase() }
    }
}

fn main() {
    let mut tags = HashSet::new();

    // Insere tags normalizadas
    tags.insert(Tag::nova("Rust"));
    tags.insert(Tag::nova("rust"));     // Duplicata! Não será inserida
    tags.insert(Tag::nova("RUST"));     // Duplicata!
    tags.insert(Tag::nova("programação"));
    tags.insert(Tag::nova("web"));

    println!("Tags únicas: {}", tags.len()); // 3

    // Verifica existência
    let busca = Tag::nova("rust");
    println!("Contém 'rust'? {}", tags.contains(&busca)); // true

    // Operações de conjunto
    let mut outras_tags = HashSet::new();
    outras_tags.insert(Tag::nova("rust"));
    outras_tags.insert(Tag::nova("linux"));
    outras_tags.insert(Tag::nova("web"));

    let comuns: HashSet<_> = tags.intersection(&outras_tags).collect();
    println!("Tags em comum: {}", comuns.len()); // 2 (rust, web)
}

Exemplo 3: Hash para enums complexas

use std::collections::HashMap;
use std::hash::{Hash, Hasher};

#[derive(Debug, Clone)]
enum Permissao {
    Ler,
    Escrever,
    Admin { nivel: u8 },
    Custom(String),
}

impl Hash for Permissao {
    fn hash<H: Hasher>(&self, state: &mut H) {
        // Hash o discriminante da variante primeiro
        std::mem::discriminant(self).hash(state);

        // Hash dos dados internos
        match self {
            Permissao::Ler => {}
            Permissao::Escrever => {}
            Permissao::Admin { nivel } => nivel.hash(state),
            Permissao::Custom(nome) => nome.hash(state),
        }
    }
}

impl PartialEq for Permissao {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Permissao::Ler, Permissao::Ler) => true,
            (Permissao::Escrever, Permissao::Escrever) => true,
            (Permissao::Admin { nivel: a }, Permissao::Admin { nivel: b }) => a == b,
            (Permissao::Custom(a), Permissao::Custom(b)) => a == b,
            _ => false,
        }
    }
}

impl Eq for Permissao {}

fn main() {
    let mut permissoes: HashMap<Permissao, Vec<String>> = HashMap::new();

    permissoes
        .entry(Permissao::Ler)
        .or_default()
        .push("Ana".into());

    permissoes
        .entry(Permissao::Ler)
        .or_default()
        .push("Bruno".into());

    permissoes
        .entry(Permissao::Admin { nivel: 1 })
        .or_default()
        .push("Carlos".into());

    for (perm, usuarios) in &permissoes {
        println!("{:?}: {:?}", perm, usuarios);
    }
}

Exemplo 4: Usando um Hasher alternativo

use std::collections::HashMap;
use std::hash::{BuildHasherDefault, Hasher};

// Hasher simples (NÃO use em produção — apenas para demonstração)
#[derive(Default)]
struct HasherSimples {
    hash: u64,
}

impl Hasher for HasherSimples {
    fn finish(&self) -> u64 {
        self.hash
    }

    fn write(&mut self, bytes: &[u8]) {
        for &byte in bytes {
            self.hash = self.hash.wrapping_mul(31).wrapping_add(byte as u64);
        }
    }
}

type BuildHasherSimples = BuildHasherDefault<HasherSimples>;

fn main() {
    // HashMap com hasher customizado
    let mut mapa: HashMap<String, i32, BuildHasherSimples> =
        HashMap::with_hasher(BuildHasherSimples::default());

    mapa.insert("um".into(), 1);
    mapa.insert("dois".into(), 2);
    mapa.insert("três".into(), 3);

    println!("{:?}", mapa);

    // Na prática, use crates como `ahash` ou `rustc-hash`
    // para hashers mais rápidos que o padrão (SipHash)
}

Exemplo 5: Por que f64 não implementa Hash

use std::collections::HashMap;

// f64 não implementa Hash nem Eq por causa de NaN
// NaN != NaN viola o contrato de Eq
// Duas representações de 0.0 (+0.0 e -0.0) são == mas têm bits diferentes

// Solução: wrapper que trata esses casos
#[derive(Debug, Clone, Copy)]
struct FloatOrdenado(f64);

impl FloatOrdenado {
    fn new(v: f64) -> Option<Self> {
        if v.is_nan() {
            None  // Rejeita NaN
        } else {
            Some(FloatOrdenado(v))
        }
    }

    fn to_bits_normalizado(&self) -> u64 {
        if self.0 == 0.0 {
            0u64  // Normaliza -0.0 e +0.0 para o mesmo valor
        } else {
            self.0.to_bits()
        }
    }
}

impl std::hash::Hash for FloatOrdenado {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.to_bits_normalizado().hash(state);
    }
}

impl PartialEq for FloatOrdenado {
    fn eq(&self, other: &Self) -> bool {
        self.to_bits_normalizado() == other.to_bits_normalizado()
    }
}

impl Eq for FloatOrdenado {}

fn main() {
    let mut contagem: HashMap<FloatOrdenado, u32> = HashMap::new();

    let temperaturas = [36.5, 37.0, 36.5, 38.0, 37.0, 36.5];

    for &temp in &temperaturas {
        if let Some(chave) = FloatOrdenado::new(temp) {
            *contagem.entry(chave).or_insert(0) += 1;
        }
    }

    for (temp, qtd) in &contagem {
        println!("{:.1}°C apareceu {} vez(es)", temp.0, qtd);
    }
}

Padrões e Boas Práticas

Derive Hash junto com PartialEq e Eq: Sempre que derivar Hash, derive os outros dois. O contrato exige consistência entre eles.
Hash e Eq devem usar os mesmos campos: Se PartialEq compara apenas o campo id, então Hash deve usar apenas o campo id. Nunca inclua campos em Hash que não participam de Eq.
Não use f64 como chave de HashMap: Floats não implementam Hash nem Eq por boas razões. Use um wrapper normalizado ou converta para inteiro.
std::mem::discriminant para enums: Ao implementar Hash manualmente para enums, use discriminant() para incluir a variante no hash.
O hasher padrão é SipHash: Rust usa SipHash-1-3, que é resistente a HashDoS. Para performance máxima (quando segurança não é preocupação), considere crates como ahash ou rustc-hash.
Ordem dos campos importa: O hash de (1, 2) deve ser diferente de (2, 1). O derive cuida disso automaticamente, mas em implementações manuais, alimente o hasher na mesma ordem consistente.
Hash é determinístico por execução: O hash do mesmo valor pode diferir entre execuções do programa (por causa da seed aleatória). Não persista hashes em disco.

Veja Também

Eq e Ord — o contrato Eq que Hash depende
AsRef e Borrow — Borrow mantém o contrato Hash+Eq
Default Trait — usado com or_default() em HashMap
Display e Debug — frequentemente derivados junto com Hash
HashMap — a principal estrutura que consome Hash
HashSet — conjunto baseado em Hash+Eq