Estruturas de dados: tabela hash

1. Introdução ao Conceito de Tabela Hash

1.1 Definição e motivação

Uma tabela hash (ou tabela de dispersão) é uma estrutura de dados que implementa um mapeamento entre chaves e valores, permitindo acesso direto aos dados através de uma função matemática chamada função hash. Diferentemente de arrays tradicionais, onde os índices são inteiros sequenciais, a tabela hash aceita chaves de qualquer tipo (strings, números, objetos) e as converte em índices numéricos.

A motivação principal surge da necessidade de realizar buscas rápidas em conjuntos de dados. Enquanto uma busca sequencial em um array não ordenado tem complexidade O(n), a tabela hash oferece tempo constante O(1) para operações de inserção, busca e remoção, em média.

1.2 Vantagens

A principal vantagem da tabela hash é sua eficiência temporal:
- Inserção: O(1) em média
- Busca: O(1) em média
- Remoção: O(1) em média

No pior caso, quando ocorrem muitas colisões, a complexidade pode degradar para O(n), mas com uma boa função hash e tratamento adequado de colisões, isso raramente acontece.

1.3 Aplicações práticas

Tabelas hash são amplamente utilizadas em:
- Caches de memória (armazenamento temporário de resultados)
- Dicionários e tabelas de símbolos em compiladores
- Indexação de bancos de dados
- Implementação de conjuntos (sets) e mapas (maps)
- Sistemas de roteamento de rede

2. Função Hash

2.1 Propriedades essenciais

Uma boa função hash deve possuir três propriedades fundamentais:
- Determinismo: para a mesma entrada, deve sempre produzir a mesma saída
- Distribuição uniforme: os valores gerados devem se distribuir uniformemente pelo espaço de índices
- Eficiência computacional: deve ser rápida de calcular

2.2 Exemplos de funções hash simples

Método da divisão (resto da divisão):

hash(chave) = chave % tamanho_tabela

Método da multiplicação:

hash(chave) = floor(tamanho_tabela * (chave * A - floor(chave * A)))

onde A é uma constante entre 0 e 1 (tipicamente 0.6180339887).

2.3 Tratamento de chaves não numéricas

Para strings, uma abordagem comum é converter cada caractere em seu código ASCII e combiná-los:

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

Este é o algoritmo djb2, criado por Daniel J. Bernstein, conhecido por sua boa distribuição.

3. Colisões e Endereçamento Aberto

3.1 O problema das colisões

Colisões ocorrem quando duas chaves diferentes produzem o mesmo índice hash. Como o espaço de chaves é geralmente maior que o tamanho da tabela, colisões são inevitáveis. O tratamento adequado é crucial para o desempenho.

3.2 Sondagem linear

No endereçamento aberto, quando ocorre uma colisão, procuramos a próxima posição livre na tabela:

posicao = (hash(chave) + i) % tamanho_tabela

Onde i = 0, 1, 2, 3... até encontrar uma posição vazia.

Problema: causa agrupamento primário (clusters), onde posições ocupadas tendem a se agrupar, degradando o desempenho.

3.3 Sondagem quadrática e double hashing

Sondagem quadrática:

posicao = (hash(chave) + i²) % tamanho_tabela

Double hashing:

posicao = (hash1(chave) + i * hash2(chave)) % tamanho_tabela

Ambas reduzem o agrupamento, mas o double hashing é geralmente superior por usar duas funções hash independentes.

4. Colisões e Encadeamento Externo

4.1 Estrutura

O encadeamento externo (separate chaining) utiliza um array de listas encadeadas. Cada posição da tabela contém um ponteiro para o início de uma lista que armazena todos os elementos que mapearam para aquele índice.

4.2 Implementação em C

typedef struct No {
    char *chave;
    int valor;
    struct No *proximo;
} No;

typedef struct {
    int tamanho;
    No **tabela;
} TabelaHash;

Função de inserção:

void inserir(TabelaHash *ht, const char *chave, int valor) {
    int indice = hash(chave) % ht->tamanho;
    No *novo_no = (No*)malloc(sizeof(No));
    novo_no->chave = strdup(chave);
    novo_no->valor = valor;
    novo_no->proximo = ht->tabela[indice];
    ht->tabela[indice] = novo_no;
}

4.3 Vantagens e desvantagens

Vantagens:
- Simplicidade de implementação
- Não sofre de agrupamento
- Número de elementos pode exceder o tamanho da tabela

Desvantagens:
- Uso extra de memória para ponteiros
- Localidade de cache pobre (nós espalhados na memória)

5. Implementação Prática em C – Estrutura Base

5.1 Definição da tabela hash

#define TAMANHO_INICIAL 101

typedef struct {
    char *chave;
    int valor;
    struct No *proximo;
} No;

typedef struct {
    int tamanho;
    int num_elementos;
    No **tabela;
} TabelaHash;

5.2 Funções de inicialização e destruição

