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. It is implemented in two primary forms: Parallel Cuckoo Hashing and Sequential Cuckoo Hashing. 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. This advanced variant of random probing strategically utilizes prime numbers and Fibonacci sequences to improve performance. This paper introduces two performance indicators, the degree of dexterity and table reference count per key. This paper identifies switching cost as a new challenge in Cuckoo Hashing and quantifies this switching cost using the parameter, table reference count per key.