Saltar para o conteúdo

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

Fonte: Wikiversidade

Tabela – HASH (Tabela de espalhamento)

[editar | editar código-fonte]

O que é a tabela HASH ?

[editar | editar código-fonte]
  • 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 ?

[editar | editar código-fonte]

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.

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

[editar | editar código-fonte]
  • 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

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.