Hash-Table Using Linear Probing Assessment Answer

Deletion in open addressing approach in hashing like linear probing and quadratic probing has to be handled with care.  Explain it with an example.   Then apply the minimum modification to the Python code given in slides 21-22 to implement linear probing (with both insertion and deletion).  The submission must include a brief report (no more than A4 2 pages).  The report must include a trace of the program execution demonstrating that the submitted program works properly.

Hash-table using Linear Probing

Deletion in open addressing approach in hashing like linear probing and quadratic probing has to be handled with care.

The Problem:

If not handled with care, it can give wrong results like ‘Not found to search query when key-value is present in hash-table’.

Solution:

We handle deletion using a special flag, lets call it 'linear_probing_flag'. Whenever we delete an key-value pair in hash-table, instead of filling empty position with None, we fill it with 'linear_probing_flag', and update the search logic accordingly in search and insert function.

Example:

Lets understand this with an example. We start with an empty hashtable with size 10.

We follow some set of insertions in hashtable followed by deletion. After each instruction, we print content of hashtable

• hash_table

[None, None, None, None, None, None, None, None, None, None]

• insert(hash_table,11,'Nepal')
• hash_table

[None, (11, 'Nepal'), None, None, None, None, None, None, None, None]

• insert(hash_table,12,'USA')
• hash_table

[None, (11, 'Nepal'), (12, 'USA'), None, None, None, None, None, None, None]

• insert(hash_table,14,'India')
• hash_table

[None,(11, 'Nepal'),(12, 'USA'),None,(14, 'India'),None,None,None,None,None]

• insert(hash_table,15,'Pak')
• hash_table

[None, (11, 'Nepal'),(12, 'USA'),None,(14, 'India'),(15, 'Pak'),None,None,None,None]

• insert(hash_table,4,'South Africa')
• hash_table

[None, (11, 'Nepal'),(12, 'USA'),None,(14, 'India'),(15, 'Pak'),(4, 'South Africa'),None,None,None]

• insert(hash_table,17,'Aus')
• hash_table

[None, (11, 'Nepal'),(12, 'USA'),None,(14, 'India'),(15, 'Pak'),(4, 'South Africa'),(17, 'Aus'),None,None]

• delete(hash_table,14)
• [None, (11, 'Nepal'),(12, 'USA'),None, 'linear_probing_flag' ,(15, 'Pak'),(4, 'SouthAfrica'),(17, 'Aus'),None,None]

Now if we search for key = 4, then if we may get “Not Found” result if we did not use special linear probing flag. But using linear probing flag, we update search logic that untill we find None entry in probing sequence we keep searching

• get(hash_table,4)
• 'South Africa'