Tabelas de dispersão

Ideia central

Uma tabela de dispersão localiza a chave pelo seu hash, sem manter ordem.

• Se duas chaves são iguais, os seus hashes são iguais. A recíproca é falsa: uma colisão não prova igualdade.
• Chaves em [0,M) dispensam hash: o acesso direto custa $O(1)$ com memória $\Theta(M)$.
• O hash comprime um universo grande em m posições. Calcular o hash de uma string lê em geral os seus carateres: custa o comprimento da chave, não $O(1)$ por defeito. Uma soma simples dos códigos, reduzida módulo m, colide anagramas; serve para mostrar esse custo, não como hash recomendado. A lição usa uma combinação polinomial (Horner, base 31) para distribuir melhor.
• A carga é $\alpha=n/m$, com n chaves em m posições. Com dispersão uniforme e custo constante de hash e comparação (chaves de dimensão limitada), o encadeamento custa $O(1+\alpha)$ em média; se tudo colidir, degrada para $\Theta(n)$.

Três estados da sondagem

Linear tenta $(h+i)\bmod m$. Apagar sem marcador parte a pesquisa.

Encontra	Pesquisa	Inserção
Ocupada	Compara	Rejeita se igual
Tombstone	Passa à frente	Guarda para reutilizar
Livre	Termina com ausência	Fecha a procura de duplicado

Limita a m passos. Só reutiliza a tombstone depois de excluir duplicado à frente.

Com m=7 e h(x)=x \bmod 7, as chaves 10, 17 e 24 ficam nas posições 3, 4 e 5. Apagar 17 deixa uma marca na posição 4; a pesquisa de 24 atravessa essa marca e encontra a chave na posição 5.

Passo e reconstrução

• Linear agrupa. Quadrática pode não cobrir todas as posições.
• Duplo usa um passo coprimo com m. Com m primo, qualquer passo com $1\le passo<m$ percorre a tabela; um múltiplo de m não serve, mesmo sendo não nulo como inteiro.
• Rehash recalcula cada chave no novo tamanho. Copiar os índices antigos invalida a tabela.
• unordered_set tem custo médio constante e pior linear. reserve(n) reduz reconstruções, mas não as elimina em geral; rehash invalida iteradores.

Exemplo completo.