Tabela Hash do Zero em Rust

A Tabela Hash (Hash Table) é uma das estruturas de dados mais utilizadas na programação, oferecendo acesso em tempo O(1) amortizado para inserção, busca e remoção. Ela funciona mapeando chaves para posições em um array por meio de uma função hash, permitindo acesso quase direto ao dado desejado.

Rust oferece o HashMap na biblioteca padrão, mas entender como uma tabela hash funciona internamente é essencial para tomar decisões sobre qual estratégia de hash e tratamento de colisões usar. Nesta página, construiremos uma tabela hash completa do zero, explorando encadeamento separado (chaining) e endereçamento aberto (open addressing).

Como Funciona

A tabela hash opera em três etapas: (1) calcular o hash da chave, (2) mapear o hash para um índice do array (geralmente hash % capacidade), e (3) tratar colisões quando duas chaves mapeiam para o mesmo índice.

Função hash: h(chave) = hash(chave) % capacidade

Inserir: ("rust", 10), ("python", 20), ("java", 30), ("go", 40)
Capacidade inicial: 8

Índice = hash(chave) % 8

Índice:  0     1     2     3     4     5     6     7
       +-----+-----+-----+-----+-----+-----+-----+-----+
       |     |     |     |     |     |     |     |     |
       +-----+-----+-----+-----+-----+-----+-----+-----+

Após inserções (supondo distribuição dos hashes):

Índice:  0     1     2     3     4     5     6     7
       +-----+-----+-----+-----+-----+-----+-----+-----+
       |     |"go" |     |"rust"|"java"|     |"py" |     |
       | --- | 40  | --- | 10  | 30  | --- | 20  | --- |
       +-----+-----+-----+-----+-----+-----+-----+-----+

=== Colisão (Encadeamento Separado / Chaining) ===

Se "c++" também mapeia para o índice 3:

Índice:  0     1     2       3           4     5     6     7
       +-----+-----+-----+---------+-----+-----+-----+-----+
       |     |"go" |     | "rust" →|"java"|     |"py" |     |
       | --- | 40  | --- | "c++"  | 30  | --- | 20  | --- |
       +-----+-----+-----+---------+-----+-----+-----+-----+

Cada bucket contém uma lista encadeada:
  Índice 3: ["rust":10] → ["c++":50] → null

=== Colisão (Endereçamento Aberto / Linear Probing) ===

Se "c++" mapeia para o índice 3 (ocupado), tenta 4, 5, ...

Índice:  0     1     2     3     4     5     6     7
       +-----+-----+-----+-----+-----+-----+-----+-----+
       |     |"go" |     |"rust"|"java"|"c++"|"py" |     |
       | --- | 40  | --- | 10  | 30  | 50  | 20  | --- |
       +-----+-----+-----+-----+-----+-----+-----+-----+
                                        ↑
                              Colocado na próxima posição livre (5)

O fator de carga (load factor) determina quando redimensionar:

Fator de carga = número_de_elementos / capacidade

Se fator_de_carga > 0.75 → redimensionar (dobrar capacidade e reinserir tudo)

Exemplo: 6 elementos em array de 8 → fator = 0.75 → redimensionar para 16

Complexidade

Operação	Caso Médio	Pior Caso	Espaço
Inserção	O(1)*	O(n)	O(n)
Busca	O(1)*	O(n)	O(1)
Remoção	O(1)*	O(n)	O(1)
Redimensionamento	O(n)	O(n)	O(n)

*Amortizado. O pior caso O(n) ocorre quando todas as chaves colidem no mesmo bucket (função hash ruim) ou durante redimensionamento.

O(1) amortizado: com uma boa função hash e fator de carga controlado, as operações são praticamente constantes.
Espaço O(n): proporcional ao número de elementos armazenados, mais o overhead dos buckets vazios.

Implementação em Rust

Tabela Hash com Encadeamento Separado

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

/// Par chave-valor armazenado na tabela.
#[derive(Debug, Clone)]
struct Entrada<K: Hash + Eq + Clone, V: Clone> {
    chave: K,
    valor: V,
}

