# ST - Seperate Chaining

```cpp
#include <iostream>
#include <bitset>
#include <functional> // for hash<class template> class

using namespace std;

const int M = 97; // no of chains

template <typename Key, typename Value>
struct Node
{
     Key key;
     Value val;
     Node<Key, Value> *next;
     Node() : next(nullptr) {}
     Node(Key key, Value val, Node<Key, Value> *next) : key(key), val(val), next(next){};
};

template <typename Key, typename Value>
class SeparateChainingHashST
{
     Node<Key, Value> *st[M]; // array of chain
     int Hash(Key);

public:
      SeparateChainingHashST();
     ~SeparateChainingHashST();
     bool contain(Key);
     void put(Key, Value);
     Value get(Key);
     bool remove(Key);
     void display();
};

template <typename Key, typename Value>
SeparateChainingHashST<Key, Value>::SeparateChainingHashST() {
    for (int i = 0; i < M; i++) {
        st[i] = nullptr;
    }
}

template <typename Key, typename Value>
SeparateChainingHashST<Key, Value>::~SeparateChainingHashST() {
    for (int i = 0; i < M; i++) {
        Node<Key, Value>* current = st[i];
        while (current != nullptr) {
            Node<Key, Value>* toDelete = current;
            current = current->next;
            delete toDelete;
        }
    }
}

template <typename Key, typename Value>
int SeparateChainingHashST<Key, Value>::Hash(Key key)
{
     hash<Key> hashCode;                      // An int between -2^31 and 2^31 - 1.
     return (hashCode(key) & 0x7fffffff) % M; // 0x7fffffff = 2147483647. 
}

template <typename Key, typename Value>
bool SeparateChainingHashST<Key, Value>::contain(Key key)
{
     int i = Hash(key);
     for (Node<Key, Value> *x = st[i]; x != nullptr; x = x->next)
     {
          if (x->key == key)
               return true;
     }
     return false;
}

template <typename Key, typename Value>
Value SeparateChainingHashST<Key, Value>::get(Key key)
{
     int i = Hash(key);
     for (Node<Key, Value> *x = st[i]; x != nullptr; x = x->next)
     {
          if (x->key == key)
               return x->val;
     }
     throw runtime_error("\n Key not present.");
}

template <typename Key, typename Value>
void SeparateChainingHashST<Key, Value>::put(Key key, Value val)
{
     int i = Hash(key);
     for (Node<Key, Value> *x = st[i]; x != nullptr; x = x->next)
     {
          if (x->key == key)
          {
               x->val = val;
               return;
          }
     }
     st[i] = new Node<Key, Value>(key, val, st[i]);
}

template <typename Key, typename Value>
bool SeparateChainingHashST<Key, Value>::remove(Key key)
{
     if (!contain(key))
          return false;

     int i = Hash(key);

     if (st[i]->key == key)
     {
          st[i] = st[i]->next;
          return true;
     }

     Node<Key, Value> *temp = st[i];
     Node<Key, Value> *x = st[i]->next;

     while (x->next != nullptr)
     {
          if (x->key == key)
          {
               temp->next = x->next;
               return true;
          }
          temp = x;
          x = x->next;
     }
     if (x->next == nullptr)
          temp->next = nullptr;
     return true;
}

template <typename Key, typename Value>
void SeparateChainingHashST<Key, Value>::display()
{
     for (int i = 0; i < M; i++)
     {
          if (st[i] != nullptr)
               cout << "\n table[" << i << "] -> ";
          for (Node<Key, Value> *x = st[i]; x != nullptr; x = x->next)
               cout << x->key << ": " << x->val << ", ";
     }
}
int main()
{
     SeparateChainingHashST<string, int> *st = new SeparateChainingHashST<string, int>();
     st->put("Nafees", 5);
     st->put("Zaid", 10);
     st->put("Tauseef", 9);
     st->put("Ali", 2);
     st->put("Awais", 3);
     st->put("Muhammad", 1);

     if (st->remove("Zaid"))
          cout << " Pair Deleted.";
     else
          cout << " Key Not Found!";

     st->display();

     try
     {
          cout << "\n Value associated with 'Zaid': " << st->get("Zaid") << endl;
     }
     catch (const runtime_error &e)
     {
          cout << e.what() << endl;
     }
     delete st;
}
```

<details>

<summary><a href="https://leetcode.com/problems/design-hashmap/">Design HashMap</a></summary>

```cpp
const int N = 97;

class Node{
    public:
    int key, val;
    Node* next;

    Node() : next(nullptr){};
    Node(int key, int val, Node* next): key(key), val(val), next(next){};
};

class MyHashMap {
    Node *mp[N];
public:
    MyHashMap() {
        for(int i = 0; i<N; ++i){
            mp[i] = nullptr;
        }
    }
    
    int hashFunc(int key) {
        hash<int> hashCode;
        return (hashCode(key) & 0x7fffffff) % N;
    }

    void put(int key, int val) {
        int i = hashFunc(key);
        for(Node* x = mp[i]; x != nullptr; x = x->next){
            if(x->key == key) {
                x->val = val;
                return;
            }
        }
        mp[i] = new Node(key, val, mp[i]);
    }
    
    int get(int key) {
        int i = hashFunc(key);

        for(Node* x = mp[i]; x != nullptr; x = x->next){
            if(x->key == key) {
                return x->val;
            }
        }
        return -1;
    }
    
    bool contain(int key){ 
        int i = hashFunc(key);

        for(Node* x = mp[i]; x != nullptr; x = x->next){
            if(x->key == key) {
                return true;
            }
        }
        return false;
    }

    void remove(int key) {
    if(!contain(key)) return ;
    
    int i = hashFunc(key);

    if (mp[i]->key == key)
    {
        mp[i] = mp[i]->next;
        return ;
    }

    Node *temp = mp[i];
    Node *x = mp[i]->next;

    while (x->next != nullptr)
    {
        if (x->key == key)
        {
            temp->next = x->next;
            return;
        }
        temp = x;
        x = x->next;
    }
    if (x->next == nullptr)
        temp->next = nullptr;
    }
};

/**
 * Your MyHashMap object will be instantiated and called as such:
 * MyHashMap* obj = new MyHashMap();
 * obj->put(key,value);
 * int param_2 = obj->get(key);
 * obj->remove(key);
 */
```

</details>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/hash-table/whats-hash-table-and-implementation/st-seperate-chaining.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.