Dando continuidade ao nosso Curso de Programação C, vamos aprender mais uma estrutura de dados? Hoje vamos aprender o que é e como funciona a estrutura de dados Tabela Hash, uma estrutura de dados muito utilizada para realização de buscas, também chamada de tabela de dispersão ou tabela de espalhamento.

O que é uma Tabela 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.

Como tratar colisões na tabela hash?

Mas nem tudo são flores. O que você acha que vai acontecer ao tentarmos inserir o valor 472196? É um valor completamente diferente certo? Contudo, a nossa função de espalhamento irá gerar novamente o índice 96. Isso se chama colisão, quando a função de espalhamento gera um índice já ocupado na tabela hash.

Existem ao menos duas formas de tratar colisões. A primeira é inserir o novo elemento na próxima posição vazia. Assim, o valor 472196 será inserido na posição 97, ou 98, ou 99, ou 0, ou 1… na próxima posição vazia.

Para minimizar o número de colisões, além de uma boa função de espalhamento é necessário que a tabela (o vetor) seja maior que o conjunto de dados que será armazenado. Uma forma de construir uma boa tabela hash é escolher o número primo mais próximo do dobro da quantidade de elemento que serão inseridos na tabela. Exemplo, se serão inseridos 6 elementos, o dobro é 12, então podemos escolher o 11 ou o 13 para o tamanho da nossa tabela.

Um número primo como tamanho da tabela ajuda a diminuir o número de colisões ao usar o tamanho da tabela na função de espalhamento.

Ao realizar a busca, como será gerado o índice 96 e o valor 472196 não estará nesta posição, fazemos o mesmo processo, olhamos a posição seguinte até encontrar o elemento ou uma posição vazia. Assim, só podemos afirmar que o elemento procurado não se encontra na tabela quando encontrarmos uma posição vazia.

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.