C++ program to implement Hash Table using Template Class

By | 08.01.2017

Hash Table using Template Class


Write a C++ program to implement Hash Table using Template Class. Here’s a Simple C++ program to implement Hash Table using Template Class in C++ Programming Language.


What are Templates in C++ ?


Templates are the foundation of generic programming, which involves writing code in a way that is independent of any particular type.

A template is a blueprint or formula for creating a generic class or a function. The library containers like iterators and algorithms are examples of generic programming and have been developed using template concept.

There is a single definition of each container, such as vector, but we can define many different kinds of vectors for example, vector <int> or vector <string>..


Function Template :

The general form of a template function definition is shown here:

template <class type> ret-type func-name(parameter list)

{
// body of function
}


Class Template :

Just as we can define function templates, we can also define class templates. The general form of a generic class declaration is shown here:

template <class type> class class-name

{
.
.
.
}


Below is the source code for C++ program to implement Hash Table using Template Class which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C++ program to implement Hash Table using Template Class  */

#include <iostream>
#include <stdlib.h>

using namespace std;

template<class E, class K>
class HashTable {
        public:
                HashTable(int divisor = 11);
                ~HashTable() {delete [] ht;
                        delete [] empty;}
                        int Search(const K& k, E& e) const;
                        HashTable<E,K>& Insert(const E& e);
                        void Output();// output the hash table
                        void del(E e);
        private:
                        int hSearch(const K& k) const;
                        int D; // hash function divisor
                        E *ht; // hash table array
                        int *empty; // 1D array
};
        template<class E, class K>
HashTable<E,K>::HashTable(int divisor)
{// Constructor.
        D = divisor;
        ht = new E [D];
        empty = new int [D];

        for (int i = 0; i < D; i++)
                empty[i] = 1;
}
template<class E, class K>
int HashTable<E,K>::hSearch(const K& k) const
{
        int i = k % D;
        int j = i;
        do {
                if (empty[j] || ht[j] == k) return j;
                j = (j + 1) % D;  // next bucket
        } while (j != i); // returned to home?
        return j;  // table full
}
        template<class E, class K>
void HashTable<E,K>::del(E e)
{
        int b=hSearch(e);
        if( !empty[b] && ht[b]==e)
        {
                ht[b]=0;
                empty[b]=1;
        }
        else
                cout<<"\nelement not found";

}
template<class E, class K>
int HashTable<E,K>::Search(const K& k, E& e) const
{
        int b = hSearch(k);
        if (empty[b] || ht[b] != k) return 0;
        e = ht[b];
        return 1;
}
        template<class E, class K>
HashTable<E,K>& HashTable<E,K>::Insert(const E& e)
{// Hash table insert.
        K k = e; // extract key
        int b = hSearch(k);
        if (empty[b]) {empty[b] = 0;
                ht[b] = e;
                return *this;

        }
        if (ht[b] == k) { cout<<"\nbad input"; return *this; } // duplicate
        cout<<"\nNo memory";// table full
        return *this;
}

        template<class E, class K>
void HashTable<E,K>::Output()
{
        cout<<endl;
        for (int i = 0; i< D; i++) {
                if (empty[i]) cout << "0 ";
                else cout << ht[i]<<" ";}
        cout<<endl;
}
class element {
        public:
        operator long() const {return key;}
        private:
        int data;
        long key;
};

int main()
{
        HashTable<int , int > h(11);
        int e;
        e = 80;
        h.Insert(e);
        e = 40;
        h.Insert(e);
        e = 65;
        h.Insert(e);
        cout<<"\nAfter inserting 80,40,65:";
        h.Output();
        cout<<endl;
        h.del(40);
        cout<<"\nAfter deleting 40:";
        h.Output();
        cout<<endl;
        e = 58;
        h.Insert(e);
        e = 24;
        h.Insert(e);
        cout<<"\nafter appending 58, 24:";
        h.Output();
        cout<<"\nTrying to delete element 25:";
        h.del(25);
        h.Output();
        e = 2;
        h.Insert(e);
        e = 13;
        h.Insert(e);
        e = 46;
        h.Insert(e);
        e = 16;
        h.Insert(e);
        e = 7;
        h.Insert(e);
        e = 21;
        h.Insert(e);
        h.Insert(10);
        cout <<"After inserting more values:" << endl;
        h.Output();
        e = 99;
        cout<<"\ntrying to insert 99:";
        h.Insert(e);
        h.Output();
        return 0;
}

OUTPUT : :


/* C++ program to implement Hash Table using Template Class  */

After inserting 80,40,65:
0 0 0 80 0 0 0 40 0 0 65


After deleting 40:
0 0 0 80 0 0 0 0 0 0 65


after appending 58, 24:
0 0 24 80 58 0 0 0 0 0 65

Trying to delete element 25:
element not found
0 0 24 80 58 0 0 0 0 0 65
After inserting more values:

21 10 24 80 58 2 13 46 16 7 65

trying to insert 99:
No memory
21 10 24 80 58 2 13 46 16 7 65

Process returned 0

Above is the source code and output for C++ program to implement Hash Table using Template Class which is successfully compiled and run on Windows System to produce desired output.

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach upto you in the short interval.


Thanks for reading the post….

2.8 4 votes
Article Rating
Subscribe
Notify of
guest

1 Comment
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
balla

it very nice web site