Tratamento de colisões através de encadeamento
# 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 :
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:
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.