The Cuckoo hashing algorithm allows for lookup of items at constant time, O(1). We would cover the following in this article:
- How Cuckoo Hashing Works
- The Cuckoo Hashing Algorithm
- The Cuckoo Graph
- Cycles in the Cuckoo Graph
- Watch the Video
1. How the Cuckoo Hashing Works
In cuckoo hashing, we maintain two hash position (and hash functions) h1 and h2. So if we need to store a key x, we would compute one of two postions h1(x) and h2(x).
This means that to retrieve an item, we simply need to lookup just two positions in the table. This is shown in Table 1.0.
To insert an Item, we first try to insert the item into position h1(x). If the position is empty, we insert the item. But if it happens that the position if occupied, we throw out the existing key in that location and insert x. (This is the behaviour of the Cuckoo). Assuming the ejected key is y, then y is place in the alternative position which is h2(y). If also this position is occupied by a key z, the y repeats the same treatment: throws out z to make room. This process continues until a given threshold is reached.
In situation like this, if cycles are encountered, then we choose new has functions h1() and h2 and rehash or rebuild the entire table.
2. The Cuckoo Hashing Algorithm
The cuckoo hashing algorithm is given in Listing 1.0. The variable pos is used to maintain the current position where we are currently trying to insert an item.
Listing 1.0: Cuckoo Hashing Algorithm
3. The Cuckoo Graph
A cuckoo graph is formed from the movement of the keys between alternative positions in the hash table. This can be created from Figure 1.0. In the figure, the direction of the arrow on each of the edges indicate that the element can move along the edge to its alternative position
When inserting an item x, the insertion algorithm will only visit positions to which there is a path in the cuckoo graph from either of the two positions h1(x) and h2(x). In the event of a loop, then we go ahead to rehash.
Analysis of the cuckoo graph shows that insertion takes constant time in the absence of a rehashing.
4. Cycles in Cuckoo Graph
Assuming we want to insert a key Z. We would examine the two possible position h1(Z) and h2(Z) which are called buckets. Let’s also assume that h1(Z) hashes to W. Then then:
- W is moved to position of H
- H is moved to position of of H and this becomes a cycle which would require rehashing the table
If however h1(Z) hashes to the position of W and W moves to the position of A. Then a can move to position of B and B moves to an empty slot. In this case, there is not cycles.
5. Demo on the Cuckoo Hashing
Check these Data Structure and Algorithms Tutorials
- Skip Lists and How They Work
- Perfect Hashing – How it Works
- Linear Probing, Quadratic Probing and Double Hashing
- Hashing With Open Addressing
- Universal Hashing
- Search Time Under Simple Uniform Hashing
- Hash Tables – Hashing With Chaining
- Introduction to Hash Tables and Direct Addressing
- Recurrences in Divide and Conquer Algorithm
- How Bloom Filters Work
- How Cuckoo Hashing Works
- Introduction to AVL Trees (With Examples)