Revisiting Cuckoo Hashing: re-addressing the challenges of Cuckoo Hashing

Hashing is essential for efficient searching, with Cuckoo Hashing being a prominent technique since its inception. Based on the size of the hash tables, Cuckoo Hashing is divided into Symmetric Cuckoo Hashing and Asymmetric Cuckoo Hashing: the former utilizes equally sized hash tables, while the latter employs tables of varying sizes. Despite its many advantages, Cuckoo Hashing faces inherent challenges, high insertion latency, inefficient memory usage, and significant data migration costs. Additionally, during bulk searches, switching overhead presents a major challenge. This paper introduces two novel performance metrics: the Degree of Dexterity and the Table Reference Count per key. The Degree of Dexterity combines search time and insertion latency to measure overall efficiency. Meanwhile, the Table Reference Count per key quantifies the impact of table switching on performance, indicating how frequently tables need to be accessed to search for a key.