Na Aula 19 definimos tabelas hash e funções de hash: dada uma chave k, calculamos um índice h(k) e armazenamos o elemento diretamente naquela posição. O objetivo é acesso em O(1). O problema: duas chaves distintas podem produzir o mesmo índice — isso é uma colisão. Esta aula apresenta as principais estratégias para lidar com colisões sem perder a eficiência.

1. Colisões são inevitáveis

Seja U o universo de chaves possíveis e m o tamanho da tabela. Se |U| > m, pelo princípio da casa dos pombos, é matematicamente impossível que toda função de hash evite colisões: existem mais chaves do que posições.

Mais surpreendente: mesmo com uma função boa e uma tabela razoavelmente grande, as colisões aparecem muito antes de a tabela estar cheia. O problema do aniversário mostra que, ao inserir apenas ≈√m chaves, a probabilidade de pelo menos uma colisão já supera 50%:

Isso não é uma falha da função de hash — é probabilidade básica. Uma colisão não significa que a tabela está quebrada; significa que precisamos de uma política de tratamento para continuar operando corretamente.

2. Encadeamento separado (chaining)

A ideia mais direta: cada posição da tabela não guarda um único elemento, mas sim uma lista encadeada de todos os elementos que mapeiam para aquele índice. Uma colisão simplesmente estende a lista.

Operações:

• Inserção: calcula i = h(k), adiciona o novo elemento no início da lista em tabela[i]. Custo: O(1).
• Busca: calcula i = h(k), percorre a lista em tabela[i] até encontrar a chave ou chegar ao fim. Custo: O(1 + comprimento da lista).
• Remoção: localiza o elemento como na busca e o retira da lista. Custo: O(1 + comprimento da lista).

Fator de carga e desempenho:

Define-se o fator de carga como λ = n / m, onde n é o número de elementos e m é o número de slots. Com encadeamento, λ pode superar 1 (mais elementos do que slots). O comprimento esperado de cada lista é exatamente λ. Portanto, o custo médio de busca é O(1 + λ). Se mantemos λ = O(1) (por exemplo, λ ≤ 1), a busca é O(1) em média.

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

Inserindo as chaves: 10, 22, 31, 4, 15, 28, 17

• 10 % 7 = 3
• 22 % 7 = 1
• 31 % 7 = 3
• 4 % 7 = 4
• 15 % 7 = 1
• 28 % 7 = 0
• 17 % 7 = 3

slot 0: [28]
slot 1: [15] → [22]
slot 2: (vazio)
slot 3: [17] → [31] → [10]
slot 4: [4]
slot 5: (vazio)
slot 6: (vazio)

n = 7, m = 7, λ = 7/7 = 1,0
Comprimento médio de busca: O(1 + 1,0) = O(1)
Pior caso neste exemplo: slot 3 tem 3 elementos → 3 comparações

Implementação em C:

typedef struct No {
    int chave;
    int valor;
    struct No *prox;
} No;

typedef struct {
    No **tabela;   /* vetor de ponteiros para listas */
    int m;         /* número de slots */
    int n;         /* número de elementos */
} TabelaHash;

/* Inserção com encadeamento — O(1) */
void inserir(TabelaHash *t, int chave, int valor) {
    int i = chave % t->m;
    No *novo = malloc(sizeof(No));
    novo->chave = chave;
    novo->valor = valor;
    novo->prox  = t->tabela[i];   /* insere no início */
    t->tabela[i] = novo;
    t->n++;
}

/* Busca com encadeamento — O(1 + comprimento da lista) */
int buscar(TabelaHash *t, int chave) {
    int i = chave % t->m;
    No *p = t->tabela[i];
    while (p != NULL) {
        if (p->chave == chave) return p->valor;
        p = p->prox;
    }
    return -1;   /* não encontrado */
}

/* Remoção com encadeamento — O(1 + comprimento da lista) */
int remover(TabelaHash *t, int chave) {
    int i = chave % t->m;
    No *p = t->tabela[i];
    No *ant = NULL;
    while (p != NULL) {
        if (p->chave == chave) {
            if (ant == NULL)
                t->tabela[i] = p->prox;   /* era o primeiro */
            else
                ant->prox = p->prox;
            free(p);
            t->n--;
            return 1;   /* removido */
        }
        ant = p;
        p   = p->prox;
    }
    return 0;   /* não encontrado */
}

