Vimos que árvores binárias de busca oferecem busca em O(log n), e heaps fornecem acesso ao máximo em O(1). Mas é possível buscar um elemento arbitrário em O(1)? Sim — com tabelas hash. A ideia central é usar uma função matemática para mapear uma chave diretamente para um índice do vetor, eliminando comparações por completo. Em vez de percorrer uma árvore ou fazer busca binária, calculamos onde o elemento está e vamos direto ao ponto.

1. A ideia da tabela hash

Uma tabela hash é um vetor de tamanho m. Dada uma função de hash h: U → {0, 1, ..., m−1}, onde U é o universo de chaves possíveis, a chave k é armazenada na posição h(k) do vetor. A busca por k calcula h(k) e acessa diretamente aquela posição — sem percorrer estrutura nenhuma.

Exemplo: m = 7, h(k) = k % 7

Inserindo as chaves 15, 28, 33, 4 e 20:

h(15) = 15 % 7 = 1
h(28) = 28 % 7 = 0
h(33) = 33 % 7 = 5
h( 4) =  4 % 7 = 4
h(20) = 20 % 7 = 6

Tabela (m = 7):
+-------+-------+-------+-------+-------+-------+-------+
| [0]   | [1]   | [2]   | [3]   | [4]   | [5]   | [6]   |
+-------+-------+-------+-------+-------+-------+-------+
|  28   |  15   |  --   |  --   |   4   |  33   |  20   |
+-------+-------+-------+-------+-------+-------+-------+

Busca por 33: calcula h(33) = 5, acessa tabela[5] diretamente. Custo: O(1).

Três grandezas fundamentais:

• m: tamanho da tabela (número de posições).
• n: número de elementos armazenados.
• λ = n/m: fator de carga (load factor) — mede o quão "cheia" está a tabela. Um λ baixo significa poucas colisões; um λ alto aumenta a chance de colisão.

2. Propriedades de uma boa função de hash

Nem toda função que mapeia chaves a índices é útil na prática. As propriedades desejáveis são:

3. Hash por divisão (método simples)

Intuição do módulo

Pense no módulo como um relógio. Um relógio de 12 horas "dá a volta" a cada 12 unidades: depois das 11 vem o 0, depois vem o 1, e assim por diante. O módulo faz exatamente isso: conta de 0 até m−1 e recomeça.

m = 5  →  os possíveis índices são 0, 1, 2, 3, 4

k:    0  1  2  3  4  5  6  7  8  9  10  11  12 ...
h(k): 0  1  2  3  4  0  1  2  3  4   0   1   2 ...
                      ↑ "dá a volta" aqui

O módulo garante que qualquer chave, por maior que seja, produz um índice válido em [0, m−1]. O custo é O(1): uma única divisão inteira.

O problema é que o módulo descarta a parte inteira de k/m e conserva apenas o resto. Se as chaves tiverem padrão regular, o resto também terá — e isso causa colisões sistemáticas.

A escolha de m importa muito

Por que m primo ajuda?

A intuição não é que números primos sejam magicamente melhores. O ponto é mais sutil: quando as chaves seguem um padrão periódico (são múltiplos de algum número d, por exemplo), o conjunto de índices possíveis fica restrito a múltiplos de mdc(d, m). Se mdc(d, m) > 1, muitos slots ficam inacessíveis e as chaves se amontoam nos que sobram.

Um m primo resolve isso: mdc(d, m) = 1 para qualquer d que não seja múltiplo de m, então todos os m slots podem ser atingidos — o padrão das chaves não restringe os índices usados.

Comparação com as mesmas chaves: m = 10 vs m = 11

Chaves: 100, 200, 300, 123, 456, 789, 50

Repare que 100, 200, 300 e 50 são todos múltiplos de 10 — um padrão periódico com d = 10.

m = 10 (composto — mdc(10, 10) = 10):

h(100) = 100 % 10 = 0
h(200) = 200 % 10 = 0   ← colisão
h(300) = 300 % 10 = 0   ← colisão
h(123) = 123 % 10 = 3
h(456) = 456 % 10 = 6
h(789) = 789 % 10 = 9
h( 50) =  50 % 10 = 0   ← colisão

