Tabela Hash: Conceitos, Funções e Tratamento de Colisões

1. O que é Hash?

Hash é uma generalização da noção mais simples de um arranjo, sendo uma estrutura do tipo dicionário.

A ideia central do Hash é usar uma função aplicada sobre parte da informação (chave) para retornar um índice onde a informação será armazenada.

Estruturas de Dados do Tipo Dicionário

Estruturas de dados do tipo dicionário são especializadas em prover as operações de inserir, pesquisar e remover.

2. O que é Tabela Hash?

É uma estrutura de dados especial que armazena as informações desejadas associando chaves. A partir de uma chave, ela realiza a busca rápida e obtém o valor desejado.

Objetivo da Tabela Hash

O objetivo principal é fazer uma busca rápida e obter o valor desejado através de uma chave.

Representação da Tabela Hash

A representação da Tabela Hash é feita através de:

• Vetor: Onde o vetor armazena a posição com a informação.
• Vetor mais Lista Encadeada: O vetor terá um ponteiro para as listas que apresentam a informação.

3. A Função de Hash

A Função de Hash mapeia a chave para um índice de um arranjo. Ela é responsável por gerar um índice a partir de uma chave e por distribuir os índices pela tabela.

Hashing Perfeito e Imperfeito

• Função de Hashing Perfeito: Ocorre quando qualquer chave gerada fornece um valor diferente na saída.
• Função de Hashing Imperfeito: Ocorre quando qualquer chave gerada fornece o mesmo valor na saída.

4. Colisões em Tabela Hash

O que é Colisão?

As colisões ocorrem quando uma ou mais chaves geram o mesmo resultado na Tabela Hash.

Causas da Colisão

A principal causa de a colisão ocorrer é o número de chaves ser maior que o número de entradas disponíveis na tabela.

Estruturas Aliadas para Resolver Colisões

As estruturas de dados aliadas para resolver o problema de colisão são:

• Árvores Balanceadas
• Lista Encadeada
• A própria Tabela Hash

Técnicas de Tratamento de Colisões

As técnicas mais comuns para tratar a colisão são feitas através de:

• Endereçamento Aberto (Rehash)
• Encadeamento

Explicação do Encadeamento

O Encadeamento ocorre quando os dados são armazenados em estruturas encadeadas, como uma lista, fora da Tabela Hash.

Explicação do Endereçamento Aberto (Rehash)

Ocorre quando os dados são armazenados na própria tabela, com cada nó ficando em um índice na tabela.

5. Limitações e Aplicações do Hash

Limitações do Hash

Uma das limitações do Hash, por ser do tipo dicionário, é que ele não permite armazenar elementos repetidos e não permite recuperar os elementos de forma ordenada.

Áreas de Aplicação do Hash

As áreas de aplicação do Hash incluem:

• Criptografia
• Compactação de dados
• Integridade de Dados