Tabelas de dispersão

Imagina a lista de alunos de uma turma e a tarefa de encontrar o nome a partir do número: dás o número, que aqui se chama chave, e recebes o nome, que se chama valor. Uma tabela de dispersão guarda pares de chave e valor e calcula, a partir da chave, a posição onde o par fica, usando uma função de hash.

Não conserva ordem entre chaves. O objetivo é pesquisa, inserção e remoção de custo esperado constante. Esse «esperado» exige hipóteses sobre distribuição e carga, que a secção de encadeamento fixa. Apagar sem marcador parte a pesquisa, como a secção de sondagem mostra com estados.

Endereçamento direto e função hash

Se as chaves forem inteiros em [0,M), podes guardar a chave x diretamente na posição x. O acesso é constante, mas a memória é $\Theta(M)$ mesmo com poucos elementos. Uma função hash reduz um universo grande a m posições e permite uma tabela menor, mas causa inevitavelmente colisões quando existem mais chaves possíveis que posições.

Uma boa função é barata e distribui as chaves usadas pelas posições. Não precisa de ser criptográfica. Para igualdade compatível com hashing, chaves consideradas iguais têm de produzir o mesmo hash. Um hash diferente prova desigualdade; um hash igual não prova igualdade.

Para strings, uma combinação polinomial pode usar Horner, incorporando um carácter de cada vez. Com base 31, "abc" calcula ((97)*31+98)*31+99=96354; a posição final é 96354 mod m. Uma função que soma apenas os dígitos decimais, como no exame-modelo 2024/25, junta 19 e 28 na mesma soma e distribui mal inteiros próximos: é um exemplo de função má, não um modelo a copiar. O cálculo inicial custa $O(L)$ para comprimento L. Overflow em tipos inteiros sem sinal tem semântica modular definida; overflow com sinal não tem. O tamanho de um tipo e a implementação de std::hash podem variar, pelo que não dependas de um número de hash concreto entre plataformas.

Encadeamento separado

Cada posição guarda um conjunto ou uma lista das chaves que ali colidem. Com n chaves e m posições, o fator de carga é $\alpha=n/m$. Sob distribuição aproximadamente uniforme, a cadeia esperada tem comprimento $\alpha$ e uma operação custa $O(1+\alpha)$, para hash e comparação de custo constante.

Com todas as chaves na mesma posição, uma pesquisa pode custar $\Theta(n)$. Controlar a carga não corrige uma função que envia todas as chaves para o mesmo sítio. Média esperada não significa garantia de pior caso.

Sondagem e três estados

No endereçamento aberto, as chaves ficam no próprio array. A sondagem linear tenta $(h(x)+i)\bmod m$, com i=0,1,....

A pesquisa precisa de saber quando parar: termina numa célula livre que nunca foi usada, ao encontrar a chave, ou após m tentativas. Por isso a tabela distingue três estados, livre, ocupada e apagada, em vez de apenas cheia e vazia.

Com m=7 e h(x)=x mod 7, as chaves 10, 17 e 24 ocupam as posições 3, 4 e 5. Se retirares 17 e marcares a posição 4 como livre, pesquisar 24 para cedo e conclui incorretamente que falta. Marca-a como apagada, ou tombstone, para que a pesquisa continue.

A inserção pode guardar a primeira posição apagada para reutilizar, mas deve continuar a sondar até excluir uma chave igual já presente. Inserir logo na tombstone criaria um duplicado mais à frente. Se completares uma volta, podes reutilizar a posição apagada; sem posição disponível, a tabela está cheia.

