Tabela de dispersão (também conhecida por tabela de espalhamento ou tabela hash, do inglês hash) é uma estrutura de dados especial, que associa chaves de pesquisa a valores. Seu objetivo é, a partir de uma chave simples, fazer uma busca rápida e obter o valor desejado.
A função de espalhamento ou função de dispersão é a responsável por gerar um índice a partir de determinada chave. Caso a função seja mal escolhida, toda a tabela terá um mau desempenho.
O ideal para a função de espalhamento é que sejam sempre fornecidos índices únicos para as chaves de entrada. A função perfeita seria a que, para quaisquer entradas A e B, sendo A diferente de B, fornecesse saídas diferentes. Quando as entradas A e B são diferentes e, passando pela função de espalhamento, geram a mesma saída, acontece o que chamamos de colisão.
Colisões A função de dispersão pode calcular o mesmo índice para duas chaves diferentes, uma situação chamada colisão. Por conta disso, a função deve ser projetada para evitar ao máximo a ocorrência de colisões. Por mais bem projetada que seja a função de dispersão, sempre haverá colisões. A estrutura de dispersão utiliza mecanismos para tratar as colisões, que dependem de características da tabela usada.
Exemplo:
função para distribuir nomes:
Agora inserimos mais um nome:
- Renato Porto; Rua dos Elefantes, 687; Telefone (31) 3333-5555
E temos uma colisão:
Como se pode notar, a função utilizada para no exemplo causaria muitas colisões. Se inserirmos um outro nome começado com a letra R, teremos uma outra colisão na letra R. Se inserirmos "João Siqueira", a entrada estaria em conflito com o "José da Silva".
Fonte com algumas alterações:
http://pt.wikipedia.org/wiki/Tabela_de_dispers%C3%A3o