To remove items from a hash table, you cannot simply seek the item and then make its location in the hash table empty. The reason is that the item might be part of a chain of items that have the same hash number. I will explain this with an example.
First, an element is stored with the key “apple”. This element ends up at index 10. Second, an element is stored with the key “banana”. This element ends up at the same hash number as “apple”, so it gets stored at index 11 (with “linear probing” and a perturbation value of 1). Then, the key “cherry” is used to store an element, which again ends up with the same hash number, and thus gets stored at index 12.
When “cherry” is searched for, the hash number indicates index 10, where “apple” is stored. Since this is not “cherry”, it checks index 11, where “banana” is stored. Since this is still not “cherry”, it checks index 12, and finds “cherry”.
Now, suppose that the element with the key “banana” is removed, by making the slot with index 11 empty. Then, when searching for “cherry”, the procedure first finds “apple”, and then an empty slot, so it concludes that “cherry” is not in the hash table. This is wrong.
How can this be solved? Should you move all the elements which are later in the chain to earlier places in the chain? No, that is not a good idea; not only is this an expensive procedure, but these elements might actually be part of different chains, so moving them is not allowed.
The solution is therefore to indicate that the slot where the item is removed from is “empty”, but still potentially part of a chain. Commonly, the key is left in the table, but the associated element is removed. This entails that the slot therefore might be overwritten, but is not considered the end of a chain.