Aula 18 - Algoritmos de Busca Avançada (Binária e Hashing) 🔍

📑 1. Fundamentos Teóricos & Análise Técnica

A recuperação rápida de informações é o alicerce dos bancos de dados e sistemas de busca modernos. Quando uma coleção está desordenada, a única alternativa determinística é a Busca Linear \(O(n)\). Contudo, ao impor estruturação prévia, a latência de consulta é comprimida:

1. Busca Binária (\(O(\log n)\)): Exige que a coleção esteja previamente ordenada. Compara o elemento do meio (mid): se o alvo for menor, descarta a metade superior; se for maior, descarta a metade inferior.
2. Tabelas Hash / Tabelas de Dispersão (\(O(1)\) Médio): Mapeiam chaves arbitrárias para índices de vetores através de uma Função de Hash determinística.
3. Resolução de Colisões: Pelo Princípio da Casa dos Pombos, quando duas chaves diferentes produzem o mesmo índice de hash:
4. Encadeamento Separado (Chaining): Cada posição do vetor armazena uma lista encadeada contendo todos os elementos que colidiram naquele slot.
5. Endereçamento Aberto (Open Addressing): Procura o próximo slot livre no vetor via sondagem linear (Linear Probing) ou sondagem quadrática.

📐 Arquitetura Conceitual & Diagrama de Fluxo

flowchart TD
    Key["Chave de Entrada: 'usuario_123'"] --> HashFn["Função Hash (MurmurHash / DJB2)"]
    HashFn --> Index["Índice Calculado: 4"]
    Index --> Table["Tabela Hash (Vetor de Buckets)"]
    Table --> Slot4{"Slot 4 Ocupado?"}
    Slot4 -->|Não: Livre| Store["Grava Registro Diretamente em O(1)"]
    Slot4 -->|Sim: Colisão| Chain["Encadeamento em Lista / Sondagem Aberta"]
    style Key fill:#e1f5fe,stroke:#01579b
    style HashFn fill:#fff3e0,stroke:#e65100
    style Store fill:#e8f5e9,stroke:#2e7d32
    style Chain fill:#ffebee,stroke:#c62828

🔍 Pilares e Diretrizes Técnicas

Nesta unidade, aprofundamos os seguintes conceitos fundamentais: - Cálculo do Ponto Médio sem Overflow: Uso de mid = low + (high - low) / 2 para prevenir estouro de inteiros em arrays gigantes. - Fator de Carga (Load Factor \(\alpha = N/M\)): Proporção de elementos ocupados. Quando \(\alpha > 0.7\), a tabela deve sofrer Rehash dobrando de tamanho. - Uniformidade da Função de Hash: Distribuição uniforme de chaves para evitar clusters primários que degenerem a tabela para \(O(n)\). - Resistência a Ataques HashDoS: Uso de sementes aleatórias para evitar que atacantes explorem colisões deliberadas.

🛠️ 2. Implementação Prática em Estruturas de Dados e Algoritmos de Busca

Abaixo está a implementação técnica de referência, estruturada com padrões de engenharia de software e foco em robustez:

// hash_table_chaining.c (Tabela Hash com Resolução por Encadeamento em C)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

typedef struct HashNode {
    char key[64];
    int value;
    struct HashNode* next;
} HashNode;

typedef struct {
    HashNode* buckets[TABLE_SIZE];
} HashTable;

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

void hash_insert(HashTable* table, const char* key, int value) {
    unsigned long idx = hash_djb2(key);
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    strcpy(newNode->key, key);
    newNode->value = value;
    // Insere no início da lista encadeada (O(1))
    newNode->next = table->buckets[idx];
    table->buckets[idx] = newNode;
}

💡 Análise Passo a Passo do Código

1. Função djb2: Algoritmo de dispersão rápido que espalha bits de strings com deslocamentos (hash << 5) e somas.
2. Encadeamento em O(1): Novas colisões são inseridas na cabeça da lista encadeada no bucket correspondente sem percorrer a lista inteira.
3. Acesso Instantâneo: Acesso médio em tempo constante \(O(1)\) para recuperação posterior.

🎯 3. Próximos Passos & Sequência Didática