Question

Write an algorithm to delete an element from a hash table that uses linear probing as its clash resolution strategy. Analyze your algorithm and show the results using order notation?

Answer 1

Theory:

A hash table using linear probing for collision/ clash detection works with modulus as the hash function and the function looks as follows

h(key) = key % size

here key the value for which the have to be inserted into hash table.

size is the size of the hash table.

If the block calculated by the key is filled then it is called collision, and in that case, the resolution is to find a key such that

h(key + i) for all i= 1 .. size

and place the key in block where ever place is free or alert user that table is full.

In the same way deletion is as follows

Algorithm:

Note: step 2.1 checks the if the value at index calculated by the hash function h(x) with x as key + i contains key as asked by user

Note: removing element is implementation(language) dependent and at the ouset removing removes the value found at that index from hashTable.

1. input the key to be deleted from user.

2. found = 0

2. for i = 0 ... size

2.1. if hashTable[h(key + i)] == key then

2.1.1. remove the element

2.1.2. found = 1

2.1.3. break

3. if not found

3.1. print " key not found in hash table"

4. else

4.1. print "element deleted"

Analysis:

considering the worst case scenario we have to search all the blocks in the hash Table i.e, size

since, the hash function h(key) takes O(1) complexity.

running the loop 2.1 executes h(key) * size times

Note: This means that h(key) will be executed n times where n is equal to size

i.e, 1 * size

Note:( h(key) takes O(1); size is a variable)

therefore, deletion takes O(1 * size) => O(size) time to remove an element in worst case.

Therefore it is a liner time algorithm in worst case.

and in best case it is constant time, as it is found in the first iteration itself.

Coming to space complexity, it uses only one extra variable i.e, found, therefore space complexity is O(1).

i.e, time: O(size) or O(n)

space: O(1)

Hope your problem solved and you are appreciating this solution,

feel free to ask doubts in comment section.