Can you explain your new algorithm in simple terms? I see you don't
use a "deletedKey" tag, so I don't see how it can work (i.e. I believe there is still a bug but I'm too lazy to examine your algo in detail).
It works under the assumption that there is no key for deleted items, and that clusters of stored items are always contiguous.
When an item mapping to index K in the internal array is removed, items after it in its cluster may need to be moved. More specifically, if another item in the cluster maps to index K, it needs to be moved to the position of the removed item, so that there is no "hole" in the cluster. However, this poses a problem, because moving an item in the cluster to the "left" may create a new hole at the position of the item that was just moved, which could break the lookup of other items that map to the "left" or at the position of the moved item.
The algorithm I implemented scans, starting at the position where the removed item maps, until a free slot is encountered (until the end of the cluster). It keeps track of the position of the removed item (the "hole" we just created), and, for each item until the end of the cluster, moves it into the "hole" only if its key maps to the "left" of, or at the position of the hole. If an item is moved into the "hole", the position of the "hole" is updated, and the process keeps going until the end of the cluster. When the end of the cluster is reached, the hole is marked as being free.
All the algorithm really does is move items in a cluster closer to the position where their key maps.
My assumptions are that: 1. The algorithm can't move an item "before" the position where its key maps. Items remain at or after this position. 2. The algorithm can't make a cluster of values mapping to the same index non-contiguous. 3. If a hole was created in a cluster, then there can be no item after the hole whose key maps after the position of the hole (or before that position). Otherwise, it would have been moved into the hole.
I believe these are sufficient not to break the structure of the hash table's internal array, but feel free to tell me if my algorithm is broken.
- Maxime