Buscar uma chave em um dict Python com dez entradas leva o mesmo tempo que buscar em um com dez milhões. Isso não é acidente de uma linguagem rápida. O dict do Python, o HashMap do Java e o Map do JavaScript são todos tabelas hash, e todo o design existe para que busca, inserção e remoção rodem em O(1) na média. A notação Big O dá a essa busca o rótulo “tempo constante”. Este é o mecanismo que justifica isso.

Como uma tabela hash transforma uma chave em índice de array

Uma tabela hash é um array mais uma função que transforma uma chave em uma posição nesse array.

1

índice do bucket = hash(chave) % número_de_buckets

hash() recebe uma chave de qualquer tamanho (uma string, uma tupla, um objeto) e retorna um inteiro. Dentro de uma mesma execução do programa, a mesma chave sempre produz o mesmo inteiro, e uma boa função hash distribui esses inteiros de forma quase uniforme por toda a sua faixa de saída. Pegue o inteiro módulo o tamanho do array e você tem um slot. Armazene a chave e o valor ali. Uma busca posterior recalcula o mesmo hash, cai no mesmo slot e lê o valor. Sem percorrer nada, sem comparar com todas as outras chaves.

Tudo o mais em uma tabela hash real, da gestão de colisões ao resize até a sequência exata de probing, existe para manter essa busca de um único passo funcionando enquanto a tabela se enche.

Uma versão mínima que ignora colisões:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class TinyTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [None] * size

    def put(self, key, value):
        index = hash(key) % self.size
        self.buckets[index] = (key, value)

    def get(self, key):
        index = hash(key) % self.size
        if self.buckets[index] is None:
            raise KeyError(key)
        stored_key, value = self.buckets[index]
        if stored_key != key:
            raise KeyError(key)
        return value

1
2
3
4

>>> t = TinyTable()
>>> t.put("user:42", {"name": "Dana"})
>>> t.get("user:42")
{'name': 'Dana'}

Isso quebra assim que duas chaves diferentes caem no mesmo índice. hash("user:42") % 8 e hash("user:17") % 8 podem dar 3 nos dois casos, e TinyTable só tem espaço para uma delas: o segundo put sobrescreve o primeiro silenciosamente. Essa é uma colisão.

Como as tabelas hash lidam com colisões: chaining vs. open addressing

Existem duas formas padrão de manter as duas chaves quando caem no mesmo slot.

O chaining transforma cada bucket em um pequeno contêiner, normalmente uma lista encadeada. Uma colisão significa que o bucket guarda duas entradas em vez de uma, e a busca percorre essa lista até achar a chave correspondente.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class ChainedTable:
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]

    def put(self, key, value):
        index = hash(key) % self.size
        bucket = self.buckets[index]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket = self.buckets[hash(key) % self.size]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

O HashMap do Java é uma tabela com chaining. Cada bucket começa como lista encadeada. Se um bucket acumula pelo menos 8 entradas e a tabela tem pelo menos 64 buckets, esse bucket se converte em uma árvore rubro-negra (TREEIFY_THRESHOLD e MIN_TREEIFY_CAPACITY no código do JDK), de modo que uma varredura O(n) no pior caso de um bucket sobrecarregado passa a ser O(log n). Ele volta a ser lista se um resize o deixar com 6 entradas ou menos.

O open addressing mantém cada entrada diretamente no array, sem estrutura secundária e sem ponteiros. Em caso de colisão, ele sonda: tenta outro slot, seguindo uma regra fixa, até achar um vazio. O dict do CPython funciona assim, e o comentário sobre a busca em Objects/dictobject.c dá a razão: “Open addressing is preferred over chaining since the link overhead for chaining would be substantial.” O CPython também evita o probing linear puro, que forma aglomerados quando as chaves chegam em ordem previsível. Cada passo de probing mistura mais bits do hash no próximo índice, então duas chaves que colidem nos bits baixos se separam alguns probings depois.

As duas estratégias falham de formas diferentes. Uma tabela com chaining que enche fica mais lenta, e no pior caso toda entrada acaba em uma única lista longa. Uma tabela com open addressing não tem onde colocar uma entrada quando o array enche, então precisa fazer resize antes que isso aconteça.

O que é load factor e por que a tabela faz resize antes de ficar cheia

Load factor é o número de entradas dividido pelo número de buckets. As duas estratégias monitoram isso para decidir quando fazer resize, e Java e CPython escolhem limites diferentes.

