Algoritmo di hash: eliminazione di un elemento nel sondaggio lineare

Question

Algoritmo di hash: eliminazione di un elemento nel sondaggio lineare

#1 da (7 voti)

5

Mentre utilizziamo il metodo di sondaggio lineare per implementare l'hashing, quando cancelliamo ed elemento, la posizione dell'elemento eliminato viene dichiarata come lapide / contrassegnata come cancellata. Perché non possiamo semplicemente spostare tutti gli elementi dalla posizione corrente finché non viene rilevato il prossimo elemento vuoto? Questo non risparmierà il tempo in cui troppe pietre tombali verranno scoperte in seguito e potrebbe essere necessario un rimontaggio? Mi sto perdendo qualcosa? Per favore, dimmi se ho bisogno di chiarire la mia domanda.

Grazie mille!

algorithms hashing

posta P Ramesh 23.08.2013 - 19:45

fonte

1 risposta

Leggi altre domande sui tag algorithms hashing

Progettazione della parte CRUD di un'API HTTP Come posso eseguire il bootstrap di un servizio P2P in modo che gli utenti possano localizzarsi a vicenda?

score 7 · Accepted Answer

La migliore spiegazione per esempio contatore:

HASH(A) = 10
HASH(B) = 10
HASH(C) = 12

myHash.insert(A); // A goes to slot 10

              10   11   12
            +----+----+----+
            | A  |    |    |
            +----+----+----+

myHash.insert(B); // B goes to slot 10, but that is taken, so it sees 11 is empty and inserts there

              10   11   12
            +----+----+----+
            | A  | B  |    |
            +----+----+----+

myHash.insert(C); // C hashes to slot 12 and gets put there

              10   11   12
            +----+----+----+
            | A  | B  | C  |
            +----+----+----+

myHash.remove(B); // We remove B, and shift the ones after it back

              10   11   12
            +----+----+----+
            | A  | C  |    |
            +----+----+----+

myHash.contains(C) == false; // C hashes to slot 12, but there is nothing there.  So therefore the hash does not contain C (but it does CONTRADICTION).

Pertanto, con la prova della contraddizione, semplicemente facendo scorrere gli elementi successivi alla rimozione si otterrà un errore.

EDIT : C avrebbe dovuto dire che ha hash a 12