Hash-Table Using Linear Probing Assessment Answer

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'