Técnicas de hashing

ANDY KIAKA
LARISSA MENDES RIBEIRO
OLAVO NETO

Técnicas de Hashing

Universidade Federal de Mato Grosso do Sul
Campo Grande (MS) – Agosto 2011

Técnicas de Hashing

É um tipo de organização primária de arquivo baseada em hashing, que fornece um acesso muito rápido aos registros sob certas condições. A condição de pesquisa precisa ser de desigualdade em um único campo, esse campo é chamado de campo hash. A idéia do hashing é fornecer uma função hash representada por {h(x)}, que aplicada ao valor do campo de hash de um registro gere o endereço do bloco de disco no qual o retiro está armazenado. A busca pelo registro dentro do bloco pode ser realizada em um buffer da memória principal.

Hashing Interno
Estrutura de dados interna a um programa usada para acessar pequenos arquivos temporários com base no valor de um único campo. O Hashing interno é normalmente implementado através de uma tabela hash por meio de um vetor de registros.

* Suponha que o índice do vetor CPF varie de 000 a n-1 onde n =1000, uma função para isso poderia ser representada por: * h(x) = x mod n, este valor será então usado como endereço do registro * No Exemplo abaixo a função equivale a h(CPF) = CPF mod 1000

CPF
Nome
Profissão
Salário
123456000
456123001
234156002
567890998
089765999

000
001
002
998
999
...
...
...
...

1

2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 Tratamento de Colisões 23 24 25 * Open Addressing ou Endereçamento aberto ou linear: A partir da posição de colisão, o programa prossegue a verificação pela ordem das posições subseqüentes até que seja encontrada uma posição não utilizada * Chaining ou Encadeamento: Manter uma lista encadeada de registros de overflow para cada posição no espaço