What you have to do is walk the linear (or whatever) probe sequence completely to find two elements: the to-be-deleted element, and the last element in the sequence. Then if the to-be-deleted element exists, and is the same as the last element, we just mark that element as a free slot. Otherwise, we move the last element over the to-be-deleted element and mark last element's slot free.
Of course, "the last element" has to be one which belongs to the original starting hash slot S. We must check that its hash value odulo the table size is S. The first element that we encounter which not followed by an occupied slot is not necessary that last element.
Otherwise, we move the last element over the to-be-deleted element and mark last element's slot free.
That doesn't work at all.
Consider a hash table of size 5: [Foo, Bar, 0, 0, 0], where 0 represents "empty" locations. Assume "Foo" is in "slot#0" (0-indexed arrays. Note that Knuth in The Art of Computer Programming works with 1-indexed arrays)
Lets say we delete Foo. Bar does NOT necessarily want to go into location #0. For example, hash(Bar) might == 1 (in the case of linear probing). So in this case, we want to leave Bar exactly where it is.
That's why I have the "if(hash(array[i].value) <= idx){" line in the code. However, this conditional seems impossible to write in the case of quadratic (or other forms) of hashing. This if-statement ONLY works on linear-probing.
----------
Consider this other pattern (still Quadratic probing): [Foo, Bar, 0, 0, Foo2], where Hash(Foo) == Hash(Foo2) == 0.
While Hash(Bar) == 1.
Lets say you want to delete Bar. How do you know to "move" Foo2 into Slot#1 ? You don't. There's no easy pattern to check for here. Quadratic-probing requires the tombstone method.
----------
The code I presented is very subtle (subtle enough that I probably have a few bugs in it). It works because linear probing has a very predictable sequence.
Quadratic probing, and other forms of probing (ex: double hashing, Cuckoo hashing, etc. etc.) are very irregular, and hard to figure out if an object "should" be moved back.
------------
There's a lot of ways of thinking about this problem. But I'm pretty sure the description you gave is incorrect.
My preferred way of understanding the problem is as follows:
1. Upon any deletion, you want to perform a set of operations that is equivalent to rebuilding the Hash Table from scratch.
2. The procedure I listed before, is provably equivalent to rebuilding the hash table from scratch. (Most elements stay where they are). At least, if I didn't write a bug in it accidentally...
--------
The first element that we encounter which not followed by an occupied slot is not necessary that last element.
I disagree.
An empty slot, __in the case of linear probing__, guarantees that you've finished the chaining sequence.
That's why linear probing is best. Because you have simple guarantees for which objects are part of a "collision chain", and which ones aren't.
This means that deletion under linear-probing can be implemented efficiently. But deletion under other probing schemes (ex: Quadratic) requires the inefficient "tombstone and vacuum" procedure you were describing.
There's a lot of subtleties at play here which makes linear probing the best. And a lot of textbooks get these details wrong (ex: the Cormen book!!).
Comments
What you have to do is walk the linear (or whatever) probe sequence completely to find two elements: the to-be-deleted element, and the last element in the sequence. Then if the to-be-deleted element exists, and is the same as the last element, we just mark that element as a free slot. Otherwise, we move the last element over the to-be-deleted element and mark last element's slot free.
Of course, "the last element" has to be one which belongs to the original starting hash slot S. We must check that its hash value odulo the table size is S. The first element that we encounter which not followed by an occupied slot is not necessary that last element.
That doesn't work at all.
Consider a hash table of size 5: [Foo, Bar, 0, 0, 0], where 0 represents "empty" locations. Assume "Foo" is in "slot#0" (0-indexed arrays. Note that Knuth in The Art of Computer Programming works with 1-indexed arrays)
Lets say we delete Foo. Bar does NOT necessarily want to go into location #0. For example, hash(Bar) might == 1 (in the case of linear probing). So in this case, we want to leave Bar exactly where it is.
That's why I have the "if(hash(array[i].value) <= idx){" line in the code. However, this conditional seems impossible to write in the case of quadratic (or other forms) of hashing. This if-statement ONLY works on linear-probing.
----------
Consider this other pattern (still Quadratic probing): [Foo, Bar, 0, 0, Foo2], where Hash(Foo) == Hash(Foo2) == 0.
While Hash(Bar) == 1.
Lets say you want to delete Bar. How do you know to "move" Foo2 into Slot#1 ? You don't. There's no easy pattern to check for here. Quadratic-probing requires the tombstone method.
----------
The code I presented is very subtle (subtle enough that I probably have a few bugs in it). It works because linear probing has a very predictable sequence.
Quadratic probing, and other forms of probing (ex: double hashing, Cuckoo hashing, etc. etc.) are very irregular, and hard to figure out if an object "should" be moved back.
------------
There's a lot of ways of thinking about this problem. But I'm pretty sure the description you gave is incorrect.
My preferred way of understanding the problem is as follows:
1. Upon any deletion, you want to perform a set of operations that is equivalent to rebuilding the Hash Table from scratch.
2. The procedure I listed before, is provably equivalent to rebuilding the hash table from scratch. (Most elements stay where they are). At least, if I didn't write a bug in it accidentally...
--------
I disagree.
An empty slot, __in the case of linear probing__, guarantees that you've finished the chaining sequence.
That's why linear probing is best. Because you have simple guarantees for which objects are part of a "collision chain", and which ones aren't.
This means that deletion under linear-probing can be implemented efficiently. But deletion under other probing schemes (ex: Quadratic) requires the inefficient "tombstone and vacuum" procedure you were describing.
There's a lot of subtleties at play here which makes linear probing the best. And a lot of textbooks get these details wrong (ex: the Cormen book!!).