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

[edição não verificada][edição verificada]
Conteúdo apagado Conteúdo adicionado
m Foram revertidas as edições de 177.101.200.34 (disc) para a última revisão de AlvaroMolina
Etiqueta: Reversão
Linha 28:
Existem várias formas de se realizar um tratamento de colisões, entre elas temos o encadeamento interno.  
 
=== '''Encadeamento InterInterno''' ===
O encadeamento interno utiliza outras posições vazias dentro da própria tabela hash por meio de buscas padronizadas para armazenar a chave que obteve colisão. Existem alguns métodos para resolver isso, como:
 
Linha 45:
 
regra: h(k,i) = [ h(k) + i * h'(k) ] mod n<br /><br />
 
=== Encadeamento Externo ===
O encadeamento externo utiliza uma área extra, além da tabela hash. Alguns exemplos utilizados são:
Linha 56 ⟶ 55:
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 ==