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:
==
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).
|