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.
Categoria:Criptografia