Como excluir itens de uma tabela hash que usa encadeamento para tratar colisões? E 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 i = h(key);
2) percorrer a lista ligada em tab<=[i] 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.

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:
  1. ao excluir, você marca o slot como tombstone em vez de vazio;
  2. nas buscas e inserções, considera-se tombstone como ocupado para fins de continuação da sondagem;
  3. nas inserções, pode-se reutilizar o primeiro tombstone encontrado.

Passo 4

As circunstâncias especiais que precisam de atenção são:
  1. 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;
  2. 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;
  3. 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.

Resposta

Para separate chaining, simplesmente removemos o nó da lista ligada no bucket de índice h(key). 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.

Exercícios relacionados