Open Addressing and Chaining

Open Addressing and Chaining are two popular techniques for handling collisions in hash tables. Collisions occur when two or more keys produce the same hash value, leading them to the same location in the hash table.

Here’s a detailed look at each method:

Open Addressing

Open Addressing resolves collisions by finding another open slot within the hash table itself. When a collision happens, the algorithm searches for an empty slot (or address) according to a specific probing method. This means that each element stays within the table array, without using additional data structures like linked lists.

Types of Probing Techniques in Open Addressing

1. Linear Probing:

   • When a collision occurs, it moves to the next slot in the array (index + 1) until it finds an empty slot.
   • If the end of the table is reached, it wraps around to the beginning.
   • Drawback: Linear probing can cause primary clustering, where clusters of occupied slots form, leading to slower search times.

   Example: index = (hash + i) % tableSize

2. Quadratic Probing:

   • Instead of moving linearly, it moves in quadratic steps to find an open slot. For example, it checks the slots at (hash + 1^2), (hash + 2^2), etc.
   • This reduces primary clustering but can lead to secondary clustering, where keys with the same hash value probe the same sequence of positions.

   Example: index = (hash + i^2) % tableSize

3. Double Hashing:

   • Double hashing uses a second hash function to determine the step size for probing, which minimizes clustering.
   • This is one of the most effective probing techniques for avoiding collisions.

   Example: index = (hash1(key) + i * hash2(key)) % tableSize

C++ Example of Open Addressing (Linear Probing)

#include <iostream>
#include <vector>
using namespace std;

class HashTable {
    vector<int> table;
    int tableSize;

public:
    HashTable(int size) : table(size, -1), tableSize(size) {}  // Initialize table with -1

    int hashFunction(int key) {
        return key % tableSize;
    }

    void insert(int key) {
        int index = hashFunction(key);
        int i = 0;

        // Linear probing
        while (table[(index + i) % tableSize] != -1) {
            i++;
        }

        table[(index + i) % tableSize] = key;
        cout << "Inserted " << key << " at index " << (index + i) % tableSize << endl;
    }

    void display() {
        for (int i = 0; i < tableSize; i++) {
            cout << i << ": " << table[i] << endl;
        }
    }
};

int main() {
    HashTable ht(7);
    ht.insert(10);
    ht.insert(20);
    ht.insert(15);
    ht.insert(7);
    ht.display();
    return 0;
}

Advantages and Disadvantages of Open Addressing

• Advantages:
  • No extra memory is needed outside the hash table.
  • Useful in memory-constrained environments.
• Disadvantages:
  • Primary and secondary clustering issues can degrade performance.
  • Table can fill up faster, requiring rehashing to increase capacity.

Chaining

Chaining resolves collisions by storing all elements that hash to the same index in a linked list (or any other data structure like a dynamic array) at that index. When a collision occurs, the new element is added to the linked list at the hashed index, allowing multiple elements to exist at the same index.

How Chaining Works

1. Insert: Calculate the index using the hash function. If there’s already an element at this index, append the new element to the linked list at that index.
2. Search: Calculate the index and search through the linked list at that index to find the desired key.
3. Delete: Calculate the index and delete the element from the linked list at that index if it exists.

C++ Example of Hashing with Chaining

#include <iostream>
#include <list>
#include <vector>
using namespace std;

class HashTable {
    vector<list<int>> table;  // Each index stores a linked list
    int tableSize;

public:
    HashTable(int size) : table(size), tableSize(size) {}

    int hashFunction(int key) {
        return key % tableSize;
    }

    void insert(int key) {
        int index = hashFunction(key);
        table[index].push_back(key);
        cout << "Inserted " << key << " at index " << index << endl;
    }

    void display() {
        for (int i = 0; i < tableSize; i++) {
            cout << i << ": ";
            for (int key : table[i]) {
                cout << key << " -> ";
            }
            cout << "nullptr" << endl;
        }
    }
};

int main() {
    HashTable ht(7);
    ht.insert(10);
    ht.insert(20);
    ht.insert(15);
    ht.insert(7);
    ht.display();
    return 0;
}

Advantages and Disadvantages of Chaining

• Advantages:
  • Avoids clustering issues.
  • Allows a dynamic number of elements (linked lists can grow as needed).
• Disadvantages:
  • Requires additional memory for linked list pointers.
  • Performance may degrade if too many elements are stored in a single linked list, leading to $O(n)$ search time in the worst case.

Comparison of Open Addressing and Chaining

When to Use Each

• Open Addressing is suitable when memory is limited, and the load factor (number of elements compared to the table size) is kept below 0.7.
• Chaining is more flexible, especially when frequent insertions are expected, and load factor could be higher than 1 (number of elements exceeds table size).

In summary:

• Use open addressing when memory is constrained and the table load is low.
• Use chaining for dynamic storage and to avoid clustering issues, especially in environments where extra memory for linked lists is available.