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 |
Inclusão de informações |
||
Linha 18:
Com isso, esperamos que a função hash possa ser calculada de forma eficiente e que tenha uma grande dispersão de elementos, evitando 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.
[[Ficheiro:Dispersão_hash.png|miniaturadaimagem|Amostra de dispersão da tabela hash|centro|356x356px]]
== Colisões ==
As colisões em uma Tabela Hash ocorrem 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 para armazenar a chave chave que obteve colisão. Existem alguns métodos para resolver isso, como:
• Sondagem linear
|