Tabelas Hash

Uma tabela hash, tabela de dispersão ou ainda tabela de espalhamento, é uma estrutura de dados utilizada

para tornar o processo de busca mais eficiente. Assim, esta estrutura de dados é muito utilizada não para

inserções ou remoções, mas quando há a necessidade de realizar muitas buscas e com rápido tempo de resposta.

Imagine um vetor, estrutura de dados homogênea que aprendemos lá no início do curso. Para descobrir se um dado elemento está ou não no vetor precisamos percorrer todo o vetor procurando pelo elemento. Isso pode ser muito demorado dependendo da quantidade de buscas necessárias e principalmente do tamanho do vetor.

Em uma tabela hash é possível acessar diretamente a posição da tabela onde o elemento deve estar caso ele exista, tornando o processo de busca muito mais eficiente.

Como Implementar uma tabela hash?

Uma tabela hash pode ser implementada de diferentes formas. Veremos aqui duas formas mais utilizadas para sua implementação, usando vetor e lista encadeada.

Tabela hash com vetor

Um vetor pode ser uma tabela hash desde que o processo de inserção e busca sejam implementados para tal.

Vamos usar como exemplo um vetor de números inteiros de tamanho 100. Cada número que será guardado neste vetor recebe o nome de chave ou chave hash pois é por meio dele que iremos "calcular" a posição do vetor onde ele será inserido.

Agora imagine o número 618396. Para descobrir a posição onde este número será armazenado precisamos

definir uma função chamada de função hash ou função de espalhamento, nome bem sugestivo, uma vez que

seu objetivo é espalhar os elementos pela tabela.

Uma função de espalhamento bastante simples é obter o resto da divisão do valor a ser inserido pelo tamanho

da tabela. Assim, no nosso exemplo, teremos:

posição = 618396 % 100 = 96

Dessa forma o valor 618396 será inserido na posição de índice 96 em nosso vetor. Ao realizar uma busca para

saber se o valor 618396 está no vetor, basta usar a função de espalhamento novamente que irá retornar o valor

96 e verificar o conteúdo desta posição no vetor. Assim, conseguimos um acesso direto ao elemento, sem

precisar percorrer todo o vetor.

Tabela hash com lista encadeada

Outra forma de se construir uma tabela hash e tratar colisões é por meio de um vetor de listas encadeadas.

Assim, como cada posição da tabela possui um ponteiro para uma lista encadeada, cada elemento será inserido

nessa lista, mesmo se for uma colisão.