Encadeamento Separado
O que é?
O Encadeamento Separado (também conhecido como Encadeamento Fechado ou Tratamento por Listas) é uma das formas mais simples e eficientes de se lidar com colisões em Tabelas Hash. Nesta estratégia, a tabela hash não armazena os elementos diretamente. Em vez disso, cada posição (ou bucket) da tabela atua como um ponteiro ou cabeçalho para uma Estrutura de Dados complementar, quase sempre uma Lista Encadeada.
Sempre que dois valores diferentes tiverem o mesmo valor de índice de dispersão (Hash), ocorrerá uma colisão, e ambos serão inseridos na lista encadeada daquele mesmo índice.
Aplicação no Sistema
No Laboratório, ao selecionar "Encadeamento Separado (Listas)":
- Cada posição na memória é exibida inicialmente vazia.
- Ao adicionar o primeiro elemento em um índice, o item aparece conectado àquele espaço.
- Quando acontece uma colisão (um novo item precisa entrar em um índice já ocupado), o sistema exibe uma animação destacando a colisão no painel, e então acrescenta uma seta apontando para o novo elemento inserido no final da lista encadeada, crescendo horizontalmente.
- Na operação de Busca, se mais de um item ocupar o índice, o sistema mostrará a verificação (percorrendo o "traversing") ocorrendo elemento por elemento, ilustrando o tempo que a CPU leva para iterar através de toda a lista para encontrar (ou não) o item procurado.