Algoritmos/Estruturas de dados/Tabela Hash

Historia

Existem duas hipóteses do surgimento da Tabela Hash. A primeira delas e que foi criada por volta de 1950 por H.P. Luhn, que teve a ideia desenvolvendo um outro trabalho. A outra, é que foi desenvolvida em 1960 pelos desenvolvedores de Compiladores par linguagens de compiladores. A descoberta foi de tanta importância que a estrutura é muito presente em diversos sistemas e programas nos dias de hoje.

Tabela 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.

Com isso, esperamos que a função hash possa ser calculada de forma eficiente e que tenha uma grande dispersão de elementos. Bem como o exemplo a seguir, que mostra o a dispersão de mais de 10 mil palavras, em uma função modular, com hash de tamanho 97.

Amostra de dispersão 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.

Exemplo de colisão de chaves.

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 sequencia 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:

Exemplo de lista encadeada.

Á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 utilizassemos 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 para serem 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

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 cheio, assim criamos um novo bucket e realocamos os registros nesse novo bucket de forma que todos possam estar lá.

Adicionar a chave numero 20:

Como podemos ver a chave 20 não cabe no bucket(0) então devemos criar um novo bucket, aumentar as profundidades global e local (do bucket afetado), duplicar os endereços e fazer novas referencias.

As chaves antigas do bucket(0) foram realocadas passando a usar uma nova função Hash, e dessa forma conseguimos inserir a chave 20, e faremos isso sempre que for preciso, dessa forma não teremos que realocar TODOS os registros mas somente os que forem afetados.

Vantagens do Hash Extensível

1. O diretório cresce sem precisar reposicionar todos os registros, somente os que foram afetados.
2. A lista de Buckets aumenta de acordo com a necessidade.
3. A consulta de Buckets é feita por meio de um ponteiro(rápido).
4. Com 2 acessos ao disco podemos recuperar todo nossos registros naquele bucket (acesso ao ponteiro do bucket e ao bucket).

Bibliografia

• Hashing
• Kutova, Marcos (2017) Slides e Vídeo-aulas no AVA