Tabelas hash (introdução)

Bem-vindo à aula sobre tabelas hash em C! Nesta aula, vamos explorar um dos conceitos mais importantes e utilizados em ciência da computação: a tabela hash. Ela permite armazenar e recuperar dados de forma extremamente eficiente, com tempo médio de busca constante O(1). Vamos entender como funciona, quais são os desafios (como colisões) e como implementar uma versão simples em C.

Vamos começar com o conceito fundamental, depois discutir funções hash, colisões e, por fim, construir uma implementação prática. Ao final, você terá uma base sólida para avançar em estruturas de dados mais complexas.

Conceito

Uma tabela hash é uma estrutura de dados que associa chaves a valores, permitindo operações de inserção, busca e remoção em tempo médio O(1). Ela funciona utilizando uma função hash que transforma uma chave (como uma string, número, etc.) em um índice de um array. Esse array é chamado de tabela ou buckets.

Imagine que você tem um array de tamanho N. Para armazenar um par chave-valor, calculamos o índice i = hash(chave) % N e armazenamos o valor na posição i. Para buscar, repetimos o processo: calculamos o hash da chave e acessamos diretamente a posição. Isso elimina a necessidade de percorrer toda a estrutura, como em listas ou arrays não ordenados.

No entanto, a eficiência depende de uma boa função hash e de uma gestão adequada de colisões. Se duas chaves diferentes resultarem no mesmo índice, temos uma colisão, que precisa ser tratada. Vamos entender isso melhor nas próximas seções.

Função hash

A função hash é o coração da tabela hash. Ela deve ser rápida, determinística (mesma chave sempre gera o mesmo valor) e distribuir as chaves uniformemente pelo array para minimizar colisões. Uma função hash ruim pode fazer com que muitas chaves caiam no mesmo índice, degradando a performance para O(n).

Em C, para chaves inteiras, uma função simples é retornar a própria chave (ou uma operação aritmética). Para strings, usamos algoritmos como o djb2 ou FNV-1a. Vamos ver um exemplo de função hash para strings:

unsigned long hash_djb2(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash;
}

Essa função é amplamente utilizada por sua simplicidade e boa distribuição. O número 5381 e o fator 33 são escolhidos empiricamente para reduzir colisões. Após calcular o hash, normalmente aplicamos o módulo pelo tamanho da tabela para obter um índice válido.

É importante que o tamanho da tabela seja um número primo para melhor distribuição, mas isso é uma regra prática, não obrigatória.

Colisões

Colisões ocorrem quando duas chaves diferentes produzem o mesmo índice. Como cada posição do array só pode armazenar um elemento, precisamos de uma estratégia para lidar com isso. As duas abordagens mais comuns são:

• Encadeamento separado: cada bucket contém uma lista ligada (ou outra estrutura) com todos os elementos que mapeiam para aquele índice.
• Endereçamento aberto: quando ocorre uma colisão, procuramos outra posição livre na tabela (por exemplo, teste linear, quadrático, ou duplo hash).

Nesta aula, focaremos no encadeamento separado por ser mais simples de implementar e entender. Cada bucket é um ponteiro para o início de uma lista ligada. Quando inserimos, adicionamos no início da lista. Na busca, percorremos a lista até encontrar a chave.

A eficiência média continua O(1) se o fator de carga (número de elementos / tamanho da tabela) for mantido baixo (geralmente < 0.7). Se a lista ficar muito longa, a busca degrada.

Implementação simples

Vamos implementar uma tabela hash em C com encadeamento separado. Primeiro, definimos a estrutura do nó e da tabela:

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

#define TABLE_SIZE 10

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

typedef struct HashTable {
    Node **buckets; // array de ponteiros para nós
} HashTable;

Agora, funções para criar, inserir, buscar e destruir a tabela:

// Função hash djb2
unsigned long hash_djb2(const char *str) {
    unsigned long hash = 5381;
    int c;
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c;
    }
    return hash;
}

// Cria uma nova tabela
HashTable *create_table() {
    HashTable *table = malloc(sizeof(HashTable));
    if (!table) return NULL;
    table->buckets = calloc(TABLE_SIZE, sizeof(Node *));
    if (!table->buckets) { free(table); return NULL; }
    return table;
}

// Insere um par chave-valor
void insert(HashTable *table, const char *key, int value) {
    unsigned long index = hash_djb2(key) % TABLE_SIZE;
    Node *new_node = malloc(sizeof(Node));
    new_node->key = strdup(key);
    new_node->value = value;
    new_node->next = table->buckets[index];
    table->buckets[index] = new_node;
}

// Busca um valor pela chave
int search(HashTable *table, const char *key) {
    unsigned long index = hash_djb2(key) % TABLE_SIZE;
    Node *node = table->buckets[index];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return -1; // não encontrado
}

