Code Notes made by Vaibhav Rathod

Cuckoo Hashing

1 min read

Written by Vaibhav Rathod

Explanation

  • Cuckoo Hashing is a hash table algorithm that resolves collisions using two hash functions. If an item collides at one position, it is “kicked out” and reinserted into another position using a second hash function.

Steps

  • Insert an element using the first hash function.
  • If the spot is occupied, evict the existing element and insert it using the second hash function.
  • Repeat until the element is inserted without further eviction.

Time Complexity

  • Time complexity: O(1) average for insertion and look-up.
class CuckooHashing:
    def __init__(self, size):
        self.size = size
        self.table1 = [None] * size
        self.table2 = [None] * size
 
    def hash1(self, key):
        return hash(key) % self.size
 
    def hash2(self, key):
        return (hash(key) * 2) % self.size
 
    def insert(self, key):
        pos1 = self.hash1(key)
        if self.table1[pos1] is None:
            self.table1[pos1] = key
        else:
            evicted = self.table1[pos1]
            self.table1[pos1] = key
            self.insert_in_table2(evicted)
 
    def insert_in_table2(self, key):
        pos2 = self.hash2(key)
        if self.table2[pos2] is None:
            self.table2[pos2] = key
        else:
            evicted = self.table2[pos2]
            self.table2[pos2] = key
            self.insert(evicted)
 
# Example usage
cuckoo = CuckooHashing(10)
cuckoo.insert("hello")
cuckoo.insert("world")

Graph View

Backlinks

Recently Updated