Deletion is impossible without possibly restructuring the entire hash table. Let us define K1 to be a set of keys that collide. For the sake of our discussion, the collection of the slots of all the elements in K1 is called the (collision) pile of K1.
Let us define K2 to be another set of keys that collide, but to a different hash value than those in K1.
Let us assume that we want to remove an item with the key value k1 ∈ K1. Using the look up function, we can easily locate it. Deleting it is as easy as marking the slot is unused. However, this leaves a hole in the slots corresponding to elements in K1. The lookup function stops when it sees this empty slot (instead of continuing with the other slots).
Even if we can track all items in the hash table corresponding to elements in K1, and get them all restructured correctly, we still have a second problem. It is possible to find that ∃k1 ∈ K1,k2 ∈ K2,i,j ∈ [0..n − 1] : f(k1,i) = f(k2,j). In other words, two piles of collision can intersect!
Given that the collision piles of K1 and K2 can intersect, any changes to the collision pile of K1 can cause problems with the collision pile of K2.