Juliana Jenny Kolb
Home > Simulados on-line > Questões de Concursos > Tecnologia da Informação (TI) > Algoritmos e Estruturas de Dados > Estruturas de Dados
Estrutura 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.
A Função hash pode ser feita de diversas maneiras, porém procura-se montá-la de uma forma que a posição seja encontrada com O(1), independentemente do tamanho do arquivo, ou seja, o acesso seja direto ao registro.
Entretanto, podem ocorrer casos em que chaves distintas apontam para uma mesma função hash, tento-se então as Colisões de hash, que podem ser tratadas de diversas maneiras, como encadeamento externo, encadeamento interno, sondagem linear, sondagem quadrática e hash externa.
A função de dispersão da tabela hash seguem dois princípios: quanto mais dispersos melhor, ou seja, evitar o acontecimento de colisões de chaves. Ela também analisa qual é o tipo da chave que está sendo utilizada para o calculo da função, como por exemplo, podemos ter valores inteiros para o “código” do registro. Nesse caso, é muito recorrente o uso da função de hashing modular, que calcula a posição pelo calculo de mod M, sendo M o trabalho da tabela Hash, que desejavelmente seja um número primo, para facilitar a dispersão.
Exemplo:
F[x] = x mod M
Onde: F[x] = função de dispersão, x = chave do registro e M = Tamanho da Tabela Hash.
Colisões
Uma função hash por mais eficiente que seja na dispersão de elementos ocasionalmente terá colisões, estas ocorrem em uma Tabela Hash quando duas chaves diferentes possuem o mesmo valor da função hash e, portanto, elas são levadas à mesma posição da tabela hash. Porém, mesmo quando isso ocorre é necessário que as duas chaves sejam armazenadas na tabela e que as duas possam ser encontradas se a busca for realizada. Para resolver esse problema é necessário que uma medida seja tomada, utilizando assim alguma forma de tratamento as colisões.
Existem várias formas de se realizar um tratamento de colisões, entre elas temos o encadeamento interno.
Encadeamento Interno
O encadeamento interno utiliza outras posições vazias dentro da própria tabela hash por meio de buscas padronizadas para armazenar a chave que obteve colisão. Existem alguns métodos para resolver isso, como:
Sondagem linear
As próximas posições são sondadas até que uma posição livre seja encontrada, utilizando uma procura linear até encontrar um registro vazio.
regra: h(k,i) = [ h(k) + i ] mod n
Sondagem quadrática
A distância até a próxima posição a ser sondada é determinada pelo quadrado da tentativa.
regra: h(k,i) = [ h(k) + i² ] mod n
Duplo Hash
A distância até a próxima posição a ser somada é determinada por uma segunda função hash, que também pode ser denominada por rehash. O que acontece, nesse caso, é que o vetor da tabela é formado por uma sequência de funções de espalhamento auxiliares, na qual a chave de entrada será o valor gerado pela função anterior.
regra: h(k,i) = [ h(k) + i * h'(k) ] mod n
Encadeamento Externo
O encadeamento externo utiliza uma área extra, além da tabela hash. Alguns exemplos utilizados são:
Área de Extensão
Os registros colididos serão armazenados em uma área de extensão, que é uma área adicional à tabela hash reservada para guardar os registros que obtiveram colisões na função hash.
Lista encadeada
Todos os registros são armazenados em uma lista encadeada fora da tabela hash. A inserção na tabela requer uma busca e inserção dentro da lista encadeada, o que pode resultar em um alto custo de execução.
Uma alternativa para resolver esse problema seria utilizar outras estruturas de dados alternativas como, por exemplo, uma árvore AVL, que poderia melhorar o tempo médio de acesso da tabela hash para O(log n) em vez de O(n) se utilizássemos a lista encadeada.
Buckets
Para armazenar vários registros podemos pensar em usar Buckets que consistem em 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), 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 registros é muito mais eficiente pois não precisaremos mais acessar o disco rígido, teremos todos os registros na memória principal, uma vez feita a busca.
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 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
Referência Bibliográfica
Honda, Willian Yukio; Paraboni, Ivandré. ACH2023 – ALGORITMOS E
ESTRUTURAS DE DADOS I. Trabalho Acadêmico, 2011.
Sites Pequisados
www.devmedia.com.br