/// Tabela hash com encadeamento separado (chaining).
/// Cada bucket é um Vec de entradas (simula lista encadeada).
struct TabelaHash<K: Hash + Eq + Clone, V: Clone> {
    buckets: Vec<Vec<Entrada<K, V>>>,
    tamanho: usize,
    capacidade: usize,
}

impl<K: Hash + Eq + Clone, V: Clone> TabelaHash<K, V> {
    /// Cria uma tabela hash com capacidade inicial.
    fn nova(capacidade: usize) -> Self {
        let cap = capacidade.max(4); // mínimo de 4 buckets
        TabelaHash {
            buckets: (0..cap).map(|_| Vec::new()).collect(),
            tamanho: 0,
            capacidade: cap,
        }
    }

    /// Calcula o índice do bucket para uma chave.
    fn indice(&self, chave: &K) -> usize {
        let mut hasher = DefaultHasher::new();
        chave.hash(&mut hasher);
        (hasher.finish() as usize) % self.capacidade
    }

    /// Fator de carga atual.
    fn fator_carga(&self) -> f64 {
        self.tamanho as f64 / self.capacidade as f64
    }

    /// Insere um par chave-valor. Atualiza se a chave já existir.
    fn inserir(&mut self, chave: K, valor: V) {
        // Redimensiona se fator de carga > 0.75
        if self.fator_carga() > 0.75 {
            self.redimensionar();
        }

        let idx = self.indice(&chave);

        // Verifica se a chave já existe no bucket
        for entrada in self.buckets[idx].iter_mut() {
            if entrada.chave == chave {
                entrada.valor = valor;
                return; // Atualiza o valor existente
            }
        }

        // Chave nova — adiciona ao bucket
        self.buckets[idx].push(Entrada { chave, valor });
        self.tamanho += 1;
    }

    /// Busca o valor associado a uma chave.
    fn buscar(&self, chave: &K) -> Option<&V> {
        let idx = self.indice(chave);
        for entrada in &self.buckets[idx] {
            if entrada.chave == *chave {
                return Some(&entrada.valor);
            }
        }
        None
    }

    /// Remove uma chave e retorna o valor associado, se existir.
    fn remover(&mut self, chave: &K) -> Option<V> {
        let idx = self.indice(chave);
        if let Some(pos) = self.buckets[idx].iter().position(|e| e.chave == *chave) {
            self.tamanho -= 1;
            Some(self.buckets[idx].remove(pos).valor)
        } else {
            None
        }
    }

    /// Verifica se a chave existe na tabela.
    fn contem(&self, chave: &K) -> bool {
        self.buscar(chave).is_some()
    }

    /// Número de elementos armazenados.
    fn len(&self) -> usize {
        self.tamanho
    }

    /// Redimensiona a tabela (dobra a capacidade) e reinsere todos os elementos.
    fn redimensionar(&mut self) {
        let nova_cap = self.capacidade * 2;
        let mut nova_tabela = TabelaHash::nova(nova_cap);

        for bucket in &self.buckets {
            for entrada in bucket {
                nova_tabela.inserir(entrada.chave.clone(), entrada.valor.clone());
            }
        }

        self.buckets = nova_tabela.buckets;
        self.capacidade = nova_cap;
    }
}

fn main() {
    let mut tabela: TabelaHash<String, i32> = TabelaHash::nova(8);

    // Inserções
    tabela.inserir("rust".to_string(), 2015);
    tabela.inserir("python".to_string(), 1991);
    tabela.inserir("java".to_string(), 1995);
    tabela.inserir("go".to_string(), 2009);
    tabela.inserir("c".to_string(), 1972);

    println!("Tamanho: {}", tabela.len());
    println!("Fator de carga: {:.2}", tabela.fator_carga());

    // Buscas
    println!("\nBuscar 'rust': {:?}", tabela.buscar(&"rust".to_string()));
    println!("Buscar 'ruby': {:?}", tabela.buscar(&"ruby".to_string()));
    println!("Contém 'java': {}", tabela.contem(&"java".to_string()));

    // Atualização
    tabela.inserir("rust".to_string(), 2025);
    println!("\nApós atualizar 'rust': {:?}", tabela.buscar(&"rust".to_string()));

    // Remoção
    let removido = tabela.remover(&"go".to_string());
    println!("\nRemovido 'go': {:?}", removido);
    println!("Tamanho após remoção: {}", tabela.len());
}

