Delete operation in quadratic probing

The delete operation is another primary operation on a hash table. It deletes a key-value mapping from the hash table. Nothing is done if the key is absent in the hash table. The implementation is encapsulated in the delete function, which uses quadratic probing to search for the key in the internal array. Let us look at the algorithm and implementation of the delete operation in a hash table using quadratic probing.

Algorithm

The delete operation is also an extension of the search operation. Like the search operation, we calculate the index (hash code) for the given key and search the internal array for a record with the given key starting from the calculated index. We may need to consider three cases.

1. Key is present in the table

In this case, the key is found in an occupied record when searching the internal array using quadratic probing starting from the calculated index. We update the record to mark it DELETED. This deleted record can be reused when inserting a new key-value pair in the hash table. The search operation only terminates at an empty record, so it skips any deleted records.