// Libera a memória
void free_table(HashTable *table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Node *node = table->buckets[i];
        while (node) {
            Node *temp = node;
            node = node->next;
            free(temp->key);
            free(temp);
        }
    }
    free(table->buckets);
    free(table);
}

// Exemplo de uso
int main() {
    HashTable *table = create_table();
    insert(table, "nome", 42);
    insert(table, "idade", 30);
    printf("nome: %d\n", search(table, "nome"));
    printf("idade: %d\n", search(table, "idade"));
    printf("não existe: %d\n", search(table, "cpf"));
    free_table(table);
    return 0;
}

Essa implementação é simples e didática. Observe que a inserção sempre adiciona no início da lista, então a ordem não é preservada. A busca percorre a lista até encontrar a chave. A função strdup é usada para copiar a chave, mas lembre-se de que ela não é padrão C (é POSIX); em alguns compiladores, pode ser necessário implementar manualmente.

Em uma implementação real, você também consideraria redimensionamento dinâmico, remoção, e melhor tratamento de erros.

Boas práticas e observações

Ao trabalhar com tabelas hash, considere:

• Escolha um tamanho de tabela adequado e, se necessário, redimensione dinamicamente para manter o fator de carga aceitável.
• Use uma função hash de boa qualidade para evitar muitas colisões.
• Libere sempre a memória alocada para evitar vazamentos.
• Em aplicações críticas, considere usar bibliotecas padrão como uthash ou implementações da glibc, pois são mais robustas.

As tabelas hash são amplamente usadas em bancos de dados, caches, dicionários e compiladores. Dominá-las é essencial para qualquer programador.

Referências

• cppreference - Struct
• Wikipedia - Tabela hash
• GeeksforGeeks - Hashing
• Yale - Notas de aula sobre hash
• IME USP - Tabelas de dispersão
• uthash - Biblioteca hash para C

Exercícios

1. Implemente uma função hash para chaves inteiras que retorne o próprio valor e use-a em uma tabela hash simples.

Ver resposta

✓ Resposta: Para inteiros, a função hash pode ser simplesmente return key;. Exemplo de uso:

unsigned long hash_int(int key) { return key; }

2. Escreva uma função para remover um elemento da tabela hash com encadeamento separado.

Ver resposta

✓ Resposta:

int remove_key(HashTable *table, const char *key) {
    unsigned long index = hash_djb2(key) % TABLE_SIZE;
    Node *node = table->buckets[index];
    Node *prev = NULL;
    while (node) {
        if (strcmp(node->key, key) == 0) {
            if (prev) prev->next = node->next;
            else table->buckets[index] = node->next;
            free(node->key);
            free(node);
            return 1; // sucesso
        }
        prev = node;
        node = node->next;
    }
    return 0; // não encontrado
}

3. Modifique a implementação para que a tabela redimensione dinamicamente quando o fator de carga ultrapassar 0.7.

Ver resposta

✓ Resposta: Uma abordagem é criar uma nova tabela maior e reinserir todos os elementos. Exemplo de função resize:

void resize(HashTable *table, int new_size) {
    Node **old_buckets = table->buckets;
    int old_size = TABLE_SIZE; // mas você precisa ter o tamanho atual
    table->buckets = calloc(new_size, sizeof(Node *));
    for (int i = 0; i < old_size; i++) {
        Node *node = old_buckets[i];
        while (node) {
            Node *next = node->next;
            unsigned long new_index = hash_djb2(node->key) % new_size;
            node->next = table->buckets[new_index];
            table->buckets[new_index] = node;
            node = next;
        }
    }
    free(old_buckets);
}

4. Explique a diferença entre encadeamento separado e endereçamento aberto e cite um cenário onde cada um é preferível.

Ver resposta

✓ Resposta: No encadeamento separado, cada bucket é uma lista ligada, então não há limite de elementos por bucket, e a remoção é simples. No endereçamento aberto, todos os elementos ficam no array, e quando há colisão, procuramos outra posição. O encadeamento é preferível quando a tabela é muito dinâmica (muitas inserções/remoções) ou quando não conhecemos o volume de dados. O endereçamento aberto é preferível quando a memória é limitada e o fator de carga pode ser mantido baixo, pois usa menos memória (sem ponteiros extras).
5. Crie uma tabela hash para armazenar palavras e suas frequências em um texto. Leia um arquivo, conte as palavras e imprima as mais frequentes.

Ver resposta

✓ Resposta: Uma solução completa envolve ler o arquivo, tokenizar as palavras, inserir/atualizar na tabela. Exemplo esqueleto:

// ... funções da tabela
void process_file(const char *filename) {
    FILE *fp = fopen(filename, "r");
    if (!fp) return;
    char word[256];
    while (fscanf(fp, "%255s", word) == 1) {
        // normalizar palavra (opcional)
        int *freq = search(table, word);
        if (freq) (*freq)++;
        else insert(table, word, 1);
    }
    fclose(fp);
    // depois percorrer e imprimir
}