0Pricing
C Academy · Aula

Inserir, buscar e excluir

Operações fundamentais.

Inserir, buscar e excluir é uma aula grátis de C Academy no CoddyKit. Esta é a aula 3 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.

As três operações principais

Toda tabela hash oferece três operações: inserir, buscar e excluir. Com um bom hash e um fator de carga razoável, as três são executadas em tempo médio O(1).

Construiremos passo a passo uma tabela baseada em encadeamento.

Os tipos de tabela e de nó

Definimos um nó que contém uma cadeia de caracteres de chave copiada e um valor inteiro, além de uma estrutura de tabela que contém o vetor de compartimentos e sua capacidade.

#include <stdio.h>

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

typedef struct {
    Node **buckets;
    unsigned capacity;
    unsigned size;
} HashTable;

int main(void) {
    printf("types defined\n");
    return 0;
}

Criando a tabela

Alocamos a tabela e um vetor de compartimentos zerado com calloc, para que cada compartimento comece como NULL.

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

typedef struct Node { char *key; int value; struct Node *next; } Node;
typedef struct { Node **buckets; unsigned capacity, size; } HashTable;

HashTable *ht_create(unsigned cap) {
    HashTable *t = malloc(sizeof *t);
    t->buckets = calloc(cap, sizeof(Node *));
    t->capacity = cap; t->size = 0;
    return t;
}

int main(void) {
    HashTable *t = ht_create(16);
    printf("capacity=%u size=%u\n", t->capacity, t->size);
    return 0;
}

A função auxiliar de hash

Reutilizamos o DJB2 e o reduzimos a um índice de compartimento. Essa função auxiliar é usada pelas três operações.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381; int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

unsigned bucket_of(const char *key, unsigned cap) {
    return (unsigned)(djb2(key) % cap);
}

int main(void) {
    printf("%u\n", bucket_of("name", 16));
    return 0;
}

Inserir: atualizar ou antepor

Ao inserir, primeiro pesquise no compartimento. Se a chave existir, atualize seu valor. Caso contrário, aloque um novo nó (com uma chave copiada por meio de strdup) e anteponha-o.

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

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

Node *insert(Node *head, const char *key, int val) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) { p->value = val; return head; }
    Node *n = malloc(sizeof *n);
    n->key = strdup(key); n->value = val; n->next = head;
    return n;
}

int main(void) {
    Node *b = NULL;
    b = insert(b, "a", 1);
    b = insert(b, "a", 99); /* update */
    printf("%s=%d\n", b->key, b->value);
    return 0;
}

Busca

A busca calcula o hash da chave e percorre a lista do compartimento, comparando as chaves com strcmp. Ela retorna um ponteiro para o valor (ou NULL se ele não existir).

#include <stdio.h>
#include <string.h>

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

int *lookup(Node *head, const char *key) {
    for (Node *p = head; p; p = p->next)
        if (strcmp(p->key, key) == 0) return &p->value;
    return NULL;
}

int main(void) {
    Node n2 = {"y", 20, NULL};
    Node n1 = {"x", 10, &n2};
    int *v = lookup(&n1, "y");
    printf("%d\n", v ? *v : -1);
    return 0;
}

Excluir: religar a lista

A exclusão percorre o compartimento mantendo um ponteiro para o nó anterior, depois religa a lista ao redor do alvo e o libera (tanto a chave copiada quanto o nó).

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

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

Node *delete_key(Node *head, const char *key) {
    Node *prev = NULL, *cur = head;
    while (cur) {
        if (strcmp(cur->key, key) == 0) {
            if (prev) prev->next = cur->next; else head = cur->next;
            free(cur->key); free(cur);
            return head;
        }
        prev = cur; cur = cur->next;
    }
    return head;
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("a"); b->value = 1; b->next = NULL;
    b = delete_key(b, "a");
    printf("%s\n", b ? "left" : "empty");
    return 0;
}

Unindo tudo

Uma tabela completa encapsula essas operações calculando o compartimento e delegando o trabalho às funções auxiliares da lista. Aqui está uma pequena tabela completa em ação.

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

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

unsigned long djb2(const char *s){unsigned long h=5381;int c;while((c=(unsigned char)*s++))h=((h<<5)+h)+c;return h;}

#define CAP 16
Node *table[CAP];

void put(const char *k, int v) {
    unsigned i = djb2(k) % CAP;
    Node *n = malloc(sizeof *n);
    n->key = strdup(k); n->value = v; n->next = table[i];
    table[i] = n;
}
int get(const char *k) {
    for (Node *p = table[djb2(k) % CAP]; p; p = p->next)
        if (!strcmp(p->key, k)) return p->value;
    return -1;
}

int main(void) {
    put("age", 30); put("score", 95);
    printf("age=%d score=%d\n", get("age"), get("score"));
    return 0;
}

Por que copiar a chave

Armazenamos as chaves com strdup para que a tabela mantenha sua própria cópia. Se armazenássemos o ponteiro fornecido pelo chamador, a chave poderia ser alterada ou liberada enquanto ainda a usássemos, corrompendo as buscas.

Isso também significa que a exclusão deve usar free na chave copiada.

Complexidade temporal

Com um hash uniforme e um fator de carga mantido próximo de 0.75:

  • Inserção: O(1) em média
  • Busca: O(1) em média
  • Exclusão: O(1) em média

O pior caso é O(n), quando todas as chaves colidem em um único compartimento.

Liberando a tabela inteira

Para evitar vazamentos, libere cada nó de cada compartimento, depois o vetor de compartimentos e, por fim, a estrutura da tabela.

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

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

void free_bucket(Node *head) {
    while (head) { Node *nx = head->next; free(head->key); free(head); head = nx; }
}

int main(void) {
    Node *b = malloc(sizeof *b);
    b->key = strdup("k"); b->value = 1; b->next = NULL;
    free_bucket(b);
    printf("freed\n");
    return 0;
}

Verificação rápida

Teste sua compreensão das operações principais.

Recapitulação

Você implementou as três operações principais de uma tabela hash com encadeamento.

  • A inserção atualiza ou antepõe um nó
  • A busca percorre a lista do compartimento com strcmp
  • A exclusão religa a lista e libera a chave e o nó
  • Mantenha suas próprias chaves com strdup e libere tudo ao desmontar a tabela

Perguntas Frequentes

A aula “Inserir, buscar e excluir” é grátis?

Sim — o texto completo de “Inserir, buscar e excluir” é 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 “Inserir, buscar e excluir”?

Operações fundamentais. 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 3 de 4.

Quanto tempo leva a aula “Inserir, buscar e excluir”?

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

  1. Funções de hash
  2. Tratamento de colisões
  3. Inserir, buscar e excluir
  4. Redimensionamento e fator de carga
← Voltar para C Academy