PESQUISA TABELA HASH

Sistemas de informação – 4º Semestre

TRABALHO DE PESQUISA SOBRE TRATAMENTO DE COLISÕES EM TABELAS HASH

Transformação de Chave (Hashing)
Os registros armazenados em uma tabela são diretamente endereçados a partir de uma transformação aritmética sobre a chave de pesquisa.
Hash significa:

• Espalhar x Transformar (informática x computação)

Um método de pesquisa com o uso da transformação de chave é constituído de duas etapas principais:
1. Computar o valor da função de transformação, a qual transforma a chave de pesquisa em um endereço da tabela.
2. Considerando que duas ou mais chaves podem ser transformadas em um mesmo endereço de tabela, é necessário existir um método para lidar com colisões.

Qualquer que seja a função de transformação, algumas colisões irão ocorrer fatalmente, e tais colisões têm de ser resolvidas de alguma forma.
• Mesmo que se obtenha uma função de transformação que distribua os registros de forma uniforme entre as entradas da tabela, existe uma alta probabilidade de haver colisões.

Colisões

O paradoxo do aniversário (Feller, 1968, p. 33)
• Em um grupo de 23 ou mais pessoas, existe uma chance maior do que 50% de que 2 pessoas comemorem o aniversário no mesmo dia.
• Assim, se for utilizada uma função de transformação uniforme que enderece 23 chaves randômicas em uma tabela de tamanho 365, a probabilidade de que haja colisões é maior do que 50%.

A probabilidade p de se inserir N itens consecutivos sem colisão em uma tabela de tamanho M é:

Alguns valores de p para valores de N, com M = 365.

• Para N pequeno a probabilidade p pode ser aproximada por p ≈ N (N −1))/730.
• Por exemplo, para N = 10 então p ≈ 87,7%.

Funções de Transformação

Uma função de transformação deve mapear chaves em inteiros dentro do intervalo [0...M − 1], onde M é o tamanho da tabela.
• A função de transformação ideal é aquela que:
• Seja simples de ser computada.
• Para cada chave de entrada,