Improving Cuckoo Hashing with Perfect Hashing
Metadata[+] Show full item record
In computer science, the data structure is a systematic way of organizing data such that it can be used efficiently. There are many hashing techniques that aim at storing keys in memory to increase key access efficiency and to make hashing efficient. One option to increase throughput is to use the algorithms based on hashing. Cuckoo Hashing is one among the techniques which provide high memory usage in constant access time. Cuckoo Hashing, in turn, uses many implementations among which Parallel-d-Pipeline is more efficient. Perfect Hashing maps distinct elements to set of integers without any collision. Perfect Hashing is fast and hit ratio is high. There are many other hashing techniques like Perfect Hashing but the reason we choose perfect hashing as it doesn’t require collision resolution mechanism. Cuckoo Hashing has high memory usage in allocating keys to its memory. So, we are combining Cuckoo Hashing and Perfect Hashing to increase the keys hit ratio and memory utilization.
Table of Contents
Introduction -- Cuckoo hashing and its implementation -- Perfect hashing -- Our approach -- Implementation -- Analysis -- Conclusion