Estruturas de dados em C/C++

Tabela hash (hash table) em C e C++

Nesta lição, você vai contar quantas vezes cada palavra aparece com uma tabela hash feita à mão em C e com std::unordered_map em C++.

Introdução

Uma tabela hash (hash table) usa uma função hash (hash function) para transformar cada chave no índice de um compartimento (bucket), o que torna busca, inserção e remoção muito rápidas. Quando duas chaves diferentes caem no mesmo compartimento, ocorre uma colisão (collision), e a tabela precisa de uma estratégia como encadeamento (chaining) ou endereçamento aberto (open addressing).

Pontos importantes

Defina as condições que sempre devem ser verdadeiras (invariantes) antes de escrever as operações.
Trate os casos de estrutura vazia, cheia e de falha na alocação de memória.
Avalie ao mesmo tempo a complexidade e o gerenciamento de memória de cada operação.

Veja como funciona

Digite uma chave e guarde ou procure. A chave vira um número de bucket pelo hash, então o programa vai direto ao bucket certo.

Exemplos de código C e C++

Executar →

main.c

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

typedef struct Item {
    const char *key;
    int count;
    struct Item *next;
} Item;

unsigned hash(const char *text) {
    unsigned value = 5381;
    while (*text) {
        value = value * 33u ^ (unsigned char)*text++;
    }
    return value % 5;
}

int main(void) {
    const char *words[] = {"c", "cpp", "c"};
    Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
    Item *buckets[5] = {0};

    for (int index = 0; index < 2; ++index) {
        unsigned bucket = hash(items[index].key);
        items[index].next = buckets[bucket];
        buckets[bucket] = &items[index];
    }
    for (int index = 0; index < 3; ++index) {
        Item *item = buckets[hash(words[index])];
        for (; item; item = item->next) {
            if (strcmp(item->key, words[index]) == 0) {
                ++item->count;
                break;
            }
        }
    }
    printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}

Resultado da execução

c=2 cpp=1

C++

Executar →

main.cpp

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> counts;
    for (const std::string word : {"c", "cpp", "c"}) {
        ++counts[word];
    }
    std::cout << "c=" << counts["c"]
              << " cpp=" << counts["cpp"] << '\n';
}

Resultado da execução

c=2 cpp=1

Comparação entre C e C++

A função hash em C calcula um valor a partir dos caracteres da string e tira o resto da divisão por 5 para escolher um dos 5 buckets. Cada bucket é uma lista ligada, então as palavras que colidem são encadeadas no mesmo bucket. O exemplo em C usa poucas palavras fixas para focar no mecanismo dos buckets. Em C++, std::unordered_map gerencia os nós, cresce quando precisa e aceita qualquer string como chave.

Os dados (struct) e as operações ficam separados, e a memória é alocada e liberada à mão.

C++

Classes e contêineres protegem a consistência dos dados e gerenciam os próprios recursos.

Exercícios práticos

Execute as duas versões e depois mude o código para observar a diferença de segurança que cada linguagem oferece.

Adicione testes para a estrutura vazia e para quando ela atinge a capacidade.
Escreva a liberação de memória e verifique se há vazamentos.
Compare a complexidade com o contêiner equivalente da biblioteca padrão.

Pratique com um desafio

Use o conteúdo desta lição para resolver um problema real. Cada desafio roda no navegador, com testes instantâneos e uma revisão por IA.

Todos os desafios