---
title: "Tabela Hash do Zero em Rust"
url: "https://rustlang.com.br/algoritmos/hash-table/"
markdown_url: "https://rustlang.com.br/algoritmos/hash-table.MD"
description: "Construa uma tabela hash do zero em Rust com tratamento de colisões, rehashing e análise Big-O. Código completo e diagramas visuais."
date: "2026-02-24"
author: "Equipe Rust Brasil"
---

# Tabela Hash do Zero em Rust

Construa uma tabela hash do zero em Rust com tratamento de colisões, rehashing e análise Big-O. Código completo e diagramas visuais.


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.

```text
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:

```text
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

```rust
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

```text
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.

```rust
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)

```rust
/// 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](/algoritmos/binary-search-tree/) | [Vec](/stdlib/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

1. **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.

2. **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]`.

3. **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.

4. **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](/stdlib/hashmap/) — implementação otimizada na std do Rust
- [Hash Trait](/stdlib/hash-trait/) — como Rust calcula hashes
- [Vec — Vetores Dinâmicos](/stdlib/vec/) — base da implementação dos buckets
- [Option — Valores Opcionais](/stdlib/option/) — tratamento de valores ausentes em buscas
- [Árvore Binária de Busca em Rust](/algoritmos/binary-search-tree/) — alternativa ordenada