DC-UFRPE/Licenciatura Plena em Computação/Algoritmos e Estruturas de Dados/Tabela HASH
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.
Colisões
[editar | editar código-fonte]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
Referências
[editar | editar código-fonte]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.