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
Linha 21:
== 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.
[[Ficheiro:Hash table 4 1 1 0 0 1 0 LL.svg|miniaturadaimagem|293x293px|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
==== Sondagem linear ====
As próximas posições são sondadas até que uma posição
====Sondagem quadrática ====
Linha 36:
====Duplo Hash ====
A distância até a próxima
=== Encadeamento Externo ===
O encadeamento externo utiliza uma área extra, além da tabela hash. Alguns exemplos utilizados são:
[[Ficheiro:Lista_Encadeada.gif|miniaturadaimagem|288x288px|Exemplo de lista encadeada.]]
====Área de Extensão ====
Os registros
====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 ==
| |||