Tratamento de colisão - lista encadeada

Prévia do material em texto

Tabela Hash
Tratamento de colisões por endereçamento 
separado (listas encadeadas)
emanoelim@utfpr.edu.br
Listas encadeadas
• Em vez de procurar uma posição vaga, cada posição do 
vetor guarda o início de uma lista encadeada. 
• Toda chave mapeada para a mesma posição é adicionada 
na lista:
Listas encadeadas
Listas encadeadas
• Usamos listas encadeadas pois não sabemos quantas 
colisões podem acontecer.
• Para inserir um item, deve-se calcular a posição e inserir o 
item no início da lista correspondente. Assim, a inserção 
sempre terá custo O(1).
Listas encadeadas
• Para buscar / remover um item, deve-se calcular a posição 
e percorrer a lista até achar o item desejado. O custo será 
proporcional ao tamanho da lista (ou ao número de 
colisões que aconteceram na posição).
Referências
• Ziviani, N. “Projeto de algoritmos com implementações em C e Pascal”, 
Cengage Learning, 3ª ed., 2010.
• Notas de aula Prof. Luis Gustavo Nonato:
http://www.lcad.icmc.usp.br/~nonato/ED/Hashing/node33.html
• Vídeo aulas sobre tabela hash:
https://www.youtube.com/watch?v=njkANXEMHTY