Delete operation in double hashing

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 not in the hash table. The implementation is encapsulated in the delete function, which uses double hashing 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 double hashing.

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, double hashing finds the key in an occupied record when searching the internal array. 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.