Cuckoo Hashing

Data structure is one of Computer Science’s most important concepts. There are a lot of methods that can be used for quick search or sorting. One of them is hashing, which converts a given key to another value. To generate a new value according to a mathematical algorithm, a hash function is used. It is known as a hash value or simply, a hash.

Hash function will convert any key to its location based on the function definition for eg if we define a function like
f(n) = n%total_location where total_location = 10
so to arrange all below number
53,6,75,10,58,97,26,32,93,23,84 , we need an array or 10 size

Table to store records based on Hash function

so, in short, the last digit of each number will tell us the location/index where the number will be stored

The numbers are stored based on their key value

But. we can find out that the number 26 position is already filled earlier by 6. this one is called the collision. There are numerous methods by which the collision is solved and one of them is Cuckoo Hashing.

So now we will discuss the operation of Cuckoo hashing by which collision will be effectively handled.

In order to find the location of any record based on its key value, Cuckoo Hashing uses two separate hash functions.

Same key pass to both function which generates two location

Cuckoo Hashing takes two memory storage for two hash functions to deal with the collision in such a way that if the first hash function collides, others will figure out the second storage location. let define two hash function to understand the working the total storage location is 10

1. hf1(n) = n%total_location
2. hf2(n) = (n/total_location) % total_location

For example, in the past, when we try to insert 26, there is a collision, the 6 will jump out and store in the second table where 26 will be stored in the first table. so 6 will be stored in at the 0th position on table 2

so, all numbers will get their position in either of any one location

so the algorithm is simple to apply cuckoo hashing

1. Begin by inserting element x into table 1 to insert element x
2. If hf₁(x) is empty, place x there.
3. Place x there otherwise, evict the old y part, and attempt to place y in table 2.
4. Repeat this process until all elements stabilize, bouncing between tables.
5. If run in a cycle, the insertions run into trouble.If this occurs, perform a rehash by selecting a new hf1 and hf2 and adding all back into the table's components. before this succeeds, multiple rehashes may be required.

Analysis of Cuckoo hashing

1. to insert any element it takes only O(1) because to check only two table based on hash function
2. to delete it also takes only O(1) time to remove element
3. to search takes O(1) time to check two tables

on its key value, Cuckoo Hashing uses two separate hash functions.