Cuckoo hashing

Cuckoo hashing (English cuckoo hashing ) is an algorithm that computes by means of two hash functions to index into a table, on which the item is to be inserted. It was developed in 2001 by Rasmus Pagh and Flemming Friche sledders. He has discharged from the cuckoo, whose foreign chick eggs from the nest His name.

Operation

Each of the two hash functions calculate the index of a member to be inserted in each case on a table. First it is checked if the inserted element with the hash function can be inserted into the table at the location. If this is the case, then insert the item there. If the space is already occupied, however, then the place is with the second hash function is calculated in the second table and inserted if it is free, there. However, if the court also shows the element to be inserted is inserted into the first table and moved the item that may have been there in the second table. Now, if there again a collision occurs, the element is then moved back into the first table. Is the space in the first table free insertion is completed. If, however, here again take a place one item, it is moved back into the second table. This process is repeated until a free location is found. It may happen that the same table constellation occurs as at the beginning, so then the process gets into a cycle ( loop ). In this case, the table is rebuilt with new hash functions.

Example

The following hash functions are met:

Cycle

If you now wish to insert the element 6, then you get into a cycle. In the last row of the table we find the same initial situation as at the beginning again.