main de demonstração:

int main(void) {
    TabelaHash t;
    t.m      = 7;
    t.n      = 0;
    t.tabela = malloc(t.m * sizeof(No *));
    for (int i = 0; i < t.m; i++) t.tabela[i] = NULL;

    int chaves[] = {10, 22, 31, 4, 15, 28, 17};
    for (int i = 0; i < 7; i++)
        inserir(&t, chaves[i], chaves[i]);   /* chave = valor por simplicidade */

    printf("buscar(31) = %d\n", buscar(&t, 31));   /*  31 */
    printf("buscar(99) = %d\n", buscar(&t, 99));   /*  -1 */
    printf("lambda = %.2f\n", (double)t.n / t.m);   /* 1.00 */

    remover(&t, 31);
    printf("apos remover(31): buscar(31) = %d\n", buscar(&t, 31));   /* -1 */

    for (int i = 0; i < t.m; i++) {
        No *p = t.tabela[i];
        while (p) { No *prox = p->prox; free(p); p = prox; }
    }
    free(t.tabela);
    return 0;
}

3. Endereçamento aberto — Linear Probing

No endereçamento aberto, todos os elementos são armazenados dentro da própria tabela (sem listas externas). Quando ocorre uma colisão, procura-se (sondagem) outra posição livre dentro da tabela. Consequentemente, o número de elementos n nunca pode exceder m: obrigatoriamente λ < 1.

No linear probing, a sondagem avança linearmente a partir do índice inicial:

h(k, i) = (h(k) + i) % m     para i = 0, 1, 2, ...

Exemplo — m = 11 (primo), h(k) = k % 11:

Inserindo: 10, 22, 31, 4, 15, 28, 17, 88, 59

Chave 10: h=10%11=10. Slot 10 livre. → slot 10.
Chave 22: h=22%11= 0. Slot  0 livre. → slot  0.
Chave 31: h=31%11= 9. Slot  9 livre. → slot  9.
Chave  4: h= 4%11= 4. Slot  4 livre. → slot  4.
Chave 15: h=15%11= 4. Slot  4 OCUPADO → tenta 5: livre. → slot  5.
Chave 28: h=28%11= 6. Slot  6 livre. → slot  6.
Chave 17: h=17%11= 6. Slot  6 OCUPADO → tenta 7: livre. → slot  7.
Chave 88: h=88%11= 0. Slot  0 OCUPADO → tenta 1: livre. → slot  1.
Chave 59: h=59%11= 4. Slot  4 OCUPADO → 5 OCUPADO → 6 OCUPADO
                        → 7 OCUPADO → tenta 8: livre. → slot  8.

Estado final da tabela:
slot  0: 22
slot  1: 88
slot  2: (livre)
slot  3: (livre)
slot  4:  4
slot  5: 15
slot  6: 28
slot  7: 17
slot  8: 59   ← percorreu 5 posições por causa do agrupamento!
slot  9: 31
slot 10: 10

Problema: agrupamento primário (primary clustering)

Observe que os slots 4 a 8 formam um bloco contíguo ocupado. Isso é o agrupamento primário: sequências de slots ocupados tendem a crescer, porque qualquer chave que caia em qualquer posição desse bloco é forçada para o final, tornando o bloco ainda maior. Quanto maior o bloco, maior a chance de uma nova colisão — um ciclo vicioso.

Busca e remoção:

Para buscar a chave k: sonde h(k), h(k)+1, ... até encontrar a chave ou encontrar um slot livre (prova de que a chave não está na tabela).

Para remover: não se pode simplesmente apagar o elemento, pois um slot livre quebraria a cadeia de sondagem de chaves inseridas depois. A solução é usar um marcador especial chamado lápide (tombstone): o slot é marcado como "deletado" (não "livre"), e futuras buscas continuam além dele, mas inserções podem reutilizá-lo.

Exemplo do problema de remoção simples:

Tabela (linear probing, m=11):  slot 4=4, slot 5=15, slot 6=28 ...

