Hash Table Chaining

Hash table chaining is a technique used to handle collisions in a hash table. When a hash function maps two or more keys to the same index in the array, a collision occurs. In chaining, each index in the array contains a linked list of nodes, where each node contains a key-value pair. When a new element is inserted into the hash table and a collision occurs, the new node is appended to the linked list at the corresponding index.

Sure! Hash table chaining is a technique used to handle collisions in a hash table. When two keys hash to the same index, they are placed into a linked list at that index.

Here's a basic example of a hash table with chaining in C++. This example demonstrates a very simple hash function, and the chaining is implemented using the Standard Library's linked list (std::list).

//  main.cpp
//  HashTableChaining
//  Created by Kevin Roark on 8/8/23.

#include <iostream>
#include <list>
#include <vector>

using namespace std;

class HashTable {
private:
    int capacity; // Size of the hash table
    vector<list<int>> table; // The hash table itself, implemented as a vector of lists

    int hash(int key) {
        return key % capacity; // Simple hash function that returns the remainder of key divided by the capacity
    }

public:
    HashTable(int capacity) : capacity(capacity) {
        table.resize(capacity);
    }

    void insert(int key) {
        int index = hash(key);
        table[index].push_back(key); // Append the key to the list at the hashed index
    }

    void remove(int key) {
        int index = hash(key);
        table[index].remove(key); // Remove the key from the list at the hashed index
    }

    bool find(int key) {
        int index = hash(key);
        for (const int& element : table[index]) {
            if (element == key) {
                return true; // If the key is found in the list at the hashed index, return true
            }
        }
        return false; // If the key is not found, return false
    }

    void print() {
        for (int i = 0; i < capacity; i++) {
            cout << "[" << i << "]: ";
            for (const int& key : table[i]) {
                cout << key << " -> ";
            }
            cout << "NULL\n";
        }
    }
};

int main() {
    HashTable hashTable(10);

    hashTable.insert(15);
    hashTable.insert(25);
    hashTable.insert(35);

    hashTable.print();

    if (hashTable.find(25)) {
        cout << "Key 25 found\n";
    } else {
        cout << "Key 25 not found\n";
    }

    hashTable.remove(25);

    hashTable.print();

    if (hashTable.find(25)) {
        cout << "Key 25 found\n";
    } else {
        cout << "Key 25 not found\n";
    }
    return 0;
}

This will create a hash table with a capacity of 10, and all the keys are linked using a std::list at their hashed index. It inserts three keys and then demonstrates finding and removing one of them.

Note: This is a simple and naive implementation for demonstration purposes. In practice, you would probably want to implement more robust hashing and handle other edge cases.

In the provided example, collisions are handled using the chaining technique, which is implemented with list. Let's break it down step by step.

Initial Setup:
The hash table is an array (or std::vector in this case) of fixed size (capacity). Each slot in the array is a linked list (std::list).
vector<list<int>> table;
Hash Function:
We have a simple hash function that takes an integer key and produces an index in the hash table.
int hash(int key) { return key % capacity; }
Insertion:
To insert a new key:
- The key is hashed to determine its position in the array.
- If the slot (index) in the array is empty (no collision), a new key is added to the linked list at that slot.
- If the slot is not empty (collision), the key is simply appended to the existing linked list at that slot.
Notice that even if two or more keys hash to the same index (collision), they can all co-exist in the linked list at that index.
Searching:
To search for a key:
- Hash the key to find its potential position.
- Traverse the linked list at that position to see if the key exists.
Deletion:
To delete a key:
- Hash the key to find its position.
- Remove the key from the linked list at that position.

When a collision happens, the chaining technique uses a linked list to store all the keys that collide at the same slot. This approach ensures that no keys are rejected due to collisions, but it may result in longer search times if one slot accumulates too many keys.