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
Sem resumo de edição |
Sem resumo de edição |
||
Linha 1:
== 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. [[Ficheiro:Hash3.JPG|miniaturadaimagem|303x303px]]
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.
[[Ficheiro:
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.
Linha 16:
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,
[[Ficheiro:Dispersão_hash.png|miniaturadaimagem|Amostra de dispersão da tabela hash|centro|356x356px]]
|