Assume the utilization of linear probing for hashtables To e

Assume the utilization of linear probing for hash-tables. To enhance the complexity of the operations performed on the table, a special AVAILABLE object is used. Assuming that all keys
are positive integers, the following two techniques were suggested in order to enhance complexity:

i) In case an entry is removed, instead of marking its location as AVAILABLE, indicate the key as the negative value of the removed key (i.e. if the removed key was 16, indicate the key as -16). Searching for an entry with the removed key would then terminate once a negative value of the key is found (instead of continuing to search if AVAILABLE is used).

ii) Instead of using AVAILABLE, find a key in the table that should have been placed in the location of the removed entry, then place that key (the entire entry of course) in that location (instead of setting the location as AVAILABLE). The motive is to find the key faster since it now in its hashed location. This would also avoid the dependence on the AVAILABLE object.

Will either of these proposal have an advantage of the achieved complexity? You should analyze both time-complexity and space-complexity. Additionally, will any of these approaches result in misbehaviors (in terms of functionalities)? If so, explain clearly through illustrative examples.

Solution

Consider the following layout of the hash table.

SLOT KEY

2      EMPTY

3      103

4      404

5      203

6      EMPTY

Let\'s assume we are searching for key 203. Its hash is 3 so we start in slot 3. Slot 3 contains the wrong key, slot 4 also contains the wrong key, but slot 5 contains the right key and we found the key and its value(But not shown here).

If we were searching for key 303 we would need to continue searching in slot 6. However slot 6 is EMPTY, so we can be sure that the value is not in the hash table.

So lets take a look at 2 methods of deleting key 103 from the table:

Method 1: Special Value

The table essentially becomes this after deleting key 103:

SLOT KEY

2      EMPTY

3      AVAILABLE

4      404

5      203

6      EMPTY

The Question is Why can\'t we set it to EMPTY? Because if we were searching for 203 we would start at slot 3, find that it\'s EMPTY and stop (although the key is indeed in the table). However, slot 3 is not EMPTY but AVAILABLE. Because of that while searching for key 203 we just skip slot 3 and continue with slots 4 and 5 and finally find it.

Method 2: Finding Another Key To Move Up

We want to delete 103 from the original table again. This time we don\'t want to use AVAILABLE though:

SLOT KEY

2      EMPTY

3      ???

4      404

5      203

6      EMPTY

As explained above, we cannot just put EMPTY in there, because we would be unable to find key 203. For the new method we must search for another key with a hash which is equal to or less than the id of the ??? slot. We find key 203 in slot 5. Now we move this key (and its value) to the ??? slot:

SLOT KEY

2      EMPTY

3      203

4      404

5      ???

6      EMPTY

However, we now need to find something to put in slot 5. We must keep searching for more keys to move until we find an EMPTY slot. In this example, the next slot is EMPTY, so we can set slot 5 to EMPTY as well.

SLOT KEY

2      EMPTY

3      203

4      404

5      EMPTY

6      EMPTY

Now the key 203 has moved up and we can still find it if we search for it.

I hope you understand the two different methods of deletion now and can determine the different complexities for each operation.

For method 1 you just need to put AVAILABLE in the slot which is a constant amount of work.

And for method 2 you need to move stuff around which is of course a little more complex (hint).

However if we search for key 203 after the deletion we need to inspect 3 slots for method 1 and only 1 slot for method 2.

Also if you do a variable amount of work (do something for n elements) this is not constant, but linear complexity.