I still don't see it. let's say my table (array) is size 10, and the keys I want to insert are: 3,13,23,33,43.
so if I use linear probing, it's inserted as follows:
1)hash(3) = 3 % size so insert @ index 3 so current table:
Code:
int table[10] = {0,0,0,3,0,0,0,0,0,0}
2)hash(13) = 13 % size so insert @ index 3, BUT it's occupied so insert @ (3 + 1)%size so index 4:
Code:
int table[10] = {0,0,0,3,13,0,0,0,0,0}
3)hash(23) = 23 % size so insert @ index 3, BUT it's occupied so insert @ (3 + 1) % size BUT also taken, so (3 + 2 ) % size so index 5:
Code:
int table[10] = {0,0,0,3,13,23,0,0,0,0}
then hash(33), hash(43) so
Code:
int table[10] = {0,0,0,3,13,23,33,43,0,0}
Now to remove 23:
==============
1) hash(33) to jump to where key 33 should be: so 33 % size = 3, not there, then check (3 + 1)%size so index 4, not there etc until we find it @ index 6. So why not just set the value to 0 which means 'empty' rather than have to disgtinguish w/ a marker (let's say -1 to imply a deleted index)? Let's say I use -1 for deleted, rather than 0 (to indicate empty slot) so:
Code:
int table[10] = {0,0,0,3,13,23,-1,43,0,0}
Now search 33:
===========
1) hash(33) to jump to where key 33 should be: so 33 % size = 3, not there, etc until we hit index 6: -1 (marker to mean: 'deleted'), so we conclude key is NOT in list rather than having to traverse entire table (which would be O(n) time which is not good), but how would can we just assume that just b/c we hit a deleted index (marker of -1 @ index 6 in this case), that the key wasn't in list. Index 6 could've stored a key of 83. That's why I am a little confused. I really don't see how removal of a key makes it so detrimental to the data structure. All sources (online and books) all point out importance to disgtinguish b/t 'delete' vs 'empty' (so what the indices are initially).
Here is the quote from Eternally confuzzled:
Removal in any open addressing strategy is where things get interesting. A direct removal is not possible because future probes could rely on the key being removed, and if an empty bucket is created where a full bucket once was, searches will incorrectly fail. All in all, the obvious way to remove from a hash table with open addressing will destroy the data structure and cause it to work improperly. With linear probing, it is possible to remove a key and then re-insert each of the keys in the same cluster, but that solution is somewhat complicated.
A more general solution that works for all of the open addressing schemes is to mark a bucket as deleted in such a way so that searches will not fail.
here is the source:Eternally Confuzzled - Hash Table Tutorial
Appreciate all the help to see what I am missing here. If someone can point out what I am not getting, that would make my day.