Avore AVL

Tabela Hash

Tabela de dispersão ou tabela hash é uma estrutura de dados especiais que associa chaves de pesquisa a valores. Essa tabela tem como função pegar uma simples chave e partir disso organizar uma rápida busca para obter o valor desejado.

A criação da tabela hash pode ser considera um mistério pois a quem acredite que foi criada por H.P Luhn em um de seus trabalhos na IBM. Por outro lado ouvi-se história de que se originou através de seus compiladores para a linguagem de programação com o objetivo de manter suas listas de variáveis em seus respectivos valores.

As tabelas dispersão têm como função trabalhar com vetores associativos, conjuntos e cachê. A implementação busca uma dispersão complexa não levando em conta os números de registro da tabela. O ganho com relação a outras estruturas associativas que passa a ser conforme a quantidade de dados aumentados.

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.

Na prática, funções de espalhamento perfeitas ou quase perfeitas são encontradas apenas onde a colisão é intolerável (por exemplo, nas funções de dispersão da criptografia), ou quando conhecemos previamente o conteúdo da tabela armazenada. Nas tabelas de dispersão comuns a colisão é apenas indesejável, diminuindo o desempenho do sistema. Muitos programas funcionam sem que seu responsável suspeite que a função de espalhamento seja ruim e esteja atrapalhando o desempenho.

Por causa das colisões, muitas tabelas de dispersão são aliadas com alguma outra estrutura de dados, tal como uma lista encadeada ou até mesmo com árvores balanceadas. Em outras oportunidades a colisão é solucionada dentro da própria tabela.