Il modo migliore per rimuovere una voce da una tabella hash

Question

Qual è il modo migliore per rimuovere una voce da una tabella hash che utilizza il probing lineare? Un modo per farlo sarebbe usare un flag per indicare elementi cancellati? Esistono modi migliori di questo?

Answer 1

Una tecnica semplice è:

1. Trova e rimuovi l'elemento desiderato
2. Vai al secchio successivo
3. Se il bucket è vuoto, esci
4. Se il bucket è pieno, elimina l'elemento in quel bucket e aggiungilo nuovamente alla tabella hash usando i mezzi normali. L'articolo deve essere rimosso prima di aggiungere nuovamente, perché è probabile che possa essere aggiunto nuovamente nella sua posizione originale.
5. Ripeti il ??passaggio 2.

Questa tecnica mantiene il tuo tavolo in ordine a spese di eliminazioni leggermente più lente.

Answer 2

Dipende da come gestisci l'overflow e se (1) l'elemento da rimuovere si trova in uno slot di overflow o meno, e (2) se ci sono elementi di overflow oltre l'elemento da rimuovere, se hanno la chiave hash del oggetto da rimuovere o eventualmente qualche altra chiave hash. [Trascurare quella doppia condizione è una fonte comune di bug nelle implementazioni di eliminazione.]

Se le collisioni traboccano in un elenco collegato, è abbastanza facile. Stai spuntando la lista (che potrebbe essere vuota) o stai eliminando un membro dalla metà o dalla fine della lista collegata. Sono divertenti e non particolarmente difficili. Ci possono essere altre ottimizzazioni per evitare allocazioni e liberazioni di memoria eccessive per renderlo ancora più efficiente.

Per sondaggi lineari, Knuth suggerisce che un approccio semplice è quello di avere un modo per contrassegnare uno slot come vuoto, cancellato o occupato. Contrassegna uno slot occupante rimosso come cancellato in modo che l'overflow per sondaggio lineare lo salti, ma se è necessario un inserimento, puoi riempire il primo slot eliminato che hai passato su [The Art of Computer Programming, vol.3: Sorting and Searching , sezione 6.4 Hashing, p. 533 (ed. 2)]. Ciò presuppone che le eliminazioni siano piuttosto rare.

Knuth dà un bel perfezionamento come Algorithm R6.4 [pp. 533-534] che invece contrassegna la cella come vuota anziché eliminata, quindi trova i modi per spostare le voci della tabella più vicino alla loro posizione della sonda iniziale spostando il foro che è stato appena creato fino a quando non finisce accanto a un altro foro.

Knuth avverte che questo sposterà le voci degli slot ancora occupate esistenti e non è una buona idea se i puntatori agli slot vengono mantenuti all'esterno della tabella hash. [Se hai slot garbage collection o altri riferimenti gestiti negli slot, va bene spostare lo slot, poiché è il riferimento che viene utilizzato al di fuori della tabella e non importa dove lo slot che fa riferimento lo stesso oggetto è nella tabella.]

Answer 3

L'implementazione della tabella hash di Python (discutibile molto velocemente) utilizza elementi fittizi per contrassegnare le eliminazioni. Mentre cresci o riduci o tabella (supponendo che tu non stia facendo una tabella di dimensioni fisse), puoi far cadere i manichini allo stesso tempo.

Se hai accesso a una copia, dai un'occhiata all'articolo in Codice bellissimo sull'implementazione.

Answer 4

Le migliori soluzioni generali a cui riesco a pensare sono:

• Se puoi usare un iteratore non const (ala C ++ STL o Java), dovresti essere in grado di rimuoverli quando li incontri. Presumibilmente, tuttavia, non porteresti questa domanda a meno che tu non stia utilizzando un const iteratore o un enumeratore che sarebbe invalidato se la raccolta sottostante fosse modificata.
• Come hai detto, puoi contrassegnare un flag cancellato all'interno dell'oggetto contenuto. Questo non libera memoria né riduce le collisioni sulla chiave, quindi non è la soluzione migliore. Richiede anche l'aggiunta di una proprietà sulla classe che probabilmente non appartiene realmente a tale classe. Se questo ti dà fastidio quanto me, o se semplicemente non puoi aggiungere un flag all'oggetto memorizzato (forse non controlli la classe), potresti archiviare questi flag in una tabella hash separata. Ciò richiede l'uso della memoria più a lungo termine.
• Spingi le chiavi degli elementi da rimuovere in un elenco di vettori o di array mentre attraversi la tabella hash. Dopo aver rilasciato l'enumeratore, scorrere questo elenco secondario e rimuovere le chiavi dalla tabella hash. Se hai molti elementi da rimuovere e / o le chiavi sono grandi (cosa che non dovrebbero essere), questa potrebbe non essere la soluzione migliore.
• Se finirai per rimuovere più elementi dalla tabella hash di quanti ne lasci lì, potrebbe essere meglio creare una nuova tabella hash e mentre attraversi quella originale, aggiungi alla nuova hash tabella solo gli oggetti che hai intenzione di conservare. Quindi sostituisci i tuoi riferimenti alla vecchia tabella hash con quella nuova. Ciò consente di salvare una ripetizione dell'elenco secondario, ma probabilmente è efficace solo se la nuova tabella hash avrà un numero significativamente inferiore di elementi rispetto a quella originale, e sicuramente funzionerà solo se è possibile modificare tutti i riferimenti alla tabella hash originale, ovviamente.
• Se la tua tabella hash ti dà accesso alla sua raccolta di chiavi, potresti essere in grado di scorrere attraverso quelle e rimuovere elementi dalla tabella hash in un unico passaggio.
• Se la tua tabella hash o qualche helper nella tua libreria ti fornisce modificatori di raccolta basati su predicati, potresti avere una funzione Remove () a cui puoi passare un'espressione lambda o un puntatore a funzione per identificare gli elementi da rimuovere.

Answer 5

Una tecnica comune quando il tempo è un fattore è quella di avere una seconda tabella di elementi eliminati e ripulire la tabella principale quando hai tempo. Comunemente utilizzato nei motori di ricerca.

Answer 6

Che ne dici di migliorare la tabella hash per contenere i puntatori come un elenco collegato? Quando si inserisce, se il bucket è pieno, creare un puntatore da questo bucket al bucket in cui è memorizzato il nuovo campo.

Durante l'eliminazione di qualcosa dalla tabella hash, la soluzione sarà equivalente a come si scrive una funzione per eliminare un nodo dalla lista collegata.