Collision Resolution: Separate Chaining

Because a hash function maps a potentially infinite set of keys into a finite array, collisions are inevitable. A collision occurs when the hash function generates the same index for more than one key. One of the most common methods for handling these collisions is known as separate chaining.

How Chaining Works

In separate chaining, each index of the hash table array does not store a single element. Instead, it stores a pointer to a linked list (or another secondary data structure) containing all the key-value pairs that hash to that specific index.

When searching for a value, the algorithm first computes the hash of the key to find the correct bucket. Then, it performs a linear search through the linked list at that bucket to find the matching key. Assuming a good hash function that distributes keys evenly, the length of these chains remains small, maintaining an average time complexity of O(1) for search, insert, and delete operations.

Implementation Example

Below is a simplified C++ structure representing a hash table node and the basic skeleton of an insertion function using chaining.

// Node structure for the linked list
struct HashNode {
    int key;
    int value;
    HashNode* next;
};

class HashTable {
private:
    HashNode** table;
    int capacity;

public:
    void insert(int key, int value) {
        int hashIndex = key % capacity;
        HashNode* newNode = new HashNode{key, value, nullptr};
        
        // Insert at the head of the list for O(1) time
        if (table[hashIndex] == nullptr) {
            table[hashIndex] = newNode;
        } else {
            newNode->next = table[hashIndex];
            table[hashIndex] = newNode;
        }
    }
};

While chaining is easy to implement, it can lead to poor cache performance due to the scattered memory allocation of linked list nodes. In the next section, we will explore an alternative method called Open Addressing.