Thread: importance of distinguishing 'deleted' vs 'empty' indices via open addressing

Why is it so important to mark the difference? Why can't an item found just have its index marked as empty. For my trivial case, I'm thinking of initialize an array w/ empty signified by the value 0.

so:

Code:

int list[10] = {0,0,0,0,0,0,0,0,0,0};

So the function for removing an item could be:

Code:

int open_address_remove(int* list, int size; int key, int data)
{
  for ( int i = 0; i < size; ++i )
  {
    int cur_bucket = hash(key, i);

    if ( list[cur_bucket] == data )
    {
       list[cur_bucket] = 0;//Why do books, online tutorials make it so important to distinguish b/t empty and deleted indices?
      return cur_bucket;//return where the item to removed was found
     }
  }

  return -1;//return -1 to represent item-to-remove not found
}

Here is one very helpful link I used, it says to indicate a stop condition is when position == hash(key) but for my code above, coming full circle (so ensuriing all indices checked) is by the counter i so why this importance as this tutorial makes.
http://webdocs.cs.ualberta.ca/~holte/T26/open-addr.html

What am I not getting here? Appreciate all the help I can get.

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.

You have it the wrong way round!

Finding a DELETED entry means you have to keep looking. Finding an EMPTY entry means that the element is definitely not there and you can stop.

Originally Posted by monkey_c_monkey

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).

This would be:
3: occupied, no match
4: occupied, no match
5: occupied, no match
6: deleted (keep going)
7: occupied, no matrch
8: empty. Stop.

We can stop on empty because the 33 would have been stored there if it existed at all. Suppose you just used 0 for deleted:

Code:

int table[10] =  {0,0,0,3,13,23,0,43,0,0}

If you searched for 43, you'd stop at 6 if were considering empty to mean you can stop. Without marking things as deleted you'd have to look at every element (O(n), as you say).