Q:

C++ program to implement Hash Table using Template Class

0

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++ ?

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now