Stable and low associative left-right hashing

Abstract

Hashing is indispensable for efficient search operations, captivating the interest of numerous researchers. Among the diverse array of techniques, Cuckoo Hashing has emerged as particularly effective across a wide range of applications. Nonetheless, Cuckoo Hashing encounters significant challenges, including high insertion latency, inefficient memory usage, and high data migration costs. The concept of Combinatorial Hashing has inspired this research. Our proposed scheme enhances Combinatorial Hashing and introduces an innovative collision resolution technique called Left-Right Random Probing based on Random Probing. This paper introduces two performance indicators, the degree of dexterity and table reference count per key. This paper identifies and quantifies the switching cost as a new challenge in Cuckoo Hashing. The space complexity and insertion latency of proposed scheme is 1.7 times and 1.5 times better than Cuckoo Hashing respectively. Proposed scheme is 1.35 times faster than Cuckoo Hashing and its time complexity is nearly same as Cuckoo Hashing.