Exemplo de Execução

Tamanho: 5
Fator de carga: 0.62

Buscar 'rust': Some(2015)
Buscar 'ruby': None
Contém 'java': true

Após atualizar 'rust': Some(2025)

Removido 'go': Some(2009)
Tamanho após remoção: 4

Variações e Otimizações

1. Endereçamento Aberto com Linear Probing

Em vez de listas em cada bucket, armazenamos diretamente no array e buscamos a próxima posição livre em caso de colisão.

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

#[derive(Debug, Clone)]
enum Slot<K: Hash + Eq + Clone, V: Clone> {
    Vazio,
    Ocupado(K, V),
    Removido, // Marcador para não quebrar cadeias de probing
}

struct TabelaAberta<K: Hash + Eq + Clone, V: Clone> {
    slots: Vec<Slot<K, V>>,
    tamanho: usize,
    capacidade: usize,
}

impl<K: Hash + Eq + Clone, V: Clone> TabelaAberta<K, V> {
    fn nova(capacidade: usize) -> Self {
        let cap = capacidade.max(4);
        TabelaAberta {
            slots: (0..cap).map(|_| Slot::Vazio).collect(),
            tamanho: 0,
            capacidade: cap,
        }
    }

    fn hash_indice(&self, chave: &K) -> usize {
        let mut hasher = DefaultHasher::new();
        chave.hash(&mut hasher);
        (hasher.finish() as usize) % self.capacidade
    }

    fn inserir(&mut self, chave: K, valor: V) {
        if (self.tamanho + 1) as f64 / self.capacidade as f64 > 0.7 {
            self.redimensionar();
        }

        let mut idx = self.hash_indice(&chave);
        loop {
            match &self.slots[idx] {
                Slot::Vazio | Slot::Removido => {
                    self.slots[idx] = Slot::Ocupado(chave, valor);
                    self.tamanho += 1;
                    return;
                }
                Slot::Ocupado(k, _) if *k == chave => {
                    self.slots[idx] = Slot::Ocupado(chave, valor);
                    return; // Atualiza valor existente
                }
                _ => {
                    idx = (idx + 1) % self.capacidade; // linear probing
                }
            }
        }
    }

    fn buscar(&self, chave: &K) -> Option<&V> {
        let mut idx = self.hash_indice(chave);
        let inicio = idx;
        loop {
            match &self.slots[idx] {
                Slot::Vazio => return None,
                Slot::Ocupado(k, v) if *k == *chave => return Some(v),
                _ => {
                    idx = (idx + 1) % self.capacidade;
                    if idx == inicio {
                        return None; // Tabela cheia, deu volta completa
                    }
                }
            }
        }
    }

    fn remover(&mut self, chave: &K) -> Option<V> {
        let mut idx = self.hash_indice(chave);
        let inicio = idx;
        loop {
            match &self.slots[idx] {
                Slot::Vazio => return None,
                Slot::Ocupado(k, _) if *k == *chave => {
                    let valor = if let Slot::Ocupado(_, v) = std::mem::replace(&mut self.slots[idx], Slot::Removido) {
                        v
                    } else {
                        unreachable!()
                    };
                    self.tamanho -= 1;
                    return Some(valor);
                }
                _ => {
                    idx = (idx + 1) % self.capacidade;
                    if idx == inicio {
                        return None;
                    }
                }
            }
        }
    }

    fn redimensionar(&mut self) {
        let nova_cap = self.capacidade * 2;
        let mut nova = TabelaAberta::nova(nova_cap);
        for slot in &self.slots {
            if let Slot::Ocupado(k, v) = slot {
                nova.inserir(k.clone(), v.clone());
            }
        }
        self.slots = nova.slots;
        self.capacidade = nova_cap;
    }
}

