Linear Probing: Exercise II
Consider the state of the hash table at the end of the previous exercise; we want to perform two more operations:
| [ 0 ] | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | [ 5 ] | [ 6 ] | Output | |
|---|---|---|---|---|---|---|---|---|
| Current State | 86 | 700 | 5005 | 1111 | 2332 | 8333 | ||
remove(2332) | ||||||||
find(8333) |
Exercise Complete the table above as you carry out the operations. Do you see any (potential) issues with the remove operation?
Solution
| [ 0 ] | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | [ 5 ] | [ 6 ] | Output | |
|---|---|---|---|---|---|---|---|---|
| Current State | 86 | 700 | 5005 | 1111 | 2332 | 8333 | ||
remove(2332) | 86 | 700 | 5005 | 1111 | 8333 | |||
find(8333) | 86 | 700 | 5005 | 1111 | 8333 | 3,4,5: NF |
$$ (2 + 3 + 3 + 2) \bmod 7 = 3 $$
Lookup $2332$ at position with index $3$. The position is occupied but the occupant is not the target! Linear probing will take us to index $4$ and then index $5$ where the element can be found. We can now remove (delete) the element.
$$ (8 + 3 + 3 + 3) \bmod 7 = 3 $$
Lookup $8333$ at position with index $3$. The position is occupied but the occupant is not the target! Linear probing will take us to index $4$ and then index $5$ which is empty. At this point, the algorithm will assume $8333$ is not in the Hash Table because if it was, it would have been inserted at index $5$. Therefore, it will return NOT_FOUND.