Open addressing is a method of resolving hash collisions by probing or searching through alternative locations in the table until either the target entry is found or an unused slot is found.
When entries are removed from a hash table that uses open addressing the empty space makes the probing / searching algorithms terminate early.
One solution to prevent this is to mark deleted elements as "tombstones" which allows the searching algorithm to continue when it encounters one instead of failing. After a lot of removals "tombstones" can clog up the hash table so periodically the hashes for the whole table should be recomputed.
Linear probing is a method of open addressing in which the index is incremented once every time a collision is found until the record or an open slot is found.
For example if there is a collision at the index
Quadratic probing is a method of open addressing in which the index is incremented linearly once every time a collision is found until the record or an open slot is found.
For example if there is a collision at the index
Double hashing is a method of open addressing in which the in which the index is incremented by a second hash function of the key when a collision is encountered. For the second hash function an additional rule that it must never return 0 is introduced.