Performance analysis of sequential Cuckoo Hashing under light of switching cost [Articol]

Abstract

Cuckoo Hashing has been considered the state of the art since its origin. In Cuckoo Hashing, the search operation is executed sequentially in the tables, and thus, Cuckoo Hashing is Sequential Cuckoo Hashing. Based on the size of the table, Cuckoo Hashing is implemented in two ways: Symmetric Sequential Cuckoo Hashing and Asymmetric Sequential Cuckoo Hashing. Cuckoo Hashing suffers from higher insertion latency, inefficient memory usage, and high data migration. This work investigates the performance of both versions of Cuckoo Hashing under the light of two newly proposed performance indicators: Degree of Dexterity and Table Reference Count per key.