#include <array>
#include <iostream>
class Tabela {
    enum class Estado { livre, ocupado, apagado };
    struct Celula { int chave = 0; Estado estado = Estado::livre; };
    static constexpr int M = 7;
    std::array<Celula, M> t{};
    static int inicio(int x) { int r = x % M; return r < 0 ? r + M : r; }
public:
    bool contem(int x) const {
        for (int k = 0; k < M; ++k) {
            const auto& c = t[(inicio(x) + k) % M];
            if (c.estado == Estado::livre) return false;
            if (c.estado == Estado::ocupado && c.chave == x) return true;
        }
        return false;
    }
    bool inserir(int x) {
        int livre = -1;
        for (int k = 0; k < M; ++k) {
            const int i = (inicio(x) + k) % M;
            if (t[i].estado == Estado::ocupado) {
                if (t[i].chave == x) return false;
            } else {
                if (livre == -1) livre = i;
                if (t[i].estado == Estado::livre) break;
            }
        }
        if (livre == -1) return false;
        t[livre] = {x, Estado::ocupado}; return true;
    }
    bool remover(int x) {
        for (int k = 0; k < M; ++k) {
            auto& c = t[(inicio(x) + k) % M];
            if (c.estado == Estado::livre) return false;
            if (c.estado == Estado::ocupado && c.chave == x) {
                c.estado = Estado::apagado; return true;
            }
        }
        return false;
    }
};
int main() {
    Tabela t;
    for (int x : {10, 17, 24}) t.inserir(x);
    t.remover(17);
    std::cout << "24 existe: " << t.contem(24) << '\n';
    std::cout << "31 inserido: " << t.inserir(31) << '\n';
    std::cout << "24 repetido: " << t.inserir(24) << '\n';
    t.inserir(-4); std::cout << "-4 existe: " << t.contem(-4) << '\n';
}

A tabela do exemplo é fixa e não cresce. inserir devolve falso tanto para duplicado como para falta de espaço; uma interface de produção distinguiria esses resultados. O resto de uma chave negativa é normalizado para [0,7). O limite de sete sondagens evita ciclos infinitos numa tabela cheia, mesmo sem uma célula livre.

Agrupamento e variantes

A sondagem linear cria agrupamentos de células ocupadas: uma colisão alarga uma zona que passa a atrair mais chaves. Na sondagem quadrática, as tentativas incluem um termo quadrático; a cobertura de todas as posições depende do tamanho e dos coeficientes. Não assumes que uma sequência quadrática percorre a tabela inteira.

No hashing duplo, a posição é $(h_1(x)+i h_2(x))\bmod m$. Para visitares todas as posições, o passo deve ser não nulo e coprimo com m. Com m primo, qualquer passo em [1,m) funciona. Um passo com divisor comum de m visita só parte da tabela.

No endereçamento aberto, a carga tem de ser inferior a um para existir espaço livre. O número de tombstones também afeta os percursos, ou seja, n/m baixo não garante pesquisas curtas depois de muitas remoções. Uma reconstrução elimina tombstones e pode aumentar a capacidade.

Rehash e custo

Ao mudares m, recalcula a posição de cada chave e reinsere-a segundo a nova sequência de sondagem. Com m=7, 10, 17 e 24 ocupam 3, 4 e 5; com m=13, passam para 10, 4 e 11 sem colisão. Copiar 10 para a antiga posição 3 faria a pesquisa começar na célula livre 10 e declarar a chave ausente. A ficha 11 de 2025/26 trabalha uma tabela fixa, sem redimensionamento automático.

Rehash exige examinar todas as chaves e inicializar a nova tabela. O custo inclui a capacidade e as colisões das reinserções; sob distribuição adequada e capacidade proporcional a n, é esperado linear.

Se a tabela cresce geometricamente quando fica cheia, cada chave é recopiada poucas vezes: o custo total das reconstruções ao longo de n inserções é linear, ou seja, amortizado constante por inserção. Isto não elimina o pior caso das colisões: com uma função má, cada operação continua cara. A garantia combinada costuma ser custo esperado amortizado constante, sob dispersão adequada e capacidade proporcional a n.

Para contar motivos de ADN, percorre as substrings de comprimento K e incrementa um unordered_map<string,int>. Em ACACA, com K=2, lês AC, CA, AC, CA: cada motivo aparece duas vezes, incluindo posições sobrepostas. Há n-K+1 substrings, e copiar e calcular o hash de cada uma custa O(K). Por isso o tempo esperado é O(nK), como na ficha 11 de 2025/26, e não linear em n quando K varia.

Na biblioteca, unordered_set e unordered_map oferecem operações médias constantes e pior caso linear. reserve pode evitar reconstruções repetidas se souberes uma dimensão aproximada; não torna uma função hash má uniforme. find consulta sem inserir; unordered_map[key] cria um elemento se a chave faltar. Rehash invalida iteradores da biblioteca, embora referências a elementos possam ter garantias diferentes; consulta a regra da operação que usas.