Medium
Erasing from a linear-probing table by emptying the slot
This fixed-size open-addressing table uses linear probing and erases a key by resetting its slot to EMPTY. Keys 3, 11, and 19 all have home slot 3. After the calls below, what is found, and what is the general fix?
main.cpp
// Capacity 8, home slot = key % 8, linear probing.
struct Table {
static constexpr int EMPTY = -1;
int slot[8];
Table() { std::fill(slot, slot + 8, EMPTY); }
void insert(int key) {
int i = key % 8;
while (slot[i] != EMPTY) i = (i + 1) % 8;
slot[i] = key;
}
bool contains(int key) const {
for (int i = key % 8; slot[i] != EMPTY; i = (i + 1) % 8)
if (slot[i] == key) return true;
return false;
}
void erase(int key) {
for (int i = key % 8; slot[i] != EMPTY; i = (i + 1) % 8)
if (slot[i] == key) { slot[i] = EMPTY; return; }
}
};
Table t;
t.insert(3); t.insert(11); t.insert(19);
t.erase(11);
bool found = t.contains(19);40 of 46 in Data Structures & Algorithms