SeparateChaining.cpp

#include <iostream>

using namespace std;

const int TABLE_SIZE = 5;

class LinkedHash
{
public:
    int key, val;
    LinkedHash *next;
    LinkedHash(int key, int val)
    {
        this->key = key;
        this->val = val;
        this->next = NULL;
    }
};

class HashMap
{
private:
    LinkedHash **htable;
public:
    HashMap()
    {
        htable = new LinkedHash * [TABLE_SIZE];
        for ( int i = 0 ; i < TABLE_SIZE ; i ++ )
        {
            htable[i] = NULL;
        }
    }
    ~HashMap()
    {
        for ( int i = 0 ; i < TABLE_SIZE ; i ++ )
        {
            if ( htable[i] != NULL )
            {
                LinkedHash *prev = NULL;
                LinkedHash *entry = htable[i];
                while ( entry != NULL )
                {
                    prev = entry;
                    entry = entry->next;
                    delete prev;
                }
            }
            delete []htable;
        }
    }
    int HashFunc(int key)
    {
        return key % TABLE_SIZE;
    }
    void insert(int key, int val)
    {
        int hash_val = HashFunc(key);
        if ( htable[hash_val] == NULL )
        {
            htable[hash_val] = new LinkedHash(key, val);
        }
        else
        {
            LinkedHash *entry = htable[hash_val];
            while ( entry->next != NULL )
            {
                entry = entry->next;
            }
            if ( entry->key == key ){
                entry->val = val;
            }
            else{
                entry->next = new LinkedHash(key, val);
            }
        }
    }
    int Search(int key)
    {
        int hash_val = HashFunc(key);
        if (htable[hash_val] == NULL)
            return -1;
        else
        {
            LinkedHash *entry = htable[hash_val];
            while (entry != NULL && entry->key != key)
                entry = entry->next;
            if (entry == NULL){
                return -1;
            }
            else{
                return entry->val;
            }
        }
    }
    void Remove(int key)
    {
        int hash_val = HashFunc(key);
        if (htable[hash_val] != NULL)
        {
            LinkedHash *entry = htable[hash_val];
            LinkedHash *prev = NULL;
            while (entry->next != NULL && entry->key != key)
            {
                prev = entry;
                entry = entry->next;
            }
            if (entry->key == key)
            {
                if (prev == NULL)
                {
                    LinkedHash *next = entry->next;
                    delete entry;
                    htable[hash_val] = next;
                }
                else
                {
                    LinkedHash *next = entry->next;
                    delete entry;
                    prev->next = next;
                }
            }
        }
    }
};