Removemos a chave 15 do slot 5 e simplesmente apagamos:
  slot 5: (livre)

Agora buscamos a chave 28:
  h(28) = 6. Slot 6 tem 28. ENCONTRADO — correto neste caso.

Buscamos a chave 59 (que foi inserida em slot 8):
  h(59) = 4 → slot 4 tem 4, ≠ 59 → tenta slot 5: LIVRE → PARA.
  Conclusão: "59 não está na tabela." — ERRADO!

Com lápide (DELETADO ≠ LIVRE):
  slot 5: [DELETADO]
  h(59) = 4 → 4, ≠ → slot 5: DELETADO (continua) → slot 6 → slot 7 → slot 8: 59. ENCONTRADO. ✓

Implementação em C:

#define LIVRE    0
#define OCUPADO  1
#define DELETADO 2

typedef struct { int chave; int estado; } Slot;

void inserirLinear(Slot tab[], int m, int chave) {
    int pos     = chave % m;   /* slot inicial dado pela função de hash */
    int i       = 0;           /* contador de tentativas */
    int pri_del = -1;          /* índice da primeira lápide encontrada (-1 = nenhuma ainda) */
    while (tab[pos].estado != LIVRE && i < m) {
        /* Guarda a lápide mais próxima, mas continua para detectar duplicata */
        if (tab[pos].estado == DELETADO && pri_del == -1)
            pri_del = pos;
        if (tab[pos].estado == OCUPADO && tab[pos].chave == chave)
            return;   /* chave já existe — não insere duplicata */
        i++;
        pos = (pos + 1) % m;   /* próximo slot (circular) */
    }
    /* Se encontramos uma lápide antes, inserimos lá (posição mais próxima
       ao hash original, o que reduz o comprimento das cadeias futuras).
       Caso contrário, inserimos no slot LIVRE onde o while parou. */
    int dest;
    if (pri_del != -1)
        dest = pri_del;
    else
        dest = pos;
    tab[dest].chave  = chave;
    tab[dest].estado = OCUPADO;
}

int buscarLinear(Slot tab[], int m, int chave) {
    int pos = chave % m;
    int i   = 0;
    while (tab[pos].estado != LIVRE && i < m) {
        if (tab[pos].estado == OCUPADO && tab[pos].chave == chave)
            return pos;
        i++;
        pos = (pos + 1) % m;
    }
    return -1;
}

void removerLinear(Slot tab[], int m, int chave) {
    int pos = buscarLinear(tab, m, chave);
    if (pos != -1) tab[pos].estado = DELETADO;   /* lápide */
}

4. Endereçamento aberto — Quadratic Probing

O quadratic probing tenta resolver o agrupamento primário usando um deslocamento quadrático:

h(k, i) = (h(k) + c1·i + c2·i²) % m

Forma comum: c1 = 0, c2 = 1  →  h(k, i) = (h(k) + i²) % m

Exemplo — m = 11, h(k, i) = (k%11 + i²) % 11:

Chave  4: h=4. Slot 4 livre. → slot 4.
Chave 15: h=4. Slot 4 OCUPADO.
           i=1: (4 + 1) % 11 = 5. Slot 5 livre. → slot 5.
Chave 26: h=4. Slot 4 OCUPADO.
           i=1: (4 + 1) % 11 = 5. Slot 5 OCUPADO.
           i=2: (4 + 4) % 11 = 8. Slot 8 livre. → slot 8.
Chave 37: h=4. Slot 4 OCUPADO.
           i=1: 5 OCUPADO.
           i=2: 8 OCUPADO.
           i=3: (4 + 9) % 11 = 2. Slot 2 livre. → slot 2.

As colisões a partir do slot 4 vão para slots 5, 8, 2 — distribuição mais espalhada.

O quadratic probing elimina o agrupamento primário, mas pode apresentar agrupamento secundário: duas chaves com o mesmo h(k) seguem exatamente a mesma sequência de sondagem. Além disso, com m não primo ou λ > 0,5, pode-se deixar de sondar todos os slots.

Implementação em C:

/* usa as mesmas definições: LIVRE, OCUPADO, DELETADO e typedef Slot */

