DC-UFRPE/Licenciatura Plena em Computação/Algoritmos e Estruturas de Dados/Tabela HASH

Tabela – HASH (Tabela de espalhamento)

O que é a tabela HASH ?

• Segundo Ascencio e Araújo (2015), a tabela hash ou uma hashing é uma generalização de um vetor com m posições que representa um endereço. Assim, os elementos que irão compor a tabela hash terão um valor-chave que será utilizado para calcular a sua localização na tabela.
• Para um conjunto de tamanho m, ele terá um conjunto de endereços que variam de 0 a m – 1. Um elemento que pertence a esse conjunto será adicionado à tabela hash através da função de dispersão. Essa função tem o objetivo de reduzir o espaço de alocação dos elementos do conjunto. Em outras palavras, um conjunto com 100 elementos pode ter 5 endereços (m = 5) em vez de 100 endereços.

O que é uma função de dispersão ?

A função de dispersão ou espalhamento (também conhecida como função hashing) calcula o endereço onde cada elemento do conjunto será armazenado. Por exemplo, utilizando o método da divisão para a função de dispersão, o resto da divisão de x (elemento de entrada) por m (quantidade de endereços) detremina a posição do x na tabela HASH. Em outras palavras, a função hash é dada por h(x) = x MOD m.

Colisões

Quando duas entradas de elementos possuem o mesmo valor hash, ocorre a colisão. A colisão é quando dois elementos, depois de passar pela função de dispersão, ocupam o mesmo endereço. Nesse caso, a segunda entrada vai substituir a primeira e isso causará perda de dados. Assim, segundo Mueller e Massaron (2018), existem algumas formas de evitar de colisões:

• Valores parciais: Quando estamos trabalhando com alguns tipos de informação, parte delas podem se repetir e assim causar colisões. Nesse caso, as informações que se repetem podem ser ignoradas e as partes que não se repetem podem ser utilizadas para resolver o problema da colisão. Ex: os três primeiros dígitos de um telefone podem se repetir em uma determinada localidade. Assim, podemos desconsiderar esses três primeiros valores e utilizamos os outros restantes para o cálculo da função de dispersão.

• Desdobramentos: Um valor pode ser dividido em partes e então somá-los para se obter um valor que será utilizado para o cálculo da função de dispersão.

• Meio– quadrado: O valor de entrada é elevado ao quadrado e então os dígitos do centro do valor resultante são coletados e o resto é descartado. Esse novo valor seria utilizado para cálculo da função de dispersão. Ex: A entrada seria o número 125 e elevando esse valor ao quadrado o resultado seria 15625. Descartaríamos o primeiro dígito (1) e o último dígito (5), restando 562. O valor 562 seria utilizado no cálculo de dispersão.

Utilidades para a HASH

• Message Digest
• Verificação de senha
• Estruturas de dados (linguagens de programação)
• Operação do compilador
• Algoritmo Rabin-Karp
• Vinculando o nome e o caminho do arquivo
• Integridade de mensagens

Referências

ASCENCIO, Ana Fernanda Gomes. ARAÚJO, Graziela Santos de. Estrutura de dados - Algoritmos, análise de complexidade e implementações em Java e C/C++. 3a Ed. Editora Pearson, 2015.

MUELLER, John Paul. MASSARON, Luca. Algoritmos para leigos. Editora Alta Books, 2018.