Advanced Hashing Techniques Unveiled: Cuckoo Hashing [Series 1]

Hashing, a fundamental data structure, underpins countless software applications for its speed, efficiency, and versatility. Despite its perceived simplicity, aspiring programmers should explore the intricacies of hashing techniques. This knowledge is ubiquitous and essential for safeguarding sensitive data, fine-tuning search algorithms, or upholding data integrity, hashing plays a pivotal role in software development.

While many hashing techniques are available, I set my sights on unraveling three advanced techniques through captivating articles. There, I'll untangle the core concepts, drape them with sample code snippets, and explain some real-world applications. Brace yourself for the unveiling of Cuckoo Hashing — the opening act of our hashing saga. And if curiosity beckons, stay tuned for the forthcoming chapters.

If you find it insightful and appreciate my writing, consider following me for updates on future content. I'm committed to sharing my knowledge and contributing to the coding community. Join me in spreading the word and helping others to learn.

Introduction

Cuckoo Hashing is a hash table collision resolution technique that ensures constant-time lookup by using two hash functions. It employs multiple-choice hash tables and guarantees that each key is stored in one of the tables.

Now you might be wondering what is multiple-choice hash tables. Consider it like finding the right box for your toy. If one box is full, you try another until you find an empty one. It's the same with storing data in different boxes until you find a place without any stuff in it. That's multiple-choice hashing!

When a collision occurs, the existing item is relocated to its alternate position in the other table. This process continues recursively until all keys find a place or a predefined threshold is reached, indicating a table expansion.

Cuckoo Hashing offers efficient retrieval and insertion operations with O(1) time complexity, with worst-case constant-time complexity, making it suitable for applications requiring fast key-value lookups while minimizing memory overhead.

How Does it work

I'll try articulating of how Cuckoo Hashing works for adding (inserting) and searching for an item.

Adding (Inserting) an Item:

1. Calculate Hash Values: When adding a new item, calculate two hash values using two different hash functions. These hash values determine the potential positions where the item can be stored in the hash tables.
2. Check Availability: Check if the calculated positions in both hash tables are empty. If both positions are empty, insert the item into one of the positions and mark it as occupied.
3. Collision Handling: If one or both positions are occupied, a collision occurs. In Cuckoo Hashing, it triggers a relocation process.
4. Relocation: Move the existing item(s) from the occupied position(s) to their alternate positions in the other hash table. Then, insert the new item into the vacated position. If this insertion causes another collision, repeat the relocation process recursively until all items find a place or a predefined threshold is reached.
5. Threshold Check: If the relocation process exceeds a predefined threshold (e.g., the maximum number of relocations allowed), resize the hash tables and rehash the items to accommodate the new size.

Searching for an Item:

1. Calculate Hash Values: When searching for an item, calculate its hash values using the same hash functions used for insertion.
2. Check Positions: Check the calculated positions in both hash tables for the item. If the item is found at either position, return it as the search result.
3. Handling Absence: If the item is not found at either position, it means the item is not present in the hash tables.
4. End of Search: End the search operation with the result (found or not found).

I found this funny flow chart that lucidly explains this technique. If you want to know more, read through this document: https://www.brics.dk/RS/01/32/BRICS-RS-01-32.pdf

Pros and Cons

There are several advantages and disadvantages of this approach. Some primary advantages are as follows:

1. Constant-Time Lookup: It ensures constant-time lookup, making it efficient for retrieval operations. It is attributed to the higher performance as well.
2. Minimal Space Overhead: It minimizes memory usage by storing only keys, avoiding additional data structures like linked lists or buckets.
3. Deterministic Behavior: The placement of keys is deterministic, ensuring predictable performance characteristics.

There are some challenges with this technique as well:

1. Limited Key Density: Cuckoo Hashing requires a low key density to avoid excessive relocations, limiting its effectiveness in highly dense datasets.
2. Sensitivity to Hash Functions: The performance of Cuckoo Hashing is sensitive to the quality and independence of hash functions used, requiring careful selection and design.

Real-time Use Cases

Cuckoo Hashing is utilized in various real-time use cases across several domains due to its efficient lookup and insertion operations. Some common real-time use cases of Cuckoo Hashing include:

1. Network Routing Tables: Cuckoo Hashing is crucial for storing routing information in network routers and switches, enabling fast lookup and efficient packet forwarding.
2. In-Memory Databases: Cuckoo Hashing is widely used in in-memory databases for indexing and querying data, providing rapid access to stored information.
3. Cache Management: Cuckoo Hashing is employed in cache management systems to store frequently accessed data for quick retrieval, enhancing application performance.
4. Content Delivery Networks (CDNs): CDNs utilize Cuckoo Hashing in cache management layers to store cached content and swiftly serve requests to users, improving content delivery speed.
5. Distributed Systems: Cuckoo Hashing is applied in distributed systems for data partitioning and sharding, ensuring the even distribution of data across multiple nodes and facilitating efficient data access and load balancing.

Code Snippet

Enough of theories; let's dive into some practical code snippets. I've written the following code with inline comments to ensure a clear understanding of its purpose.

class CuckooHashing {
    /**
     * Constructor for the CuckooHashing class.
     */
    constructor(size) {
        this.size = size; // The size of the hash tables

        // Initialize two hash tables with null values
        this.table1 = new Array(size).fill(null);
        this.table2 = new Array(size).fill(null);
    }

    /**
     * Inserts a key-value pair into the hash tables.
     */
    insert(key, value) {
        const hash1 = this.hashFunction1(key);
        const hash2 = this.hashFunction2(key);
        
        if (this.table1[hash1] === null) {
            // Check if the slot in table1 is empty, if so, insert the item
            this.table1[hash1] = { key, value };
        } else if (this.table2[hash2] === null) {
            // If slot in table1 is occupied, check table2 and insert if slot is empty
            this.table2[hash2] = { key, value };
        } else {
            // If both slots are occupied, perform eviction and recursive insertion
            const { key: evictedKey, value: evictedValue } = this.table1[hash1];

            this.table1[hash1] = { key, value };
            this.insert(evictedKey, evictedValue); // Recursive call to handle evicted item
        }
    }

    /**
     * Searches for a key in the hash tables and returns the corresponding value if found.     
     */
    search(key) {
        const hash1 = this.hashFunction1(key);
        const hash2 = this.hashFunction2(key);

        if (this.table1[hash1] !== null && this.table1[hash1].key === key) {
            // Check if key is found in table1
            return this.table1[hash1].value;
        } else if (this.table2[hash2] !== null && this.table2[hash2].key === key) {
            // Check if key is found in table2
            return this.table2[hash2].value;
        } else {
            // Key not found
            return null;
        }
    }

    /**
     * First hash function for calculating the index in table1.
     */
    hashFunction1(key) {
        return hash(key) % this.size;
    }

    /**
     * Second hash function for calculating the index in table2.
     */
    hashFunction2(key) {
        return Math.floor(hash(key) / this.size) % this.size;
    }
}
        

This snippet is well-documented. However, if you need further clarification or assistance in understanding any part of it, please feel free to leave a comment. I'll be happy to provide additional explanations as needed.