void inserirQuad(Slot tab[], int m, int chave) {
    int base = chave % m;   /* slot inicial */
    for (int i = 0; i < m; i++) {
        int pos = (base + i * i) % m;   /* sonda: base, base+1, base+4, base+9, … */
        /* Tanto LIVRE quanto DELETADO servem para inserir:
           uma lápide é um slot reutilizável. */
        if (tab[pos].estado == LIVRE || tab[pos].estado == DELETADO) {
            tab[pos].chave  = chave;
            tab[pos].estado = OCUPADO;
            return;
        }
        if (tab[pos].estado == OCUPADO && tab[pos].chave == chave)
            return;   /* duplicata */
    }   /* falha: λ ≥ 0,5 ou m não primo */
}

int buscarQuad(Slot tab[], int m, int chave) {
    int base = chave % m;
    for (int i = 0; i < m; i++) {
        int pos = (base + i * i) % m;
        if (tab[pos].estado == LIVRE) return -1;
        if (tab[pos].estado == OCUPADO && tab[pos].chave == chave) return pos;
    }
    return -1;
}

void removerQuad(Slot tab[], int m, int chave) {
    int pos = buscarQuad(tab, m, chave);
    if (pos != -1) tab[pos].estado = DELETADO;
}

5. Endereçamento aberto — Double Hashing

O double hashing é o método mais sofisticado de sondagem aberta. Em vez de usar um deslocamento fixo ou quadrático, o próprio passo de sondagem é calculado por uma segunda função de hash:

h(k, i) = (h1(k) + i · h2(k)) % m

Requisito: h2(k) deve ser primo com m entre si (sem divisores comuns além de 1).
Forma comum quando m é primo: h2(k) = 1 + (k % (m − 2))

Como o passo de sondagem h2(k) varia de chave para chave, dois elementos com o mesmo h1(k) seguirão sequências de sondagem diferentes — eliminando tanto o agrupamento primário quanto o secundário.

Exemplo — m = 11, h1(k) = k % 11, h2(k) = 1 + (k % 9):

Inserir 22: h1=22%11=0. h2=1+(22%9)=1+4=5.
            i=0: slot 0 livre. → slot 0.

Inserir 33: h1=33%11=0. h2=1+(33%9)=1+6=7.
            i=0: slot 0 OCUPADO.
            i=1: (0 + 1·7) % 11 = 7. Slot 7 livre. → slot 7.

Inserir 44: h1=44%11=0. h2=1+(44%9)=1+8=9.
            i=0: slot 0 OCUPADO.
            i=1: (0 + 1·9) % 11 = 9. Slot 9 livre. → slot 9.

Três chaves com h1=0, mas cada uma vai para um slot diferente (0, 7, 9)
porque cada uma tem um passo h2 diferente (5, 7, 9).
Com linear probing, as três formariam um bloco em 0, 1, 2.

Implementação em C:

/* usa as mesmas definições: LIVRE, OCUPADO, DELETADO e typedef Slot */

/* h1: slot inicial (onde a chave "deveria" estar) */
static int h1(int k, int m) { return k % m; }
/* h2: passo de sondagem — sempre ≥ 1 e primo com m entre si (garante visitar todos os slots) */
static int h2(int k, int m) { return 1 + (k % (m - 2)); }

void inserirDouble(Slot tab[], int m, int chave) {
    int base = h1(chave, m);   /* slot de partida */
    int step = h2(chave, m);   /* passo: varia por chave, eliminando agrupamento secundário */
    for (int i = 0; i < m; i++) {
        int pos = (base + i * step) % m;   /* sonda: base, base+step, base+2·step, … */
        if (tab[pos].estado == LIVRE || tab[pos].estado == DELETADO) {
            tab[pos].chave  = chave;
            tab[pos].estado = OCUPADO;
            return;
        }
        if (tab[pos].estado == OCUPADO && tab[pos].chave == chave)
            return;   /* duplicata */
    }
}