100, 200, 300 e 50 — quatro chaves diferentes, todas para o slot [0].
Os outros 9 slots mal são usados.
Por quê? Todos terminam em 0; k % 10 captura só o último dígito decimal.

m = 11 (primo — mdc(10, 11) = 1):

h(100) = 100 % 11 = 1
h(200) = 200 % 11 = 2
h(300) = 300 % 11 = 3
h(123) = 123 % 11 = 2   ← colisão com 200
h(456) = 456 % 11 = 5
h(789) = 789 % 11 = 8
h( 50) =  50 % 11 = 6

Apenas 1 colisão — e ela não tem nada a ver com o padrão das chaves.
100, 200, 300 e 50 ficaram em slots diferentes: o padrão foi quebrado.

Exemplo ruim: m = 8 (potência de 2)

Chaves: 8, 16, 24, 32   (múltiplos de 8)
h( 8) =  8 % 8 = 0
h(16) = 16 % 8 = 0   ← colisão
h(24) = 24 % 8 = 0   ← colisão
h(32) = 32 % 8 = 0   ← colisão

Todos vão para [0] — a tabela degenera para uma lista.

Por quê? Em binário:
   8 = 0...01000   últimos 3 bits: 000
  16 = 0...10000   últimos 3 bits: 000
  24 = 0...11000   últimos 3 bits: 000
  32 = 0...100000  últimos 3 bits: 000

k % 8 captura apenas os 3 bits finais — e todos são iguais.
Os bits que diferenciam as chaves (os mais significativos) são ignorados.

4. Hash multiplicativo

O hash por divisão usa apenas o resto de k ÷ m — o que ignora boa parte da informação contida em k. O hash multiplicativo extrai informação de todos os bits da chave, em três etapas:

1. Multiplica a chave por uma constante A ∈ (0, 1): obtém k · A.
2. Descarta a parte inteira de k · A, ficando apenas com a parte fracionária frac(k · A) — um número em [0, 1).
3. Escala para o intervalo [0, m): multiplica por m e arredonda para baixo.

onde frac(x) = x − ⌊x⌋ (parte fracionária).

Por que funciona?

A parte inteira de k · A cresce com k e é descartada — ela carregaria o padrão regular das chaves. A parte fracionária, por outro lado, não segue um padrão simples quando A é irracional: multiplicar por um número irracional "quebra" qualquer regularidade das chaves e espalha os valores por [0, 1) de forma quase uniforme.

Knuth recomenda usar a razão áurea conjugada:

Essa constante tem uma propriedade matemática especial: as partes fracionárias de 1·A, 2·A, 3·A, ... se distribuem no intervalo [0,1) de forma maximamente uniforme — cada novo ponto cai no maior espaço ainda vazio entre os pontos anteriores. É a constante que minimiza a chance de colisões sistemáticas.

Vantagem sobre o hash por divisão

O método funciona bem para qualquer valor de m, inclusive potências de 2. No hash por divisão, m = 2^p é problemático porque a operação k % 2^p considera apenas os p bits menos significativos de k. No hash multiplicativo, a multiplicação por A mistura todos os bits antes de extrair o índice.

Exemplo passo a passo: m = 8, A = 0,618, chaves 10, 20, 30

k = 10:
  Passo 1 — multiplica:  10 · 0,618 = 6,18
  Passo 2 — frac:        frac(6,18) = 0,18
  Passo 3 — escala:      ⌊8 · 0,18⌋ = ⌊1,44⌋ = 1   →  h(10) = 1

k = 20:
  Passo 1 — multiplica:  20 · 0,618 = 12,36
  Passo 2 — frac:        frac(12,36) = 0,36
  Passo 3 — escala:      ⌊8 · 0,36⌋ = ⌊2,88⌋ = 2   →  h(20) = 2

k = 30:
  Passo 1 — multiplica:  30 · 0,618 = 18,54
  Passo 2 — frac:        frac(18,54) = 0,54
  Passo 3 — escala:      ⌊8 · 0,54⌋ = ⌊4,32⌋ = 4   →  h(30) = 4

