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?
editarUma 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
editarUm 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
editarOutra 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.