TabelaHash* criar_tabela(int tamanho) {
    TabelaHash *ht = (TabelaHash*)malloc(sizeof(TabelaHash));
    ht->tamanho = tamanho;
    ht->num_elementos = 0;
    ht->tabela = (No**)calloc(tamanho, sizeof(No*));
    return ht;
}

void destruir_tabela(TabelaHash *ht) {
    for (int i = 0; i < ht->tamanho; i++) {
        No *atual = ht->tabela[i];
        while (atual != NULL) {
            No *temp = atual;
            atual = atual->proximo;
            free(temp->chave);
            free(temp);
        }
    }
    free(ht->tabela);
    free(ht);
}

5.3 Função de hash para strings (djb2)

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

6. Operações Fundamentais

6.1 Inserção

void inserir(TabelaHash *ht, const char *chave, int valor) {
    unsigned long indice = hash_djb2(chave) % ht->tamanho;

    // Verificar se chave já existe
    No *atual = ht->tabela[indice];
    while (atual != NULL) {
        if (strcmp(atual->chave, chave) == 0) {
            atual->valor = valor; // Atualizar valor existente
            return;
        }
        atual = atual->proximo;
    }

    // Inserir novo nó
    No *novo_no = (No*)malloc(sizeof(No));
    novo_no->chave = strdup(chave);
    novo_no->valor = valor;
    novo_no->proximo = ht->tabela[indice];
    ht->tabela[indice] = novo_no;
    ht->num_elementos++;
}

6.2 Busca

int buscar(TabelaHash *ht, const char *chave, int *resultado) {
    unsigned long indice = hash_djb2(chave) % ht->tamanho;
    No *atual = ht->tabela[indice];

    while (atual != NULL) {
        if (strcmp(atual->chave, chave) == 0) {
            *resultado = atual->valor;
            return 1; // Encontrado
        }
        atual = atual->proximo;
    }
    return 0; // Não encontrado
}

6.3 Remoção

int remover(TabelaHash *ht, const char *chave) {
    unsigned long indice = hash_djb2(chave) % ht->tamanho;
    No *atual = ht->tabela[indice];
    No *anterior = NULL;

    while (atual != NULL) {
        if (strcmp(atual->chave, chave) == 0) {
            if (anterior == NULL) {
                ht->tabela[indice] = atual->proximo;
            } else {
                anterior->proximo = atual->proximo;
            }
            free(atual->chave);
            free(atual);
            ht->num_elementos--;
            return 1;
        }
        anterior = atual;
        atual = atual->proximo;
    }
    return 0;
}

7. Análise de Desempenho e Fator de Carga

7.1 Definição de fator de carga

O fator de carga α (alpha) é definido como:

α = n / m

Onde n é o número de elementos armazenados e m é o tamanho da tabela.

7.2 Complexidade temporal

  • Caso médio: O(1) para todas as operações
  • Pior caso: O(n) quando todas as chaves colidem para o mesmo índice
  • O fator de carga ideal geralmente é mantido abaixo de 0.75

7.3 Redimensionamento dinâmico (rehashing)

Quando o fator de carga excede um limiar (ex: 0.75), devemos redimensionar a tabela:

void rehash(TabelaHash *ht, int novo_tamanho) {
    No **tabela_antiga = ht->tabela;
    int tamanho_antigo = ht->tamanho;

    ht->tabela = (No**)calloc(novo_tamanho, sizeof(No*));
    ht->tamanho = novo_tamanho;
    ht->num_elementos = 0;

    for (int i = 0; i < tamanho_antigo; i++) {
        No *atual = tabela_antiga[i];
        while (atual != NULL) {
            inserir(ht, atual->chave, atual->valor);
            No *temp = atual;
            atual = atual->proximo;
            free(temp->chave);
            free(temp);
        }
    }
    free(tabela_antiga);
}

8. Boas Práticas e Considerações Finais

8.1 Escolha da função hash

  • Para inteiros: método da divisão com números primos
  • Para strings: djb2, FNV-1a, ou SHA-256 para aplicações críticas
  • Evite funções hash que produzem muitos zeros

8.2 Gerenciamento de memória

  • Sempre use strdup() para copiar strings (libere com free())
  • Implemente funções de destruição que liberem toda a memória alocada
  • Use valgrind ou ferramentas similares para detectar vazamentos

8.3 Comparação com outras estruturas

  • Arrays: Tabela hash oferece busca O(1) vs O(n) do array
  • Listas encadeadas: Hash é superior para busca, mas inferior para iteração ordenada
  • Árvores binárias: Hash é mais rápido (O(1) vs O(log n)), mas não mantém ordenação

A tabela hash é uma estrutura versátil e poderosa, essencial para qualquer programador C. Sua implementação cuidadosa, com atenção ao gerenciamento de memória e escolha adequada de função hash, resulta em estruturas de dados eficientes para uma vasta gama de aplicações.

Referências