Cuckoo Hashing – Worst case O(1) Lookup!

Background : 

There are three basic operations that must be supported by a hash table (or a dictionary):  

• Lookup(key): return true if key is there on the table, else false
• Insert(key): add the item ‘key’ to the table if not already present
• Delete(key): removes ‘key’ from the table

Collisions are very likely even if we have a big table to store keys. Using the results from the birthday paradox: with only 23 persons, the probability that two people share the same birth date is 50%! There are 3 general strategies towards resolving hash collisions: 

• Closed addressing or Chaining: store colliding elements in an auxiliary data structure like a linked list or a binary search tree.
• Open addressing: allow elements to overflow out of their target bucket and into other spaces.

Although above solutions provide expected lookup cost as O(1), the expected worst-case cost of a lookup in Open Addressing (with linear probing) is ?(log n) and ?(log n / log log n) in simple chaining (Source : Standford Lecture Notes). To close the gap of expected time and worst case expected time, two ideas are used: 

• Multiple-choice hashing: Give each element multiple choices for positions where it can reside in the hash table
• Relocation hashing: Allow elements in the hash table to move after being placed

Cuckoo Hashing : 

Cuckoo hashing applies the idea of multiple-choice and relocation together and guarantees O(1) worst case lookup time! 

• Multiple-choice: We give a key two choices the h1(key) and h2(key) for residing.
• Relocation: It may happen that h1(key) and h2(key) are preoccupied. This is resolved by imitating the Cuckoo bird: it pushes the other eggs or young out of the nest when it hatches. Analogously, inserting a new key into a cuckoo hashing table may push an older key to a different location. This leaves us with the problem of re-placing the older key. 
  • If the alternate position of older key is vacant, there is no problem.
  • Otherwise, the older key displaces another key. This continues until the procedure finds a vacant position, or enters a cycle. In the case of a cycle, new hash functions are chosen and the whole data structure is ‘rehashed’. Multiple rehashes might be necessary before Cuckoo succeeds.

Insertion is expected O(1) (amortized) with high probability, even considering the possibility of rehashing, as long as the number of keys is kept below half of the capacity of the hash table, i.e., the load factor is below 50%.

Deletion is O(1) worst-case as it requires inspection of just two locations in the hash table. 
  
Illustration  

Input: 

{20, 50, 53, 75, 100, 67, 105, 3, 36, 39}

 Hash Functions: 

h1(key) = key%11
h2(key) = (key/11)%11

Let’s start by inserting 20 at its possible position in the first table determined by h1(20):

Next: 50

Next: 53. h1(53) = 9. But 20 is already there at 9. We place 53 in table 1 & 20 in table 2 at h2(20) 

Next: 75. h1(75) = 9. But 53 is already there at 9. We place 75 in table 1 & 53 in table 2 at h2(53) 

Next: 100. h1(100) = 1. 

Next: 67. h1(67) = 1. But 100 is already there at 1. We place 67 in table 1 & 100 in table 2 

Next: 105. h1(105) = 6. But 50 is already there at 6. We place 105 in table 1 & 50 in table 2 at h2(50) = 4. Now 53 has been displaced. h1(53) = 9. 75 displaced: h2(75) = 6.

Next: 3. h1(3) = 3.

Next: 36. h1(36) = 3. h2(3) = 0.

Next: 39. h1(39) = 6. h2(105) = 9. h1(100) = 1. h2(67) = 6. h1(75) = 9. h2(53) = 4. h1(50) = 6. h2(39) = 3.
Here, the new key 39 is displaced later in the recursive calls to place 105, which it displaced.

Implementation: 

Below is the implementation of Cuckoo hashing

Final hash tables:
- 100 - 36 - - 50 - - 75 - 
3 20 - 39 53 - 67 - - 105 - 

105 unpositioned
Cycle present. REHASH.
Final hash tables:
- 67 - 3 - - 39 - - 53 - 
6 20 - 36 50 - 75 - - 100 - 

Time Complexity: O(N), the time complexity of the Cuckoo Hashing algorithm is O(N), where N is the number of keys to be stored in the hash table. This is because the algorithm requires only one pass over the list of keys to place them in the hash table.

Auxiliary Space: O(N), the space complexity of the Cuckoo Hashing algorithm is O(N), where N is the number of keys stored in the hash table. This is because the algorithm requires an auxiliary space of size equal to the hash table, where all the keys are stored.

Generalizations of cuckoo hashing that use more than 2 alternative hash functions can be expected to utilize a larger part of the capacity of the hash table efficiently while sacrificing some lookup and insertion speed. Example: if we use 3 hash functions, it’s safe to load 91% and still be operating within expected bounds.