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

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.