# 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>
