Binary Probing: A Novel Approach for Efficient Hash Table Operations

Database Management Systems hash the data values into memory using a hash function to generate a key or hash using which data is stored at the appropriate memory location. This is done to ensure faster data retrieval operations from memory. Many times duplicate keys may be generated for different data points leading to a collision. Presently, there are varied algorithms to resolve collisions such as separate chaining, linear probing, quadratic probing, and double hashing. In this paper, we have worked to develop a new collision resolution algorithm titled as Binary Probing. Binary probing was developed with an objective to resolve the inadequacies of existing schemes. Binary probing works to efficiently hash the data values into the hash table using the divide and conquer method in association with binary tree and queue structures. Binary Probing was able to hash data values ranging from one lakh to one crore values in less than 1 s.