Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

While using Linear probing method to implement hashing, when we delete and element, the position of the deleted element is declared as a tombstone/ mark it as deleted. Why can't we just shift all the elements from the current position until the next empty element is encountered? Won't this save the time when too many tombstones are encountered later and a rehashing might be required? Am I missing something? Please tell me if I need to clarify my question.

Thanks a lot!

share|improve this question

1 Answer 1

up vote 6 down vote accepted

Best explained by counter example:

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).

Therefore, by proof of contradiction, simply sliding the succeeding elements upon removal will result in incorrectness.

EDIT: C should have said that it hashes to 12

share|improve this answer
    
Yes, got it. Thanks! –  P Ramesh Aug 23 '13 at 18:05
    
@BobFincheirmer You example doesn't explain what happens if we remove A and then check hash.contains(B). –  duros Aug 23 '13 at 19:17
    
@duros It would work in that situation, but the point of the counter-example is to show it does not work in all situations –  Bob Fincheimer Aug 26 '13 at 15:16

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.