Hash Extensivel

Rápido acesso a dados com um custo mínimo de processamento

(overhead cost).

• Introducao:

Os principais objetivos deste método são pesquisa O(1) e tamanho variável conforme a quantidade de contudo.

Hash extensível usa a chave gerada pela função hash como uma pseudo-chave, que será quebrada conforme necessidade.

• Profundidade:

A profundidade deve ser tal que o numero de baldes contenham todas as chaves, é importante que a função hash distribua bem as chaves.

Este número de baldes(B) corresponde a 2p indices, assim p = log2 B. Onde B = (numero de chaves)/(taxa de ocupacao).

Supondo ocupação máxima temos B = (numero de chaves) / (tamanho do balde).

Inserção

• Inserção• Após obtida a pseudo-chave a partir da chave da

informação a ser armazenada, pega-se os p bits mais significativos da pseudo-chave (p se refere a profundidade de diretório ou profundidade global) como índice para acessar um posição do diretório.

• Por exemplo, se a pseudochave é 10100110 e a profundidade do diretório é 3, acessaremos a posição 101. Nesta posição do diretório teremos uma referência ao balde em que tentaremos inserir o dado( ou uma referência a ele). Daí poderemos ter três casos:

• Melhor caso: há espaço no balde e a pseudochave é simplesmente inserida no balde

• Caso Intermediário . Não há espaço no balde encontrado , mas ele pode ser divido em mais um balde

A profundidade desse balde é menor que a do diretório. Um novo balde é criado, e as pseudochaves são redistribuídas entre o novo balde e o original. A profundidade local desses baldes serão iguais a profundidade do balde original mais um.

• Pior caso: Não há espaço no balde encontrado e a entrada do diretório encontrada faz referência a um único balde, ou seja, a profundidade local do balde é igual a profundidade do diretório .

• O diretório dobra de tamanho e as pseudochaves são distribuídos entre os baldes do novo diretório.

Pesquisa

• A pesquisa no hash extensível é simples e muito rápida. A chave de pesquisa passa pela função hash retornando a pseudochave. Se a profundidade do diretório é p, os primeiros p bits da pseudochave são usados para compor o índice do diretório. Nesta posição temos a referência ao balde onde faremos pesquisa semelhante a feita num nó de árvore B.

Remoção

• Após removermos a informação do balde, temos que fazer duas verificações:

• 1- Se é possível fundi-lo com outro balde (balde amigo).

• 2- Se o tamanho do diretório pode ser reduzido.

Balde amigo

• Para a primeira verificação, temos que achar o balde amigo. Para haver um único balde amigo a profundidade do balde tem que ser a mesma do diretório. Dado um índice de um balde, o balde amigo é aquele que difere apenas no último bit do índice.

Redução de tamanho

• Isto é possível quando cada balde da estrutura é referenciado por pelo menos duas entrada do diretório.

• Ou seja, a profundidade de todos os baldes é menor que a global .Assim o diretório é reduzido pela metade ( a profundidade decresce de 1) e as referenciais aos baldes são refeitas.

Aplicações e Desemplenho

• Se o diretório de um hash podeser mantido na memória RAM um simples acesso é necessário para recuperar um registro.

• Mas, se o diretório é tão grande que ele precise ser mapeado fora da memória RAM, dois acessos podem ser necessários.

• Vantagens:

O tempo de acesso é completamente independente do tamanho do arquivo.

Hash extensível não há necessidade da ordenação dos dados no arquivo.

Tamanho tão grande quanto necessário(até um limite definido pela função hash).

Desempenho

Quão grande deve ser um diretório para um seterminado número de chaves?

A resposta foi dada por Frajolet em 1983:

Tamanho estimado do diretório = 3.92 r(1+1/b)/b.

Sendo r o número total de registros e b o tamanho do balde.

Sobre o preenchimento dos baldes, espera-se que os baldes estejam entre 0.53 e 0.94 cheios.

A análise de Fagin, Nievergelt, Pippenger e Strong sugere que para um número r de registros e um bloco de memória de tamanho b, o número médio de blocos N é aproximadamente:

N » r /(b ln 2)A utilização é dada por: r / (b N) que é igual a

ln 2 = 0.69.

• Assim, esperamos uma utilização de 69%. As árvores B tendem a ter uma utilização de 67%, que pode ser aumentado para 85%, se distribuirmos as chaves durante a inserção.

• Logo, uma árvore B tende a ocupar menos memória, ao custo de se procurar mais para se achar um dado.

Usos

• Hash extensível é usado quando temos um grande número de informações que estão em constantes mudança e elas têm de ser acessadas rapidamente.

• Isso ocorre principalmente em sistemas de arquivos de um sistema operacional e sistemas de bancos de dados.