I am working on a hashmap and having trouble with the remove function of a double hashing open address-style map. Lets say I insert on a table of size 10, and my 2 hash functions are as follows:
int hash( int key, std::size_t M ) { return key % M; }
int hash2( int key, std::size_t M ) { return key % (M-1) + 1; }
If I insert items with key 0, 10, and 20, the items will go to positions 0, 2, and 3.
<[ 0:A, - , 10:B, 20:C, - , - , - , - , - , - ]>
When removing an item, however, I want to remove the item AND rehash the following items in the same cluster. When I remove, say, item with key 0, it finds the item to remove no problem. But, it now needs to jump to index 2 - BUT IT CANT BECAUSE ITS USING THE KEY 0 AS ITS INCREMENT, so it jumps to index 1 instead. So, it will never find the subsequent items in the cluster. How do I do this???
In general you delete an item by placing a deleted marker in that position. For the purpose of searching, it is occupied, so items that collided and require probing to find are not orphaned. But when inserting, you can reuse that spot. If the number of deleted markers in your table becomes large, you can rehash the table to clean it up.
This lecture explains in more detail: Open Addressing