Hash table open addressing removing: what could happen if we search for a removed key (which we don't know) is replaced by a tombstone? since the key is not existing, will the search become an infinite loop to keep probing and find the key?
See the screenshot from William Fiset's data structure course -- what if k3 is already removed or not exist the hashtable orginally? looks like we keep probing until find k3? enter image description here
When looking for a key, you keep probing until you find the key, or get to an empty slot (note that a "removed" slot is not empty). If you get to an empty slot, you know the key is not present. As long as there is at least one empty slot, you'll eventually get to it. This potential looping is why open hash tables generally limit their occupancy to not get too large, as the greater the occupancy (fewer empty slots), the longer you need to loop until you get to an empty slot when searching for a not-present key.
