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

 

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.

 

 

Com isso, esperamos que a função hash possa ser calculada de forma eficiente e que tenha uma grande dispersão de elementos, evitanto o máximo possível a colisão. 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.