Tabela hash (HashMap): como funciona e por que é tão eficiente

A tabela hash (ou hashmap, ou dicionário) é possivelmente a estrutura de dados mais utilizada em programação real depois dos arrays. É a estrutura por trás dos dicionários do Python, dos objetos JavaScript, dos HashMap do Java, e dos unordered_map do C++. O motivo da popularidade: busca, inserção e remoção em O(1) em média — tempo constante, independente de quantos elementos há na tabela. Entender como tabelas hash funcionam por baixo não é apenas satisfatório intelectualmente — é necessário para entender quando elas são a estrutura certa e quando podem falhar.

O problema: indexação por chave arbitrária

Arrays dão acesso O(1) por índice numérico. Mas e se você quiser acessar um valor por uma chave string, como "nome" ou "CPF"? A ideia da tabela hash: converta a chave num número (o hash) e use esse número como índice de um array interno.

Função hash: transformando chaves em índices

def hash_simples(chave, tamanho_tabela):
    """
    Função hash ingênua — soma os valores ASCII dos caracteres
    e usa o módulo para garantir que o índice cabe na tabela.
    """
    total = sum(ord(c) for c in str(chave))
    return total % tamanho_tabela

print(hash_simples("nome", 10))    # Algum índice entre 0 e 9
print(hash_simples("email", 10))   # Índice diferente

Funções hash reais (como a usada pelo Python internamente) são muito mais sofisticadas para minimizar colisões e distribuir os valores uniformemente. O Python usa uma combinação de operações bitwise e valores aleatórios por execução (para segurança contra ataques de DoS por colisão deliberada).

Colisões: quando duas chaves mapeiam para o mesmo índice

Colisões são inevitáveis — duas chaves diferentes podem produzir o mesmo hash (especialmente com tabelas pequenas). A estratégia mais comum para resolver colisões é o encadeamento (chaining): cada posição da tabela armazena uma lista encadeada de todos os pares chave-valor que mapearam para aquele índice.

class TabelaHash:
    def __init__(self, tamanho=10):
        self.tamanho = tamanho
        self.buckets = [[] for _ in range(tamanho)]

    def _hash(self, chave):
        return hash(chave) % self.tamanho

    def inserir(self, chave, valor):
        idx = self._hash(chave)
        for item in self.buckets[idx]:
            if item[0] == chave:
                item[1] = valor  # Atualiza se chave já existe
                return
        self.buckets[idx].append([chave, valor])

    def buscar(self, chave):
        idx = self._hash(chave)
        for item in self.buckets[idx]:
            if item[0] == chave:
                return item[1]
        return None

tabela = TabelaHash()
tabela.inserir("nome", "Ana")
tabela.inserir("cidade", "São Paulo")
print(tabela.buscar("nome"))    # Ana
print(tabela.buscar("cidade"))  # São Paulo

Fator de carga e rehashing

Quando a tabela fica muito cheia (fator de carga = n_elementos / tamanho_tabela > 0.7–0.8), colisões se tornam frequentes e a performance degrada. A solução: rehashing — criar uma tabela maior e reinserir todos os elementos. As implementações nativas fazem isso automaticamente — o dicionário do Python dobra de tamanho quando necessário, garantindo O(1) amortizado.

Quando usar tabela hash

Use hashmap/dicionário quando: precisa de busca, inserção ou remoção por chave em O(1), quer contar frequência de elementos (contador[elemento] += 1), precisa verificar se um elemento já foi visto antes (detecção de duplicatas), ou quer mapear um tipo de dado para outro (chave → valor). É a solução para uma enorme classe de problemas de otimização: sempre que um algoritmo O(n²) usa dois loops para comparar elementos, pergunte-se se um hashmap eliminaria o loop interno trazendo para O(n).