Graduando

Tabelas Hash

Tabela Hash é, basicamente, uma estrutura de dados não ordenada que utiliza uma função de hash para permitir uma rápida localização dos elementos nela contidos.
Uma Função hash, por sua vez, é uma procedimento ou função matemática que converte uma grande quantia de dados (possivelmente de tamanho variável) em uma informação menor, geralmente um número inteiro. Os valores retornados por este tipo de função são chamados de valores hash, códigos hash, somas hash, checksums, ou simplesmente hashes, e podem ser usados como índices para matrizes, como é o caso das tabelas hash.
Nas tabelas hash, uma função deste tipo é usada para transformar a chave da tabela em um índice (hash) do elemento da matriz (slot).
Idealmente, a função hash deve transformar cada chave possível em um único índice, porém isso raramente acontece na prática pois há situações em que duas chaves possuem o mesmo hash, e, portanto, referenciam o mesmo slot na matriz. Este evento é chamado de colisão. A maioria dos designs de tabelas hash assume que as colisões são possíveis de se acontecer e que devem ser tratadas de alguma maneira.

Resolução de Colisões

Se duas chaves possuem o mesmo índice, os registros correspondentes não podem ser armazenados no mesmo local, portanto, se o slot estiver ocupado, o registro deve ser armazenado em outro, de maneira que o permita ser localizado futuramente.
Há diversas técnicas para resolução de colisões, mas as mais comuns são: encadeamento, e endereçamento aberto.

Encadeamento
Nesta técnica, cada slot da matriz faz referência a uma lista relacionada de registros correspondentes a cada slot da matriz. Desta maneira, quando um registro é inserido ele é adicionado no final da lista relacionada àquele slot. Quando um registro é consultado, ele é procurado na lista relacionada equivalente. A figura 1 representa uma colisão hash resolvida por encadeamento.

Figura 1 Colisão hash resolvida por encadeamento

Endereçamento aberto