[406] Tabelas Hash: Busca em Tempo Constante

Fechamos o estudo das estruturas de dados clássicas com a mais engenhosa de todas. A árvore de busca nos deu busca logarítmica — rápida. A tabela hash promete algo ainda mais impressionante: busca em tempo praticamente constante, independentemente de quantos elementos existam. Encontrar um item entre dez ou entre dez milhões custa quase o mesmo. Como isso é possível? Através de uma ideia brilhante: em vez de procurar onde um dado está, nós calculamos onde ele deveria estar. Esta aula reúne vetores, listas encadeadas, strings e um toque de criatividade — uma síntese digna de encerrar a Fase 5.

A ideia central: calcular a posição

Nas estruturas anteriores, para encontrar um valor, precisávamos percorrer nós ou descer ramos. A tabela hash inverte isso. Ela usa uma função hash — uma função que transforma uma chave (um texto, um número) em um índice de vetor. A mágica é: se a mesma chave sempre produz o mesmo índice, então podemos ir direto à posição onde o dado mora, sem procurar. Guardar e buscar viram um cálculo, não uma busca.

Imagine um vetor de 100 posições. Para guardar o valor associado à chave "Ana", calculamos hash("Ana"), que devolve, digamos, 42. Guardamos o dado na posição 42. Para buscá-lo depois, calculamos hash("Ana") de novo — que devolve 42 outra vez — e vamos direto à posição 42. Nenhum percurso, nenhuma comparação sequencial: o índice é computado a partir da própria chave.

Uma função hash simples para strings

A função hash é o coração da estrutura. Ela precisa transformar uma chave em um índice dentro dos limites do vetor, distribuindo as chaves o mais uniformemente possível. Uma função clássica e simples para strings soma valores derivados de seus caracteres:

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

#define TAMANHO 100

unsigned int hash(const char *chave) {
    unsigned int soma = 0;
    for (int i = 0; chave[i] != '\0'; i++) {
        soma = soma * 31 + chave[i]; // combina cada caractere
    }
    return soma % TAMANHO; // garante índice entre 0 e TAMANHO-1
}

int main(void) {
    printf("hash(\"Ana\")   = %u\n", hash("Ana"));
    printf("hash(\"Bruno\") = %u\n", hash("Bruno"));
    printf("hash(\"Ana\")   = %u\n", hash("Ana")); // mesmo resultado da 1ª vez!
    return 0;
}

A função percorre a string combinando cada caractere numa soma (o multiplicador 31 é uma escolha clássica que ajuda a espalhar os valores). O % TAMANHO final é essencial: ele "dobra" qualquer número grande para dentro da faixa válida de índices do vetor, de 0 a 99. E note a propriedade fundamental, visível na saída: hash("Ana") produz sempre o mesmo valor. É esse determinismo que permite guardar e reencontrar: você calcula o mesmo índice toda vez para a mesma chave.

O problema inevitável: colisões

Há um obstáculo que toda tabela hash enfrenta. Como comprimimos infinitas chaves possíveis em um número finito de posições (aqui, 100), é inevitável que duas chaves diferentes acabem produzindo o mesmo índice. Isso se chama colisão. Se "Ana" e "Carlos" ambas mapeiam para a posição 42, o que fazemos? Não podemos simplesmente sobrescrever uma com a outra. Lidar com colisões é o desafio central de qualquer implementação de tabela hash, e há duas estratégias principais.

Encadeamento: uma lista em cada posição

A estratégia mais comum e intuitiva chama-se encadeamento (chaining), e aqui reaproveitamos as listas encadeadas da aula Listas Encadeadas: A Estrutura que Só Existe com Ponteiros. Em vez de cada posição do vetor guardar um único elemento, ela guarda uma lista encadeada de todos os elementos que colidiram naquele índice:

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

#define TAMANHO 100

typedef struct No {
    char chave[50];
    int valor;
    struct No *proximo; // encadeia colisões no mesmo índice
} No;

typedef struct {
    No *baldes[TAMANHO]; // vetor de listas (os "baldes")
} TabelaHash;

unsigned int hash(const char *chave) {
    unsigned int soma = 0;
    for (int i = 0; chave[i] != '\0'; i++) {
        soma = soma * 31 + chave[i];
    }
    return soma % TAMANHO;
}

void inicializar(TabelaHash *t) {
    for (int i = 0; i < TAMANHO; i++) {
        t->baldes[i] = NULL; // todas as listas começam vazias
    }
}

