Explanation of how to remove an element from a hash table with quadratic probing collision resolution:
Remove the element (x) by placing the dummy value "gone" into the bucket x hashes to.
Now when doing subsequent inserts (say with element y), we skip over the gone in the normal quadratic style, stopping when we hit an empty bucket or the bucket that y hashed to initially. If we hit an empty bucket we insert y into it and stop. In order to guarentee that we get back to y's original bucket by repeated squaring, we must make the size of the table a prime number. When arriving at the original number, we are obviously in a cycle and will be unable to insert the element.
Note in linear probing this is easier because we know that we will not be able to insert merely if the table is full. In quadratic probing it is somewhat more difficult in that we actual have to probe before we can find out if the insert will be successful.
mmaxim