Tratamento de colisões através de encadeamento

O objetivo de uma função de Hash é receber um determinado valor e retornar um número inteiro, que é um identificador para este valor que lhe foi passado.

Exemplo :

Valor1 = 10 , Valor2 = 27 Objetivo da Função é que : hash(valor1) seja diferente de hash(valor2)

Mas nem sempre a função cumpre o seu objetivo.

Já é sabido que matematicamente o número de valores possíveis é muito maior do que os identificadores retornados pela função de Hash.

Com isso, é possível que ocorram colisões.

Exemplo:

Valor1 = 10 , Valor2 = 27 É possível que o retorno da função seja: hash(valor1) = hash(valor2)

Este problema pode ser resolvido usando um dos vários métodos de tratamento colisões
em tabelas de Hash.

Encadeamento

Basicamente o que um algoritmo de Encadeamento faz é armazenar na tabela informações sobre onde o próximo registro deve ser buscado. Existem duas formas de Encadeamento :

• Encadeamento Externo
• Encadeamento Interno

Encadeamento Combinado

Neste encadeamento é criado um outro campo que pode ser chamado de próximo, este campo armazenará a posição em que devemos fazer a busca.

Funciona da seguinte maneira:

É calculado o Hash da chave que estamos procurando para descobrir onde ela se encontra, enquanto não chegar ao fim da busca e a posição não tiver sido encontrada, então verificamos neste novo campo onde deve ser feita a próxima busca.

Encadeamento Aberto

Neste encadeamento é usada uma lista encadeada como estrutura auxiliar.

A tabela contém ponteiros para início de cada lista.

Em busca ou inserção é aplicada a função de hash, o retorno será qual ponteiro deve ser seguido.