fn main() {
    let mut tabela = TabelaAberta::nova(8);

    tabela.inserir("alfa", 1);
    tabela.inserir("beta", 2);
    tabela.inserir("gama", 3);
    tabela.inserir("delta", 4);

    println!("Buscar 'beta': {:?}", tabela.buscar(&"beta"));
    println!("Buscar 'omega': {:?}", tabela.buscar(&"omega"));

    tabela.remover(&"beta");
    println!("Após remover 'beta': {:?}", tabela.buscar(&"beta"));
    // 'gama' ainda é encontrada mesmo após remoção de 'beta' (slot Removido preserva cadeia)
    println!("'gama' ainda acessível: {:?}", tabela.buscar(&"gama"));
}

2. Função Hash Personalizada (FNV-1a)

/// Implementação simples do hash FNV-1a para strings.
/// Boa distribuição e rápida para chaves pequenas.
fn fnv1a_hash(dados: &[u8]) -> u64 {
    let mut hash: u64 = 0xcbf29ce484222325; // FNV offset basis
    for &byte in dados {
        hash ^= byte as u64;
        hash = hash.wrapping_mul(0x100000001b3); // FNV prime
    }
    hash
}

fn main() {
    let palavras = ["rust", "python", "java", "go", "c++", "ruby"];
    let capacidade = 16;

    println!("Hash FNV-1a (mod {}):", capacidade);
    for palavra in &palavras {
        let h = fnv1a_hash(palavra.as_bytes());
        println!("  '{}' → hash={} → índice={}", palavra, h, h as usize % capacidade);
    }
}

Aplicações Práticas

Caches: tabelas hash são a base de sistemas de cache como memcached e Redis, onde o acesso rápido por chave é essencial.
Compiladores: tabelas de símbolos em compiladores usam hash tables para mapear nomes de variáveis a informações de tipo e escopo.
Contagem de frequência: contar a frequência de palavras em um texto ou caracteres em uma string.
Deduplicação: detectar duplicatas em conjuntos de dados massivos.
Roteamento de rede: tabelas de roteamento em switches de rede usam hashing para encaminhamento rápido de pacotes.
Bancos de dados: índices hash permitem busca O(1) para consultas de igualdade (WHERE id = X).

Comparação com Alternativas

Característica	Hash Table (chaining)	Hash Table (open addr.)	BST	Vec ordenado
Busca (médio)	O(1)	O(1)	O(log n)	O(log n)
Inserção (médio)	O(1)	O(1)	O(log n)	O(n)
Remoção (médio)	O(1)	O(1)	O(log n)	O(n)
Dados ordenados	Não	Não	Sim	Sim
Consulta de faixa	Não	Não	Sim	Sim
Uso de memória	Maior (ponteiros)	Compacto	Ponteiros	Contíguo
Localidade de cache	Ruim	Boa	Ruim	Excelente
Pior caso	O(n)	O(n)	O(n)	O(log n)

Use tabelas hash quando a ordem dos elementos não importa e você precisa de acesso O(1). Use árvores quando precisa de dados ordenados ou consultas por faixa.

Exercícios Práticos

Contador de palavras: Usando a tabela hash implementada, construa um contador de frequência de palavras para um texto. Leia uma string, divida em palavras e conte quantas vezes cada uma aparece.
Two Sum: Dado um vetor de inteiros e um alvo, encontre dois índices cujos valores somam o alvo. Use uma tabela hash para resolver em O(n). Exemplo: [2, 7, 11, 15], alvo 9 -> [0, 1].
Quadratic probing: Implemente uma variante da tabela com endereçamento aberto que usa probing quadrático em vez de linear: idx = (hash + i^2) % capacidade. Compare o clustering com linear probing.
Robin Hood hashing: Implemente a técnica Robin Hood onde, durante inserção com probing, se o elemento sendo inserido tem um deslocamento (distância do índice ideal) maior que o elemento no slot atual, eles trocam de posição. Isso reduz a variância no tempo de busca.

Veja Também

HashMap — Mapa Associativo — implementação otimizada na std do Rust
Hash Trait — como Rust calcula hashes
Vec — Vetores Dinâmicos — base da implementação dos buckets
Option — Valores Opcionais — tratamento de valores ausentes em buscas
Árvore Binária de Busca em Rust — alternativa ordenada