Hashing Linear: Estrutura de Dados

Prévia do material em texto

Hashing Linear 
Gabriela Pilegi Ibata 
 
Hashing Linear é um tipo de estrutura de dados em tabela hash dinâmica 
que aumenta seu tamanho em um bucket cada vez que a expansão é 
necessária. 
 
Funcionamento 
O Hashing Linear funciona com os seguintes parâmetros: 
➔ Next(N): o bucket que será dividido, se necesário. ( inicialmente 0) 
➔ Numero de buckets: quantidade de buckets. 
➔ Condição de divisão: condição que determina se haverá aumento da 
tabela. 
➔ Capacidade do bucket: quantidade de elementos suportados por um 
bucket. 
 
A tabela é inicializada com uma quantidade arbitrária de buckets. 
As colisões podem ser tratadas de diversas maneiras, em grande parte 
das vezes a capacidade do bucket é de dois itens e um novo é criado a 
medida que ocorrem overflows. 
Ao inserir um elemento calcula-se o endereço de inserção através função 
hash a partir de sua chave. Quando mais de um item é referenciado à uma 
posição na tabela hash duas coisas podem acontecer : 
-Existe espaço suficiente para o novo elemento: nesse caso ele é 
adicionado ao bucket normalmente. 
- A quantidade de elementos por bucket é excedida: nesse caso é criado 
um nov bucket de overflow apontado pelo inicial. 
Depois de feita a inserção outras duas situações podem ocorrer: 
-A entrada do elemento no bucket não feriu a condição de divisão ( a 
tabela não precisará ser aumentada): Nesse caso nenhuma ação será 
tomada. 
-A entrada do elemento novo feriu a condição de divisão, nesse caso o 
algoritmo prosseguirá da seguinte forma : 
 
-Um novo bucket será adicionado à tabela. 
-O bucket endereçado pela variável Next obedecerá a outra função 
hash que comportará a nova quantidade de buckets, seus elementos 
serão distribuídos novamente pela tabela a partir dessa função. 
-O endereço de Next é modificado para o próximo bucket que não 
obedece a nova função. (o Next é adicionado até que todos os 
buckets tenham suas funções atualizadas e então volta para o 
inicio). 
 
Vantagens e desvantagens do hashing linear 
 
O algoritmo lida bem com colisões, a utilização do aumento da tabela uma 
unidade por vez divide o custo da operação entre cada expansão, em vez 
de dobrar a tabela de tamanho de uma só vez como no caso do Hashing 
Extensivo. 
Porém as cadeias de overflow fazem com que o algoritmo perca 
desempenho.