Como excluir itens de uma tabela hash que usa encadeamento para tratar colisões?
se for endereçamento aberto? Quais são as circunstâncias especiais que devem ser tratadas?
Passo 1
A questão pede para explicarmos como remover itens de uma tabela hash em dois cenários: encadeamento (separate chaining) e endereçamento aberto (open addressing), e destacar quais cuidados especiais cada caso exige.
Passo 2
No caso de encadeamento, cada posição do array da tabela contém uma lista ligada (ou vetor dinâmico) de entradas que colidiram naquele índice. Para excluir uma chave você faz: 1) calcular o índice via função hash, digamos
;
2) percorrer a lista ligada em procurando o nó com a chave;
3) uma vez encontrado, desvincular esse nó da lista (ajustar ponteiro do nó anterior para o próximo). O custo é proporcional ao comprimento da lista naquele bucket. Não há outras armadilhas, exceto manter os ponteiros/links corretos.
2) percorrer a lista ligada em
3) uma vez encontrado, desvincular esse nó da lista (ajustar ponteiro do nó anterior para o próximo). O custo é proporcional ao comprimento da lista naquele bucket. Não há outras armadilhas, exceto manter os ponteiros/links corretos.
Passo 3
Em endereçamento aberto, não há listas: cada elemento é armazenado diretamente no array, e colisões são resolvidas por sondagem (por exemplo, linear, quadrática ou duplo hashing). A exclusão simples — limpar a posição tornando-a “vazia” — quebra cadeias de sondagem posteriores, pois uma busca pode parar cedo pensando que não há mais elementos. Para contornar isso, usa-se a marcação de “tombstone” (ou seja, um estado especial “excluído”). Assim:
- ao excluir, você marca o slot como tombstone em vez de vazio;
- nas buscas e inserções, considera-se tombstone como ocupado para fins de continuação da sondagem;
- nas inserções, pode-se reutilizar o primeiro tombstone encontrado.
Passo 4
As circunstâncias especiais que precisam de atenção são:
- acúmulo de tombstones degrada o desempenho de buscas e inserções — por isso é comum rehashear (reconstruir toda a tabela, re-inserindo só os itens ativos) quando a proporção de tombstones ultrapassa certo limiar;
- se optarmos por não usar tombstones, podemos adotar o método de “recompactação”: excluído um elemento, readiciona-se todos os elementos seguintes na cadeia de sondagem para corrigir possíveis quebras — mas isso tem custo linear no pior caso;
- em tabelas com sondagem quadrática ou duplo hashing, o gerenciamento de tombstones deve respeitar a mesma sequência de sondagem, senão corre-se o risco de perder elementos.
Passo 5
Em resumo:
– Com encadeamento, basta remover o nó da lista ligada no bucket correspondente.
– Com endereçamento aberto, marque o slot como tombstone em vez de vazio, mantendo a sondagem funcional, e faça rehash ou recompactação periódica para não acumular lixo.
– Com encadeamento, basta remover o nó da lista ligada no bucket correspondente.
– Com endereçamento aberto, marque o slot como tombstone em vez de vazio, mantendo a sondagem funcional, e faça rehash ou recompactação periódica para não acumular lixo.
Resposta
Para separate chaining, simplesmente removemos o nó da lista ligada no bucket de índice
. Para open addressing, não podemos deixar o slot vazio: marcamos como tombstone (excluído) para não interromper sondagens. As circunstâncias especiais são o acúmulo de tombstones (que exige rehash periódico) e, caso não usemos tombstones, a necessidade de recompactar/reinserir elementos seguintes para preservar cadeias de sondagem.