Resultado: 10→1, 20→2, 30→4  (espalhado, sem colisões)

Compare com h(k) = k % 8:
  h(10) = 2,  h(20) = 4,  h(30) = 6  (padrão regular: sempre pares)
  Para k = 8, 16, 24: todos vão para [0] — degeneração.
  O hash multiplicativo não sofre esse problema.

5. Hash para strings — hash polinomial

O problema com strings

Strings não são inteiros — não dá para aplicar divisão ou multiplicação diretamente. A abordagem mais simples seria somar os valores ASCII de cada caractere. Mas somas ignoram a ordem: "gato" e "tago" teriam o mesmo hash, e anagramas colidiriam sempre.

A solução é dar um peso diferente a cada posição. Trata-se a string como um polinômio em que os coeficientes são os valores ASCII e a variável é uma base B:

O primeiro caractere é multiplicado pela maior potência de B — ele tem mais influência no resultado. O último caractere é multiplicado por B⁰ = 1. Assim, a mesma letra em posições diferentes contribui valores diferentes, e a ordem importa.

A base B é tipicamente 31 (para letras minúsculas) ou 37. Valores primos reduzem colisões entre anagramas.

Regra de Horner — calculando sem potências explícitas

A fórmula acima tem um problema prático: calcular B^L-1, B^L-2, ... exigiria L exponenciações separadas, e para strings longas as potências crescem sem limite — overflow garantido. A Regra de Horner reorganiza o polinômio algebricamente para evitar isso.

A fórmula geral é a recorrência:

Para ver que é o mesmo polinômio, expanda passo a passo:

É exatamente o polinômio original — mas calculado com apenas uma multiplicação e uma adição por passo, sem potências.

Considere uma string de 4 caracteres para ver como a fatoração funciona. O polinômio original:

pode ser reescrito fatorando B progressivamente da esquerda para a direita:

São expressões idênticas — experimente expandir os parênteses. O ganho é que agora basta uma multiplicação e uma adição por passo, sem potência alguma. O algoritmo fica:

Percorra os caracteres da esquerda para a direita, atualizando h a cada passo. Ao final, aplique mod m. Por segurança, aplique % m em cada iteração — assim os valores intermediários ficam sempre em [0, m−1] e não há risco de overflow mesmo em strings longas.

Exemplo: B = 31, m = 13, hash("gato")

Valores ASCII: 'g'=103, 'a'=97, 't'=116, 'o'=111

h₀ =  0
h₁ = ( 0 * 31 + 103) % 13  →  103 % 13 = 12   (processou 'g')
h₂ = (12 * 31 +  97) % 13  →  469 % 13 =  1   (processou 'a')
h₃ = ( 1 * 31 + 116) % 13  →  147 % 13 =  4   (processou 't')
h₄ = ( 4 * 31 + 111) % 13  →  235 % 13 =  1   (processou 'o')

h("gato") = h₄ = 1

A ordem importa — comparando com o anagrama "tago"

Valores ASCII: 't'=116, 'a'=97, 'g'=103, 'o'=111

h₀ =  0
h₁ = (  0 * 31 + 116) % 13  →  116 % 13 =  7   (processou 't')
h₂ = (  7 * 31 +  97) % 13  →  314 % 13 =  1   (processou 'a')
h₃ = (  1 * 31 + 103) % 13  →  134 % 13 =  4   (processou 'g')
h₄ = (  4 * 31 + 111) % 13  →  235 % 13 =  1   (processou 'o')

h("tago") = h₄ = 1

Neste caso houve colisão — ambas produziram 1.
Isso acontece porque m = 13 é pequeno demais: há apenas 13 slots possíveis
para infinitas strings. Com m primo grande (ex.: 100003) e B = 31,
a chance de dois anagramas distintos colidirem é muito menor.

Custo: O(L) onde L é o comprimento da string — cada caractere é processado exatamente uma vez.

6. Código C das funções de hash