// insere (ou atualiza) uma chave e seu valor
void inserir(TabelaHash *t, const char *chave, int valor) {
    unsigned int i = hash(chave);

    // procura se a chave já existe neste balde
    for (No *n = t->baldes[i]; n != NULL; n = n->proximo) {
        if (strcmp(n->chave, chave) == 0) {
            n->valor = valor; // já existe: atualiza
            return;
        }
    }

    // não existe: cria um novo nó no início da lista deste balde
    No *novo = malloc(sizeof(No));
    if (novo == NULL) return;
    strcpy(novo->chave, chave);
    novo->valor = valor;
    novo->proximo = t->baldes[i];
    t->baldes[i] = novo;
}

Cada posição do vetor é chamada de balde (bucket), e contém a cabeça de uma lista encadeada. Ao inserir, calculamos o índice, vamos ao balde correspondente, e adicionamos o elemento àquela lista (verificando antes se a chave já existe, para atualizar em vez de duplicar). Quando duas chaves colidem, elas simplesmente convivem na mesma lista. É uma combinação elegante das duas estruturas: o vetor dá acesso direto ao balde, e a lista absorve as colisões.

Buscando na tabela

A busca espelha a inserção: calcula o índice, vai ao balde, e percorre a pequena lista daquele balde procurando a chave exata:

// busca o valor associado a uma chave; retorna via ponteiro
int buscar(TabelaHash *t, const char *chave, int *valor) {
    unsigned int i = hash(chave);

    for (No *n = t->baldes[i]; n != NULL; n = n->proximo) {
        if (strcmp(n->chave, chave) == 0) {
            *valor = n->valor; // encontrou
            return 1;
        }
    }
    return 0; // não encontrado
}

int main(void) {
    TabelaHash tabela;
    inicializar(&tabela);

    inserir(&tabela, "Ana", 30);
    inserir(&tabela, "Bruno", 25);
    inserir(&tabela, "Carla", 35);

    int idade;
    if (buscar(&tabela, "Bruno", &idade)) {
        printf("Bruno tem %d anos.\n", idade); // 25
    }
    if (!buscar(&tabela, "Diego", &idade)) {
        printf("Diego não encontrado.\n");
    }
    return 0;
}

Aqui está por que a busca é tão rápida. Vamos direto ao balde certo pelo cálculo do hash (um passo), e então percorremos apenas a pequena lista daquele balde específico — não todos os elementos da tabela, apenas os poucos que colidiram naquele índice. Se a função hash distribui bem e a tabela não está lotada, cada balde tem zero, um ou dois elementos, e a busca é praticamente instantânea. É essa combinação — acesso direto ao balde mais lista curta — que dá o "tempo constante" prometido.

Por que "praticamente" constante

Preciso ser honesto sobre esse "praticamente". A busca em tempo constante depende de duas condições. Primeiro, uma boa função hash, que espalhe as chaves uniformemente pelos baldes — uma função ruim que jogasse tudo no mesmo balde transformaria a tabela numa única lista longa, com busca linear. Segundo, um fator de carga razoável: se você guardar muito mais elementos do que o vetor comporta, os baldes ficam com listas longas e a eficiência degrada. Implementações profissionais lidam com isso redimensionando a tabela (aumentando o vetor e redistribuindo os elementos) quando ela fica cheia demais. Com esses cuidados, a tabela hash entrega, na média, a busca constante que a torna a estrutura preferida para dicionários, caches e índices. Sem eles, ela degenera. Como sempre, conhecer as condições de bom funcionamento é parte de usar a ferramenta com maestria.

Comparando as estruturas da Fase 5

Vale um panorama de tudo que construímos. A lista encadeada é flexível para inserção/remoção, mas busca é linear. A árvore de busca oferece busca logarítmica e mantém os dados ordenados (útil quando a ordem importa). A tabela hash dá a busca mais rápida — praticamente constante —, mas não mantém ordem alguma (percorrer os baldes devolve os elementos em ordem imprevisível). Não existe estrutura perfeita: a tabela hash vence em velocidade de busca pura, a árvore vence quando você precisa de ordenação junto com busca eficiente, a lista vence em simplicidade e inserção. Escolher entre elas conforme as necessidades do problema — busca? ordem? memória? — é a marca de quem realmente entende estruturas de dados, e não apenas as memoriza.

Liberando a tabela

Como cada balde é uma lista de nós alocados, liberar a tabela significa liberar cada lista — reaplicando a disciplina da aula Listas Encadeadas: A Estrutura que Só Existe com Ponteiros a cada balde:

