Melhor maneira de remover uma entrada de uma tabela hash

Question

O que é a melhor maneira de remover uma entrada de uma tabela hash que usos linear sondagem? Uma maneira de fazer isso seria usar uma bandeira para indicar elementos excluídos? Há alguma maneira melhor do que isso?

Answer 1

Uma técnica simples é:

1. Encontrar e remover o elemento desejado
2. Vá para a próxima balde
3. Se o balde estiver vazio, saia
4. Se o balde está cheio, exclua o elemento em que balde e adicioná-lo novamente para a tabela hash usando os meios normais. O item deve ser removido antes de re-adição, porque é provável que o item pode ser adicionado de volta para sua exata original.
5. Repita o passo 2.

Esta técnica mantém o seu arrumado tabela à custa de eliminações ligeiramente mais lentas.

Answer 2

Depende de como você lida com estouro e se (1) o item a ser removido está em um slot de estouro ou não, e (2) se há itens de estouro além do item que está sendo removido, se eles têm a chave hash do artigo a ser removido ou possivelmente alguma outra chave da mistura. [Com vista que dupla condição é uma fonte comum de erros em implementações de eliminação.]

Se colisões transbordar em uma lista ligada, é muito fácil. Ou você está aparecendo na lista (que pode ter ido vazia) ou exclusão de um membro do programa a partir do meio ou no fim da lista ligada. Aqueles são divertidos e não é particularmente difícil. Pode haver outras otimizações para evitar alocações de memória excessivas e freeings para tornar isso ainda mais eficiente.

Para linear sondagem, Knuth sugere que uma abordagem simples é ter uma maneira de marcar um slot como vazio, apagado, ou ocupados. Marcar um slot ocupante removido como excluído assim que transbordam por linear sondagem vai pular, mas se uma inserção é necessária, você pode preencher o slot primeira excluídos que você passou [The Art of Computer Programming, vol.3: classificação e pesquisa , secção 6.4 hashing, p. 533 (Ed.2)]. Isso pressupõe que exclusões são bastante raros.

Knuth dá um bom Refinamento como Algoritmo R6.4 [pp. 533-534] que, ao invés marcas da célula como vazia em vez de excluído e, em seguida, encontra maneiras de mover entradas da tabela de volta para perto de sua localização inicial-sonda movendo o buraco que foi feito apenas até acabar ao lado de outro buraco.

precauções Knuth que isso vai mover entradas de caça-níqueis ainda ocupados existente e não é uma boa idéia se os ponteiros para os slots estão sendo realizadas para fora da tabela de hash. [Se você tem referências gerenciadas lixo-collected- ou outra nos slots, está tudo certo para mover o slot, uma vez que é a referência que está a ser utilizado fora da mesa e não importa onde o slot que referências o mesmo objeto está na mesa.]

Answer 3

O Python implementação de tabela de hash (discutível muito rápido) utiliza elementos fictícios para eliminações marca. À medida que crescer ou encolher ou mesa (supondo que você não está fazendo uma tabela de tamanho fixo), você pode soltar os manequins, ao mesmo tempo.

Se você tem acesso a uma cópia, ter um olhar para o artigo na Beautiful código sobre a implementação.

Answer 4

As melhores soluções gerais que posso pensar incluem:

• Se você é pode usar um const não-iterator (ala C STL ++ ou Java), você deve ser capaz de removê-los como você encontrá-los. Presumivelmente, porém, você não estaria fazendo esta pergunta a menos que você estiver usando um iterador const ou um recenseador que seria invalidado se a coleção subjacente é modificado.
• Como você disse, você poderia marcar uma bandeira eliminado dentro do objeto contido. Isto não libera qualquer memória ou reduzir colisões na chave, embora, por isso não é a melhor solução. requer também a adição de uma propriedade na classe que provavelmente não pertence realmente lá. Se Incomoda tanto quanto ele me faria, ou se você simplesmente não pode adicionar um sinalizador para o objeto armazenado (talvez você não controla a classe), você pode armazenar esses sinalizadores em uma tabela hash separado. Isso requer o uso de memória mais longo prazo.
• Empurre as chaves dos itens a-ser-removidos em uma lista vetor ou matriz ao atravessar a tabela hash. Depois de lançar o entrevistador, percorrer esta lista secundário e remover as chaves de tabela hash. Se você tem um monte de itens para remover e / ou as teclas são grandes (que não deve ser), isso pode não ser a melhor solução.
• Se você está indo para acabar remover mais itens da tabela hash que você está deixando lá dentro, pode ser melhor para criar uma nova tabela hash, e à medida que atravessa o seu original, adicionar ao novo hash mesa apenas os itens que você vai manter. Em seguida, substitua sua referência (s) para a tabela hash antigo com o novo. Isso economiza uma lista iteração secundária, mas é provavelmente apenas eficiente se a nova tabela hash terá significativamente menos itens do que o original, e definitivamente só funciona se você pode mudar todas as referências à tabela hash original, é claro.
• Se a sua tabela hash dá-lhe acesso à sua coleção de chaves, você pode ser capaz para percorrer os e remover itens da tabela hash em uma passagem.
• Se a sua tabela hash ou algum ajudante em sua biblioteca fornece-lhe com modificadores de coleta baseadas em predicados, você pode ter uma função Remove () para que você pode passar um ponteiro expressão ou função lambda para identificar os itens para remover.

Answer 5

Uma técnica comum quando o tempo é um fator é ter uma segunda tabela de itens excluídos, e limpar a mesa principal quando tiver tempo. Comumente usado em motores de busca.

Answer 6

Como sobre como melhorar a tabela hash para conter ponteiros como uma lista ligada? Quando você insere, se o balde está cheio, criar um ponteiro a partir deste balde para o balde onde o novo campo na armazenado.

Enquanto apagar algo da hashtable, a solução será equivalente à forma como você escrever uma função para excluir um nó de LinkedList.