T Cnicas De Hashing

Técnicas de Hashing
3º Período – Sistemas P/ Internet
Aluno: Álef Lemos Borges e Rosa

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 varie de 0 a M1.

*Uma função típica para isto seria a função: h(K)
= K mod M
* Este valor será então usado como endereço do registro 

Funções hash não garantem endereços únicos



Ocorrência de colisões

Métodos para tratar colisões:


Open Addressing (Endereço aberto)



Encadeamento (Chaining)



Hashing Múltiplo

Hashing externo


Chama-se hash externo quando se trata de hashing para arquivos em disco



O espaço de endereçamento alvo é constituído de buckets. 

Buckets são grupos de blocos de disco consecutivos.



A função hash mapeia uma chave a um número de bucket. 

Uma tabela, mantida no cabeçalho do arquivo, converte o número do bucket para o endereço de bloco de disco.

Técnicas hashing que permitem a expansão de arquivos dinâmicos
O grande problema com os esquemas hashing apresentados anteriormente, os chamados hashing estáticos, é que o espaço de endereçamento hash é fixo.
Deste modo fica difícil aumentar ou diminuir um arquivo dinamicamente.

 Hashing extensível
Neste tipo de hashing é mantido um vetor de 2 d endereços de