Hash tables por dentro

Não procure — calcule o endereço

Imagine uma biblioteca onde, em vez de procurar um livro, existe uma regra: some os códigos das letras do título, divida por 1000, e o resto é a prateleira. Guardar um livro é instantâneo. Achar um livro também — não importa se a biblioteca tem mil ou dez milhões de livros. Isso é uma hash table.

O problema aparece quando dois títulos diferentes dão a mesma prateleira. Isso é uma colisão, e ela não é um bug nem um azar: é matemática inevitável. Você está mapeando infinitas chaves possíveis em um número finito de prateleiras. Pelo princípio da casa dos pombos, colisões vão acontecer. Toda a engenharia de uma hash table é sobre como lidar com elas de forma barata.

Colisões, sondagem e o fator de carga

Insira chaves e veja onde elas caem. Alterne entre encadeamento e endereçamento aberto para comparar os dois jeitos de resolver colisões, e acompanhe a barra de fator de carga até o ponto em que o rehash se torna necessário. Na segunda aba, veja por que o endereçamento aberto explode perto de α = 1.

A função hash

# Uma função hash transforma qualquer chave num número.
# Esse número, módulo o número de buckets, vira um índice de array.
#
#   "gato"  --hash-->  3.847.291.104  --% 8-->  bucket 0
#   "sol"   --hash-->  1.209.336.712  --% 8-->  bucket 0   ← colisão!
#
# Uma boa função hash precisa de três propriedades:
#   1. determinística — a mesma chave sempre dá o mesmo número
#   2. uniforme       — espalha bem, sem favorecer certos buckets
#   3. rápida         — é chamada em TODA operação da tabela

# djb2 — uma hash clássica, simples e surpreendentemente boa
def djb2(s):
    h = 5381
    for c in s:
        h = (h * 33 + ord(c)) & 0xFFFFFFFF   # mantém em 32 bits
    return h

djb2("gato") % 8    # → índice do bucket

# Note o que a hash NÃO precisa ser: reversível. Ninguém precisa
# recuperar "gato" a partir do número — a chave original fica
# guardada junto com o valor, para poder comparar em caso de colisão.

Resolvendo colisões: encadeamento

# SOLUÇÃO 1: encadeamento separado (separate chaining)
# Cada bucket guarda uma lista. Colisão = lista mais comprida.
class HashChaining:
    def __init__(self, cap=8):
        self.buckets = [[] for _ in range(cap)]
        self.cap = cap
        self.n = 0

    def put(self, k, v):
        b = self.buckets[hash(k) % self.cap]
        for par in b:
            if par[0] == k:              # chave já existe: atualiza
                par[1] = v; return
        b.append([k, v]); self.n += 1
        if self.n / self.cap > 0.75:   # fator de carga alto
            self._rehash()

    def get(self, k):
        for par in self.buckets[hash(k) % self.cap]:
            if par[0] == k: return par[1]
        raise KeyError(k)

    def _rehash(self):
        antigos = [p for b in self.buckets for p in b]
        self.cap *= 2                          # dobra a capacidade
        self.buckets = [[] for _ in range(self.cap)]
        self.n = 0
        for k, v in antigos:
            self.put(k, v)                     # reinsere TUDO: O(n)

# Custo médio de busca: 1 + α, onde α = n/capacidade.
# Com α = 0.75, isso é ~1.75 comparações. Praticamente O(1).

Resolvendo colisões: endereçamento aberto

# SOLUÇÃO 2: endereçamento aberto (open addressing)
# Sem listas: se o slot está ocupado, procura o próximo livre.
def put(tabela, k, v):
    i = hash(k) % len(tabela)
    while tabela[i] is not None and tabela[i][0] != k:
        i = (i + 1) % len(tabela)          # sondagem linear
    tabela[i] = (k, v)

# Vantagem: tudo num array contíguo → excelente uso de cache,
# zero alocação de nós. Costuma ser mais rápido na prática.
#
# Desvantagem 1: AGLOMERAÇÃO. Blocos de slots ocupados crescem e
#   se fundem, alongando as sondagens. Custo médio: ½(1 + 1/(1−α)).
#   Com α = 0.9, isso já são 5.5 sondagens. Com α = 0.99, 50.
#
# Desvantagem 2: REMOÇÃO é traiçoeira. Se você simplesmente apagar
#   um slot no meio de uma cadeia de sondagem, quebra a busca das
#   chaves seguintes. A solução é marcar como "tumba" (tombstone):
#   um marcador que diz "vazio para inserir, mas continue procurando".
#
# Variantes que reduzem a aglomeração:
#   - sondagem quadrática: i + 1², i + 2², i + 3² ...
#   - hash duplo: o passo da sondagem também depende da chave
#   - Robin Hood: chaves "pobres" (longe de casa) roubam o slot
#     de chaves "ricas", equalizando as distâncias de sondagem

Como o dict do Python faz

# O dict do Python (CPython 3.7+) é mais esperto que os dois:
#
# Ele separa a tabela de índices dos dados propriamente ditos:
#   indices = [None, 1, None, 0, None, 2, None, None]  ← esparso, pequeno
#   entries = [(hash, "gato", "🐱"),                    ← denso, na ORDEM
#              (hash, "sol",  "☀️"),                        de inserção
#              (hash, "casa", "🏠")]
#
# Consequências:
#   1. gasta ~30% menos memória (a parte esparsa só guarda inteiros)
#   2. iterar é rápido e sequencial (percorre entries direto)
#   3. a ordem de inserção é preservada — que virou GARANTIA da
#      linguagem no Python 3.7. Era um efeito colateral da otimização.

# Onde as hash tables aparecem sem você perceber, em Python:
d = {"a": 1}         # dict
s = {1, 2, 3}          # set — um dict só com as chaves
obj.__dict__          # atributos de objeto são um dict
globals(), locals()   # escopos são dicts
import sys; sys.modules  # módulos importados: um dict

# Por isso "chave precisa ser hasheável" (imutável): se a chave
# mudasse depois de inserida, o hash mudaria e ela ficaria
# perdida no bucket errado — inalcançável para sempre.

Construindo do zero

Mini projeto: implemente a HashChaining acima e instrumente-a: conte quantas comparações cada get faz. Insira 10 mil palavras de um dicionário e imprima o histograma de tamanho dos buckets. Depois troque a função hash por uma proposital ruim (len(chave)) e refaça o histograma — você vai ver a tabela virar dezenas de listas ligadas e a busca virar O(n) na prática.

Projeto principal: implemente um cache LRU com capacidade fixa, com get e put em O(1). A combinação clássica é uma hash table (chave → nó) somada a uma lista duplamente ligada que mantém a ordem de uso: acessar um item o move para a frente, e quando o cache enche você remove o último. É exatamente assim que o functools.lru_cache do Python funciona por dentro.

Desafio extra: implemente endereçamento aberto com remoção correta. Comece apagando o slot direto e escreva um teste que insira três chaves colidindo, remova a do meio e tente buscar a terceira — você vai ver a busca falhar. Então conserte com tombstones, e meça quanto o desempenho degrada quando a tabela acumula muitas tumbas (dica: elas contam para as sondagens mas não para o fator de carga, então precisam ser limpas em algum rehash).

Teste sua intuição

Onde você encontra isso