Pesquisa de Dados

Consiste em buscar dados em uma estrutura usando um algoritmo de pesquisa. Dois exemplos de algoritmo de pesquisa são pesquisa seqüencial e binária.

Pesquisa Seqüencial e Binária

A pesquisa seqüencial ou linear consiste em procurar partindo de um ponto inicial e encerrando apenas quando o dado for encontrado ou ao chegar ao final da estrutura sem encontrá-lo.

A pesquisa binária é um algoritmo aplicado somente a estruturas ordenadas, armazenadas em dispositivos de acesso direto. Consiste em comparar o argumento de pesquisa com a chave localizada no meio da estrutura. Se o argumento for maior, o processo é repetido para a metade superior da lista. Se for menor, para a metade inferior. Caso contrário é porque o argumento é igual à chave contida na estrutura.

Para ver as implementações da pesquisa seqüencial e binária (iterativa e recursiva), abra a unit Busca.

Pesquisa por cálculo de endereço (Hashing)

A pesquisa por cálculo de endereço (Hashing) baseia-se na idéia de calcular o endereço de armazenamento do dado a partir do valor da chave, ou seja, aplica-se uma função de cálculo de endereço (função Hashing) sobre a chave, obtendo-se como resultado o endereço de armazenamento na tabela.

Dessa forma, este método é mais do que um método de pesquisa. É um método de organização física das tabelas.

A função ideal seria aquela que gerasse um endereço diferente para cada um dos N diferentes valores das chaves presentes na tabela. Entretanto, este tipo de função não é conseguida e as funções normalmente utilizadas provocam colisões, isto é, atribuem um mesmo endereço a diferentes valores de chave.

Uma das funções mais usadas é:

Esta função pode ser adaptada para tipos de chaves não-numéricas. Teríamos para uma chave do tipo String a seguinte função Hashing:

Supondo que as chaves variam de 0 a 1000 e que o tamanho da tabela é igual a 100 (endereços variando de 1 a 100), os endereços correspondentes às chaves abaixo seriam:

Note que as chaves 801 e 101 geram o endereço 2 segundo a função Hashing, isto é, ocorre uma colisão. Uma das técnicas mais simples e usuais para solucionar o problema de colisões é chamado endereçamento aberto e consiste em procurar seqüencialmente, a partir do endereço gerado, o primeiro endereço lido e nele armazenar o novo dado. Para o exemplo anterior teríamos:

Uma solução alternativa para o problema das colisões consiste no uso de encadeamento. Neste caso, todas as chaves que colidem em um mesmo endereço são coletadas em uma mesma lista encadeada que tem como nós as chaves cujos endereços calculados pela função Hashing colidem.

Para ver a implementação de uma tabela Hash, abra a unit TabHash e o programa TestHash que demonstra seu uso.