/* Hash por divisão.
   O (+m)%m garante resultado não-negativo para chaves negativas. */
int hashDivisao(int chave, int m) {
    return ((chave % m) + m) % m;
}

/* Hash multiplicativo de Knuth. */
int hashMultiplicativo(int chave, int m) {
    double A    = 0.6180339887;
    double frac = chave * A - (int)(chave * A);
    return (int)(m * frac);
}

/* Hash polinomial para strings (Regra de Horner). */
int hashString(const char *s, int m) {
    int h = 0;
    int B = 31;
    for (int i = 0; s[i] != '\0'; i++)
        h = (h * B + s[i]) % m;
    return h;
}

7. Colisões são inevitáveis

Por melhor que seja a função de hash, colisões não podem ser completamente eliminadas quando o universo de chaves é maior que m. Isso é uma consequência direta do princípio da casa dos pombos: se mais de m chaves distintas precisam ser mapeadas para m posições, alguma posição receberá pelo menos duas chaves.

O problema do aniversário

A situação é ainda mais delicada: a primeira colisão ocorre muito mais cedo do que se imagina. O problema do aniversário mostra que, em um grupo de apenas 23 pessoas, a probabilidade de duas delas compartilharem o mesmo dia de aniversário supera 50% — mesmo havendo 365 dias possíveis.

Para uma tabela de tamanho m, a primeira colisão ocorre com
probabilidade > 50% após aproximadamente √m inserções:

  m = 365   (dias do ano)    → ~23 inserções para >50% de colisão
  m = 1024  (tabela pequena) → ~38 inserções para >50% de colisão
  m = 10000 (tabela média)   → ~118 inserções para >50% de colisão

Mesmo com m = 1.000.000, a primeira colisão é esperada
em torno de ~1177 inserções — muito antes de a tabela
estar cheia.

8. Complexidade

O caso médio O(1) assume uma boa função de hash (distribuição uniforme) e fator de carga adequado: λ < 1 para encadeamento separado, ou λ < 0,75 para endereçamento aberto. O pior caso O(n) ocorre quando todas as n chaves colidem no mesmo slot — a tabela degenera para uma lista encadeada. Na prática, com uma boa função de hash e λ controlado, o pior caso raramente acontece.

Resumo

Exercícios

1. O que é uma tabela hash e qual é sua principal vantagem em relação a uma árvore binária de busca balanceada?
2. Dada a função h(k) = k % 11, insira as chaves 44, 33, 77, 55, 22 em uma tabela de tamanho 11. Em qual posição cada chave é armazenada? Há colisão?
3. Por que m = 16 (potência de 2) é uma escolha ruim para a função h(k) = k % m? Dê um exemplo concreto de um conjunto de chaves que degrada o desempenho.
4. Uma tabela hash tem m = 100 slots e n = 75 elementos. Qual é o fator de carga? Esse valor é aceitável para endereçamento aberto?
5. Por que o hash polinomial para strings usa a Regra de Horner em vez de calcular diretamente o polinômio B^L-1 · s[0] + B^L-2 · s[1] + ...?
6. As strings "ar" e "ra" deveriam (idealmente) ter hashes diferentes. O hash polinomial com base B garante isso? Por quê?
7. O que é o problema do aniversário e o que ele implica para tabelas hash?
8. Uma função de hash sempre retorna 0 para qualquer entrada. Ela é determinística e computada em O(1). Por que ainda assim é uma péssima função de hash?

h(44) = 44 % 11 = 0
h(33) = 33 % 11 = 0   ← COLISÃO com 44!
h(77) = 77 % 11 = 0   ← COLISÃO com 44 e 33!
h(55) = 55 % 11 = 0   ← COLISÃO!
h(22) = 22 % 11 = 0   ← COLISÃO!

Todas as chaves vão para a posição [0].
Isso ocorre porque 44, 33, 77, 55 e 22 são todos múltiplos de 11.
m = 11 é primo, mas as chaves foram escolhidas especificamente para
serem múltiplos de m — ilustrando que nenhuma função garante ausência
de colisões para qualquer conjunto de chaves.