int buscarDouble(Slot tab[], int m, int chave) {
    int base = h1(chave, m);
    int step = h2(chave, m);
    for (int i = 0; i < m; i++) {
        int pos = (base + i * step) % m;
        if (tab[pos].estado == LIVRE) return -1;
        if (tab[pos].estado == OCUPADO && tab[pos].chave == chave) return pos;
    }
    return -1;
}

void removerDouble(Slot tab[], int m, int chave) {
    int pos = buscarDouble(tab, m, chave);
    if (pos != -1) tab[pos].estado = DELETADO;
}

main de demonstração — endereçamento aberto:

/* Compilar: gcc -Wall -o demo demo.c -lm  (inclua os três blocos acima) */

int main(void) {
    int m = 11;   /* primo — usado pelas três estratégias */
    Slot lin[11], quad[11], dbl[11];
    for (int i = 0; i < m; i++)
        lin[i].estado = quad[i].estado = dbl[i].estado = LIVRE;

    /* --- Sondagem linear --- */
    inserirLinear(lin, m, 10);  inserirLinear(lin, m, 21);  inserirLinear(lin, m, 32);
    printf("[linear] buscar(21) = slot %d\n", buscarLinear(lin, m, 21));   /* 10 */
    removerLinear(lin, m, 21);
    printf("[linear] buscar(32) apos remover 21 = slot %d\n",
           buscarLinear(lin, m, 32));   /* ainda alcançável — lápide preserva cadeia */

    /* --- Sondagem quadrática --- */
    inserirQuad(quad, m,  4);   /* slot 4 */
    inserirQuad(quad, m, 15);   /* slot 5  (i=1 → +1) */
    inserirQuad(quad, m, 26);   /* slot 8  (i=2 → +4) */
    printf("[quad]   buscar(26) = slot %d\n", buscarQuad(quad, m, 26));    /* 8 */
    removerQuad(quad, m, 15);
    printf("[quad]   buscar(26) apos remover 15 = slot %d\n",
           buscarQuad(quad, m, 26));   /* ainda 8 */

    /* --- Hash duplo --- */
    inserirDouble(dbl, m, 22);   /* h1=0, h2=5 → slot 0 */
    inserirDouble(dbl, m, 33);   /* h1=0, h2=7 → slot 7 */
    inserirDouble(dbl, m, 44);   /* h1=0, h2=9 → slot 9 */
    printf("[double] buscar(33) = slot %d\n", buscarDouble(dbl, m, 33));   /* 7 */
    removerDouble(dbl, m, 22);
    printf("[double] buscar(33) apos remover 22 = slot %d\n",
           buscarDouble(dbl, m, 33));   /* ainda 7 — passo de 33 é independente de 22 */

    return 0;
}

6. Fator de carga e rehashing

O fator de carga λ = n/m é o principal indicador de saúde de uma tabela hash. Ele determina diretamente o desempenho médio de busca:

Para λ = 0,9 (tabela 90% cheia), linear probing exige ≈ 50 sondagens em caso de insucesso, enquanto double hashing exige ≈ 10. O crescimento do linear probing é quadrático em 1/(1−λ); o do double hashing é linear — uma diferença enorme próximo de λ = 1.

Limiares práticos recomendados:

Rehashing:

Quando λ ultrapassa o limiar, a tabela deve ser redimensionada. O processo:

1. Aloca uma nova tabela de tamanho m' ≈ 2m (preferencialmente o próximo primo acima de 2m).
2. Para cada elemento existente, recalcula h(k) com o novo m' e reinsere.
3. Descarta a tabela antiga.

Custo: O(n) por rehash. Amortizado ao longo de todas as inserções, cada inserção custa O(1) amortizado — o mesmo argumento usado para vetores dinâmicos (ArrayList).

7. Comparação dos métodos

Resumo das escolhas práticas:

• Encadeamento — preferido quando n é desconhecido ou variável, quando remoções são frequentes, ou quando a simplicidade de implementação é prioritária.
• Linear probing — melhor desempenho de cache; use apenas com λ < 0,5 para controlar o agrupamento primário.
• Double hashing — melhor método de endereçamento aberto na prática; boa performance até λ ≈ 0,7 sem agrupamento significativo.

Resumo

Exercícios

