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