void liberar(TabelaHash *t) {
    for (int i = 0; i < TAMANHO; i++) {
        No *atual = t->baldes[i];
        while (atual != NULL) {
            No *proximo = atual->proximo; // guarda antes de liberar
            free(atual);
            atual = proximo;
        }
        t->baldes[i] = NULL;
    }
}

Percorremos cada um dos baldes e, dentro de cada um, liberamos sua lista nó por nó — com o mesmo cuidado de guardar o proximo antes do free, evitando o use-after-free. Toda a memória alocada nas inserções é assim devolvida.

Fechando a Fase 5

Com a tabela hash, encerramos a fase de algoritmos e estruturas de dados. Você percorreu um caminho notável: da recursão às listas encadeadas (simples, duplas, circulares), às pilhas e filas, à árvore de busca hierárquica, e agora à tabela hash de busca constante. Mais importante que cada estrutura isolada, você aprendeu a pensar sobre elas — a avaliar custos, escolher a certa para cada problema, e implementá-la do zero com ponteiros e memória dinâmica. Na próxima fase, mudamos de foco: em vez de escrever mais código, vamos aprender a trabalhar como profissionais. Começamos com o GDB, o depurador que permite parar seu programa, inspecionar variáveis e caçar bugs de dentro — a ferramenta que transforma a depuração de adivinhação em investigação.

Fontes e leituras recomendadas

• The C Programming Language (K&R), Kernighan & Ritchie — Cap. 6.6, com uma implementação de tabela hash
• Algorithms, Robert Sedgewick — capítulo sobre hash tables
• Introduction to Algorithms (CLRS) — Cap. 11, Hash Tables
• The Art of Computer Programming, Vol. 3, Donald Knuth — tratamento profundo de hashing
• Visualização interativa de tabelas hash — https://www.cs.usfca.edu/~galles/visualization/OpenHash.html

Exercícios

Exercício 1

Implemente a função hash do artigo e teste-a com cinco chaves diferentes, imprimindo o índice de cada uma. Verifique se alguma colide (produz o mesmo índice). Depois, reduza TAMANHO para 5 e observe como as colisões ficam muito mais frequentes.

#include <stdio.h>
#include <string.h>
#define TAMANHO 100
unsigned int hash(const char *chave) {
    unsigned int soma = 0;
    for (int i = 0; chave[i] != '\0'; i++) soma = soma * 31 + chave[i];
    return soma % TAMANHO;
}
int main(void) {
    const char *chaves[] = {"Ana", "Bruno", "Carla", "Diego", "Ester"};
    for (int i = 0; i < 5; i++)
        printf("hash(\"%s\") = %u\n", chaves[i], hash(chaves[i]));
    return 0;
}

Exercício 2

Usando a TabelaHash do artigo, insira cinco pares chave/valor (nomes e idades) e busque três: dois que existem e um que não existe. Imprima os resultados.

int main(void) {
    TabelaHash t;
    inicializar(&t);
    inserir(&t, "Ana", 30);
    inserir(&t, "Bruno", 25);
    inserir(&t, "Carla", 35);
    inserir(&t, "Diego", 28);
    inserir(&t, "Ester", 40);

    int idade;
    const char *procurar[] = {"Bruno", "Ester", "Fabio"};
    for (int i = 0; i < 3; i++) {
        if (buscar(&t, procurar[i], &idade))
            printf("%s: %d anos\n", procurar[i], idade);
        else
            printf("%s: não encontrado\n", procurar[i]);
    }
    liberar(&t);
    return 0;
}

Exercício 3

Escreva uma função void imprimir_tabela(TabelaHash *t) que percorra todos os baldes e imprima, para cada balde não vazio, seu índice e todas as chaves ali armazenadas. Isso permite visualizar as colisões.

void imprimir_tabela(TabelaHash *t) {
    for (int i = 0; i < TAMANHO; i++) {
        if (t->baldes[i] != NULL) {
            printf("Balde %d: ", i);
            for (No *n = t->baldes[i]; n != NULL; n = n->proximo) {
                printf("%s ", n->chave);
            }
            printf("\n");
        }
    }
}

Exercício 4

Explique, com suas palavras, o que é uma colisão numa tabela hash e por que ela é inevitável. Descreva como a estratégia de encadeamento (chaining) resolve o problema.

Exercício 5

Compare a tabela hash com a árvore binária de busca da aula anterior. Cite uma vantagem da tabela hash sobre a árvore e uma vantagem da árvore sobre a tabela hash. Em que situação você escolheria cada uma?