O HashMap do Java faz resize quando o número de entradas supera a capacidade multiplicada pelo load factor. O Javadoc do construtor sem argumentos dá os valores padrão: 16 buckets, load factor 0,75, então o primeiro resize dispara na 12ª entrada. Um resize dobra aproximadamente o número de buckets e refaz o hash de todas as entradas existentes no novo array. É por isso que o Javadoc recomenda dimensionar o map antecipadamente com HashMap.newHashMap(expectedSize) (Java 19+) quando você sabe aproximadamente quantas entradas ele terá: você evita os rehashes repetidos.

O dict do CPython faz resize mais tarde e cresce mais rápido. O comentário USABLE_FRACTION no código diz que a tabela faz resize quando está dois terços cheia, e GROWTH_RATE dimensiona a nova tabela para cerca de três vezes o número atual de entradas vivas, não um simples dobro.

Nenhum dos dois números é arbitrário. Um load factor perto de 1 aproveita o array ao máximo, mas torna cada operação mais lenta conforme os buckets enchem; um load factor perto de 0 desperdiça memória em slots que ainda ninguém usa. Os dois designs se estabilizam entre 0,66 e 0,75, ponto a partir do qual mais memória já não reduz muito os probings.

Por que a busca em uma tabela hash é O(1) na média, não sempre

O tempo constante só se mantém enquanto os hashes distribuem as chaves de forma quase uniforme entre os buckets. Duas coisas quebram isso.

Uma função hash ruim ou previsível. Se toda chave que você insere cai no mesmo bucket, uma tabela com chaining degenera em uma única lista encadeada com busca O(n), exatamente o que a estrutura existe para evitar. Isso acontece em produção. Um servidor que faz hash de entrada controlada por um atacante (nomes de campos de formulário, cabeçalhos HTTP, chaves JSON) com uma função previsível fica exposto a ataques de complexidade algorítmica: o atacante envia milhares de chaves construídas para colidir e força o pior comportamento em cada requisição. O Python randomiza o hash de str e bytes por processo desde a versão 3.3 (controlado por PYTHONHASHSEED) exatamente por esse motivo. A mesma string produz hashes diferentes em duas execuções do interpretador, então ninguém consegue pré-calcular um conjunto de colisões offline.

Modificar uma chave depois de inserida. O bucket onde uma chave vive foi escolhido pelo seu hash, então a tabela assume que esse hash nunca muda. O Python impõe isso no nível do tipo: tipos mutáveis como list e dict definem __hash__ como None, e usar um deles como chave gera TypeError: unhashable type: 'list' antes que o erro possa acontecer. Tuplas e strings são hashable porque são imutáveis. Para uma classe de chave personalizada, implemente __hash__ e __eq__ juntos e baseie-os apenas em campos que nunca mudam. Caso contrário, uma chave editada “desaparece”: a entrada ainda está na tabela, no bucket apontado pelo hash antigo, mas a busca procura em outro lugar.

Quando não usar uma tabela hash

Uma tabela hash responde rápido a uma pergunta: essa chave existe, e qual é o seu valor? Quase tudo o mais ela faz mal.

  • Consultas de intervalo e ordenação. “Todos os usuários criados este mês” ou “a próxima chave depois desta” precisam de uma estrutura ordenada. Uma tabela hash não tem ordem. O dict do CPython garante ordem de inserção desde a 3.7, mas isso é ordem de iteração, não ordem de classificação, e não ajuda em “tudo entre X e Y”. Essa consulta é trabalho de uma B-tree, por isso a maioria dos bancos de dados usa índices B-tree como padrão em vez de índices hash. Como funcionam os índices de banco de dados trata o trade-off entre scan e seek por trás desse padrão.
  • Correspondência por prefixo ou aproximada. “Chaves que começam com user:” significa verificar cada chave uma a uma. Uma trie, ou uma estrutura ordenada com busca binária, resolve isso diretamente.
  • Chaves inteiras pequenas em um intervalo restrito. Se a chave já é um dia da semana ou uma classe de código de status HTTP, pule a função hash e indexe o array diretamente. Uma camada a menos, nenhuma colisão.

Quando uma tabela hash é a estrutura certa, você quase nunca escreve uma do zero. dict, HashMap, Map e std::unordered_map já são otimizadas e corretas. Você também as usa indiretamente mais do que imagina: uma função decorada com functools.lru_cache, tratada em Decoradores Python explicados, constrói uma chave a partir dos argumentos da chamada e a busca em um dict.

A decisão, então, é simples. Se a operação é “busque isso por chave exata”, use a tabela hash embutida e não escreva a sua. Se a questão envolve ordem, intervalos ou correspondências parciais, escolha desde o início uma estrutura ordenada ou uma trie, porque nenhuma função hash conserta uma estrutura que responde à pergunta errada.

Artigos relacionados