Search operation in double hashing

The search operation is one of the primary operations on a hash table and is used to retrieve the value of a key as stored in the hash table. The implementation is encapsulated in the search function and relies on the double hashing collision resolution scheme to look for a value in the internal array. Let us look at the algorithm and implementation of the search operation in a hash table implemented using double hashing.

Algorithm

The search operation is quite simple. We only need to calculate the index (hash code) for the given key and then search for the key at the index. However, the hash table could have a collision for the given key, so we use the double hashing scheme to search for it.

Once we calculate the index (hash code) for the given key, we search the array starting from that index in increments of the step size calculated by the second hash function until we either find an occupied record with the given key, hit an empty record, or finish the probe sequence. Let us look at the different cases separately to understand how the search operation is implemented in a hash table that uses a double hashing scheme for collision resolution.

1. The key is present in the table