C Academy · Aula

Tratamento de colisões

Encadeamento e sondagem.

Tratamento de colisões é uma aula grátis de C Academy no CoddyKit. Esta é a aula 2 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de C Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de C Academy inclui 4 aulas no total.

O problema das colisões

Uma colisão ocorre quando duas chaves distintas produzem o mesmo compartimento. Como as colisões são inevitáveis, toda tabela de dispersão precisa de uma estratégia para armazenar várias chaves em uma única posição.

As duas principais famílias são o encadeamento e o endereçamento aberto.

Encadeamento separado

Com o encadeamento separado, cada compartimento contém uma lista encadeada de entradas. Em caso de colisão, basta anexar (ou antepor) a entrada à lista desse compartimento.

Os compartimentos armazenam os primeiros nós das listas
As buscas percorrem uma única lista curta

Estrutura do nó de encadeamento

Cada nó armazena uma chave, um valor e um ponteiro next. A tabela é um vetor de ponteiros para nós.

#include <stdio.h>

typedef struct Node {
    char *key;
    int value;
    struct Node *next;
} Node;

int main(void) {
    Node *buckets[8] = {0};
    printf("slots = %zu\n", sizeof buckets / sizeof buckets[0]);
    return 0;
}

Inserção com encadeamento

Antepor um elemento à lista do compartimento custa O(1). Aqui construímos manualmente uma pequena cadeia e a exibimos.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node { int key; struct Node *next; } Node;

Node *prepend(Node *head, int key) {
    Node *n = malloc(sizeof *n);
    n->key = key; n->next = head;
    return n;
}

int main(void) {
    Node *bucket = NULL;
    bucket = prepend(bucket, 10);
    bucket = prepend(bucket, 26); /* same bucket as 10 mod 8 */
    for (Node *p = bucket; p; p = p->next)
        printf("%d ", p->key);
    printf("\n");
    return 0;
}

Endereçamento aberto

Com o endereçamento aberto, cada entrada vive diretamente no vetor de compartimentos. Em caso de colisão, você sonda outra posição vazia usando uma sequência fixa.

Nenhum nó extra é alocado, o que favorece o uso do cache.

Sondagem linear

A sondagem linear verifica a próxima posição, depois a seguinte, dando a volta ao chegar ao fim: (h + i) % capacity.

Ela é simples e favorece o uso do cache, mas sofre com agrupamento.

#include <stdio.h>

int main(void) {
    int slots[8] = {0,0,1,0,0,0,0,0}; /* slot 2 taken */
    unsigned h = 2, cap = 8;
    for (unsigned i = 0; i < cap; i++) {
        unsigned idx = (h + i) % cap;
        if (!slots[idx]) { printf("insert at %u\n", idx); break; }
    }
    return 0;
}

Sondagem quadrática

A sondagem quadrática usa (h + i*i) % capacity para distribuir as sondagens e reduzir o agrupamento primário.

#include <stdio.h>

int main(void) {
    unsigned h = 3, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h + i*i) % cap);
    return 0;
}

Hash duplo

O hash duplo usa um segundo hash para o tamanho do passo: (h1 + i*h2) % capacity. Isso fornece a cada chave sua própria sequência de sondagem e a melhor distribuição das três.

#include <stdio.h>

int main(void) {
    unsigned h1 = 3, h2 = 5, cap = 8;
    for (unsigned i = 0; i < 4; i++)
        printf("probe %u -> slot %u\n", i, (h1 + i*h2) % cap);
    return 0;
}

Exclusão no endereçamento aberto

Você não pode simplesmente limpar uma posição no endereçamento aberto, pois isso romperia as cadeias de sondagem de outras chaves. Em vez disso, marque-a com um marcador de exclusão para que as buscas continuem sondando além dela.

Encadeamento versus endereçamento aberto

Compromissos:

Encadeamento: lida com fatores de carga altos e permite exclusões simples, mas usa ponteiros e alocações
Endereçamento aberto: favorece o uso do cache e não exige alocação por entrada, mas degrada acentuadamente quando a tabela está quase cheia e precisa de marcadores de exclusão

Demonstração da quantidade de sondagens

A sondagem linear pode precisar de várias etapas quando as posições ficam agrupadas. Aqui contamos as sondagens necessárias para encontrar uma posição livre.

#include <stdio.h>

int main(void) {
    int slots[8] = {1,1,1,0,0,0,0,0};
    unsigned h = 0, cap = 8, probes = 0;
    for (unsigned i = 0; i < cap; i++) {
        probes++;
        if (!slots[(h + i) % cap]) break;
    }
    printf("probes used = %u\n", probes);
    return 0;
}

Verificação rápida

Teste seus conhecimentos sobre tratamento de colisões.

Recapitulação

Você explorou como as tabelas hash resolvem colisões.

O encadeamento armazena uma lista encadeada por compartimento
O endereçamento aberto sonda uma posição livre
Variações de sondagem: linear, quadrática e hash duplo
O endereçamento aberto precisa de marcadores de exclusão para realizar exclusões

Perguntas Frequentes

A aula “Tratamento de colisões” é grátis?

Sim — o texto completo de “Tratamento de colisões” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de C Academy, atualize para CoddyKit PRO. O curso de C Academy inclui 4 aulas no total.

O que vou aprender em “Tratamento de colisões”?

Encadeamento e sondagem. Você pratica C Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.

Preciso ter experiência prévia para começar C Academy?

Nenhuma experiência prévia é necessária. C Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 2 de 4.

Quanto tempo leva a aula “Tratamento de colisões”?

A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.

Posso escrever e executar código nesta aula de C Academy?

Sim. Cada aula de C Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.

Todas as aulas deste curso

← Voltar para C Academy