Algoritmos/Estruturas de dados/Tabela Hash: diferenças entre revisões

[edição não verificada][edição não verificada]
Conteúdo apagado Conteúdo adicionado
Inclusão de informações
Bucket, e Hash Dinâmica. Falta por as fotos.
Linha 1:
== Tabela Hash DinâmicaTabela Hash ==
A Tabela Hash ( ou tabela de dispersão) é uma estrutura de dados que se assemelha à uma tabela. Ela geralmente é utilizada para armazenar dados de grande volume, como arquivo de dados. A tabela Hash é uma estrutura muito eficiente,pois a posição de onde o registro será posicionado pode ser facilmente calculada com uma função de dispersão, nomeada Função Hash. [[Ficheiro:Hash3.JPG|miniaturadaimagem|303x303px]]
 
Linha 27:
 
• Sondagem linear
 
== Buckets ==
Para armazenar vários registros podemos pensar em usar Buckets que seriam blocos (de vários registros). Trabalhar com Buckets é interessante pois ele não armazena em um endereço um único registro, mas sim vários. Vamos supor, por exemplo, um registro de índice simples com 12 bytes (4 para o id e 8 para o endereço), assim temos que um setor no HD possui 4096 bytes que dividindo pelo índice fica 341,33 ou melhor 341 registros nesse setor. A busca desses registro é muito mais eficiente pois não precisaremos mais acessar o disco rígido, teremos todos os registros na memória principal.
 
(Foto)
 
Como o Bucket funciona:
 
Temos vários registros param ser armazenados no Bucket, para isso utilizaremos uma função hash, para ver em qual endereço devemos armazenar aquele registro de índice. A inserção no Bucket é feita conforme há espaço nele, caso o Bucket o esteja cheio, devemos utilizar alguns tratamentos de colisões como:
# Encadeamento Interno
* Sondagem Linear
* Sondagem Quadrática
* Re-Hash
# Encadeamento Externo
* Área de extensão
* Lista encadeada
# Criação de um novo Bucket
 
== Hash Dinâmica ==
A vantagem da tabela hash dinâmica para a tabela hash estática é que podemos aumentar a dinâmica conforme precisamos, sem reposicionar TODOS os registros, que é o que acontece na tabela hash estática. O reposicionamento dos registros na tabela dinâmica é somente no Bucket que estiver estourado sua capacidade de registros com o novo Bucket que será criado.
 
Legenda
* p: profundidade global (diretorio)
* p’: profundidade local (bucket)
* n: número de elementos no bucket
(Fotos)
 
Vantagens do Hash Extensível
 
O diretório cresce sem precisar reposicionar todos os registros, somente os que foram afetados.
 
A lista de Buckets aumenta de acordo com a necessidade.
 
A consulta de Buckets é feita por meio de um ponteiro(rápido).
 
Com 2 acessos ao disco podemos recuperar todo nossos registros naquele bucket (acesso ao ponteiro do bucket e ao bucket).