Essa técnica se baseia em criar tabelas e utilizar funções de transformações de chaves de forma a obter o índice do elemento na tabela. Podem ocorrer elementos com índice igual. Essas 'colisões' podem ser tratadas com listas encadeadas ou com encadeamento aberto, que será explicado mais adiante.
Como fazer uma tabela hash
a tabela tem um tamanho fixo M. Basta calcular, usando uma função hash, um índice para cada chave de forma a distribuí-los na tabela entre 0 e M-1.Tratamento de colisões:
As colisões podem ser tratadas por meio de listas encadeadas, ou seja, caso um elemento tenha um índice onde já há outro elemento, ele é inserido logo após a raíz da lista e aponta para o elemento seguinte.
Podem, também, ser tratadas por endereçamento aberto:
- Hashing linear: caso o índice definido para um elemento já esteja ocupado, ele será inserido na primeira posição vazia disponível a partir daquele índice. Só que é perigoso a tabela encher e os registros começarem a se agrupar.
- Hashing quadrático: o elemento é inserido na posição correspondente ao quadrado do primeiro índice encontrado.
- Hashing duplo: caso haja colisão, é aplicada outra função hash para obter outro índice.
Função hash:
A função hash mais comum para chaves inteiras é chave % M. Lembrando que caracteres podem ser transformados em inteiros utilizando seu código ascii.
Nenhum comentário:
Postar um comentário