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, esperase 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.