Cuckoo Hashing

Also part of Open addressing, but one alternate slot.

We have two independent hash functions $h_0,h_1$ and two tables $T_0,T_1$ .

Main idea: An item with key $k$ can ONLY be at $T_0[h_0(k)]$ or $T_1[h_1(k)]$.

• search and delete $\to$ constant time $O(n)$
• insert [always] initially puts a new item into $T_0[h_0(k)]$. If $T_0[h_0(k)]$ is occupied: “kick-out” the other item, which we then attempt to re-insert into its alternate position $T_1[h_1(k)]$. This may lead to a loop of “kicking-out”. We detect this by aborting after too many attempts. In case of failure: rehash with a larger $M$ and a new hash functions.

Insert may be slow, but is expected to be constant time $O(1)$ if the load factor $\alpha$ is small enough.

Insertion What is $n$? The total number of items in both tables.

Example: (in notes)

• We have two hash functions and two hash tables
• If we want to insert, we calculate two values, always insert with the first calculated value in the first table. If the place in the first table we want to insert in is occupied, we kick it out, the kicked out item will go to the value calculated in the second table. If we kick out the item from the first table and its second tables place is taken, we kick out the element in the second table and calculate its first hash function value to put it back into somewhere in the first table, so on and so forth.
• To delete, we check both tables???

What is $n$? The number of elements?

Time Complexity of Cuckoo Hashing

• Insertion: $O(1)$, if the load factor $\alpha$ is small enough.
• Deletion: worst-case is $O(1)$, only requires inspection at two locations in hash tables $\to$ in cuckoo hashing, search and delete have guaranteed $O(1)$ run-time.

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)$