1. Dada uma tabela com m = 7 e h(k) = k % 7, insira as chaves 14, 21, 7, 3, 35, 10 usando encadeamento separado. Desenhe a tabela final com as listas em cada slot.
2. O que é agrupamento primário (primary clustering)? Em qual método de tratamento de colisões ele ocorre? Por que ele piora o desempenho?
3. Dada uma tabela de tamanho m = 11 usando linear probing com h(k) = k % 11, insira as chaves 10, 21, 32 nessa ordem. Em quais posições cada chave é armazenada? Mostre as tentativas de sondagem.
4. Por que não é possível simplesmente apagar um elemento de uma tabela com endereçamento aberto? O que é uma lápide (tombstone) e como ela resolve o problema? Aponte alguma desvantagem do uso de lápides.
5. Uma tabela hash tem m = 100 slots e contém n = 73 elementos. Qual é o fator de carga λ? Esse valor é aceitável para linear probing? Para encadeamento? Justifique.
6. Quando devemos realizar um rehash? Descreva os passos do processo. Qual é o custo de um rehash de uma tabela com n elementos? E o custo amortizado por inserção?
7. Comparando encadeamento e double hashing: qual dos dois tem melhor desempenho de cache? Qual suporta fatores de carga mais altos mantendo boa performance? Justifique ambas as respostas.
8. Uma tabela hash com encadeamento tem m = 5 slots e n = 20 elementos. Assumindo distribuição uniforme, quantos elementos há em média por slot? Qual é o número médio de comparações para encontrar um elemento (incluindo a comparação bem-sucedida)?
9. Considere double hashing com m = 13, h1(k) = k % 13, h2(k) = 1 + (k % 11). Mostre a sequência de slots sondados ao inserir a chave 40, sabendo que os slots 1 e 12 já estão ocupados.

h(k) = k % 7:
  14%7=0, 21%7=0, 7%7=0, 3%7=3, 35%7=0, 10%7=3

slot 0: [35] → [7] → [21] → [14]   (inserções no início da lista)
slot 1: (vazio)
slot 2: (vazio)
slot 3: [10] → [3]
slot 4: (vazio)
slot 5: (vazio)
slot 6: (vazio)

λ = 6/7 ≈ 0,86. Slot 0 tem 4 elementos — busca nesse slot requer até 4 comparações.

Chave 10: h=10%11=10. Slot 10 livre. → slot 10.
Chave 21: h=21%11=10. Slot 10 OCUPADO → tenta slot 0: livre. → slot 0.
Chave 32: h=32%11=10. Slot 10 OCUPADO → slot 0 OCUPADO → tenta slot 1: livre. → slot 1.

Resultado: 10 no slot 10, 21 no slot 0, 32 no slot 1.
Nota: as três chaves possuem o mesmo h(k)=10 e já formam um bloco (10, 0, 1).

Chave 40: h1 = 40 % 13 = 1. h2 = 1 + (40 % 11) = 1 + 7 = 8.

i=0: slot (1 + 0·8) % 13 = 1.   Slot 1 OCUPADO.
i=1: slot (1 + 1·8) % 13 = 9.   Slot 9 livre. → slot 9.

A chave 40 é inserida no slot 9.
(O slot 12 estava ocupado mas nem chegamos a ele — o passo 8 desviou direto para 9.)

Código completo — TAD Tabela Hash

Os arquivos abaixo reúnem o conteúdo das aulas 19 e 20 em um único TAD em C:

• hash.h — declarações: três funções de hash + TabelaEnc (encadeamento) + TabelaLinear, TabelaQuad, TabelaDouble (cada estratégia de endereçamento aberto com sua própria struct).
• hash.c — implementação completa de todas as operações (inserir, buscar, remover, destruir) para cada TAD, com suporte a lápide no endereçamento aberto.
• hash_demo.c — demonstração de funções de hash e encadeamento separado.
• hash_demo_aberto.c — demonstração dos três tipos de endereçamento aberto, com exemplos de colisão e remoção.

Compilar e executar:

gcc -Wall -o hash_demo hash_demo.c hash.c -lm
./hash_demo

gcc -Wall -o hash_demo_aberto hash_demo_aberto.c hash.c -lm
./hash_demo_aberto

↓ Download hash.zip