C++ classes: Hash Table

____________________________________

First: Header file.h (functions prototype).

____________________________________ 

// File: hashTable.h
// Definition of Hash Table Template Class
#ifndef HASH_TABLE_H
#define HASH_TABLE_H

// Specification of the class
template <class keyType, class dataType>

class hashTable
{
  public:
       
    // Member Functions
    hashTable(int nelements = 11);        // Constructor
    ~hashTable();                        // Destructor
   
    // Functions Prototype Definitions
   
    void emptyTable(const keyType & );
    bool tableIsEmpty() const;
    bool tableIsFull() const;
    int  occupancy() const;
    bool insert(const keyType &, const dataType & );
    bool search(const keyType & );
    //void remove();
    void updateData(const dataType & );
    void retrieveData(dataType &) const;
    void traverse() const;
   
  private:
   
    // Slot Class
       class slot
       {
        public:
            keyType key;         // key
            dataType data;        // Data
        }; // end of class slot declaration

    slot *T;                            // Pointer to Storage Array
    int h;                                // Index to a slot
    int MaxSize, csize;                    // Maximum and Current Sizes
    keyType Empty;                        // empty symbol

    // Private Member function
    int hash(const keyType & ) const;
};
#endif // HASH_TABLE_H
#include "hashTable.cpp"

________________________________________________ 

second: Implementation file.cpp 

_____________________________________

  

// File:hashTable.cpp
// hashTable Class implementation file


#include <iostream>
using namespace std;


// Constructor with argument, size is nelements, default is 11
template <class keyType, class dataType>
hashTable<keyType, dataType>::hashTable(int nelements)  
{  MaxSize = nelements; T = new slot[MaxSize];  h = -1; csize = 0;} 


// Destructor
template <class keyType, class dataType>
hashTable<keyType, dataType>::~hashTable()
{ delete [] T;}


// Empty all slots
template <class keyType, class dataType>
void hashTable<keyType, dataType>::emptyTable(const keyType &k)
{
    Empty = k;
    for(int i = 0; i < MaxSize; i++) T[i].key = Empty;
    h = -1;  csize = 0;
}

// return True if table is empty
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::tableIsEmpty() const
{
    return (csize == 0);
}

// return True if table is full
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::tableIsFull() const
{
    return (csize == MaxSize);
}

// to return the current occupancy of the table
template <class keyType, class dataType>
int hashTable<keyType, dataType>::occupancy() const
{   
    return csize;   
}


// insert key and data at a hashed slot
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::insert(const keyType &k, const dataType &d)
{   
    if (!tableIsFull())   
    {
        h = hash(k);
        while(T[h].key != Empty)
            h = (h+1) % MaxSize;
        T[h].key = k;  T[h].data = d; csize++;
        return true;
    }
    else return false;
}

// Search the table for the slot that matches key.
// If found, return True, set current position to slot
template <class keyType, class dataType>
bool hashTable<keyType, dataType>::search(const keyType &k )
{   
   
      if(!tableIsEmpty())
    {
        h = hash(k); int start = h;
        for ( ; ; )
        {
            if (T[h].key == Empty) return false;
            if (k == T[h].key) return true;
            h = (h+1) % MaxSize;
            if (h == start) return false;
        }
    }
    else return false;
}

/* Remove given key from (make deleted) current slot
template <class keyType, class dataType>
void hashTable<keyType, dataType>::remove()
{
    T[h].key = Deleted;   
}
*/

// Update the data part of the current slot
template <class keyType, class dataType>
void hashTable<keyType, dataType>::updateData(const dataType &d )
{
    if ((h >=0)&&(h < MaxSize)) T[h].data = d;
}

// Retrieve the data part of the current slot
template <class keyType, class dataType>
void hashTable<keyType, dataType>::retrieveData(dataType &d) const
{
    if ((h >= 0)&&(h < MaxSize)) d = T[h].data;
        else d = T[0].data;
}

// Traverse whole table
template <class keyType, class dataType>
void hashTable<keyType, dataType>::traverse() const
{
    for(int i = 0; i < MaxSize; i++)
        cout << T[i].key << endl;
}

// Private Hashing Function
template <class keyType, class dataType>
int hashTable<keyType, dataType>::hash(const keyType &k ) const
{
    return (k % MaxSize);
}

________________________________________________ 

finally class test

_____________________________________

// File: hashtest.cpp
// Test class template hashTable
#include <iostream>
using namespace std;
#include "hashTable.h"

int main()
{
    const int N = 9;
    int A[N] = {55,35,66,76,59,48,84,70,54};
    int B[N] = {1,2,3,4,5,6,7,8,9};
    int e = -1;
    int x,d;
    hashTable<int, int> HT;
    cout << "Constructing empty Hash Table\n";
    HT.emptyTable(e);
    cout << "Table " << (HT.tableIsEmpty() ? "is" : "is not") << " empty\n";
    cout << "Traversing\n";
    HT.traverse();
    for(int i = 0; i<N; i++)
            if(HT.insert(A[i], B[i])) cout << A[i] <<" is inserted, occupancy = "
                << HT.occupancy() << endl;
  
    cout << "Table " << (HT.tableIsEmpty() ? "is" : "is not") << " empty\n";
    cout << "Traversing\n";
    HT.traverse();
    cout << "Searching\n";
    x = A[2];
    cout << x << (HT.search(x) ? " is" : " is not") << " found\n";
    cout << "Retrieving data part of " << x;
    HT.retrieveData(d);  cout <<" = " << d;
    cout << endl;
    cout << "Updating\n";
    HT.updateData(99);
    cout << "Retrieving data part of " << x;
    HT.retrieveData(d);  cout <<" = " << d;
    cout << endl;
    x = 123;
    cout << x << (HT.search(x) ? " is" : " is not") << " found\n";
    x = 70;
    cout << "Searching\n";
    cout << x << (HT.search(x) ? " is" : " is not") << " found\n";
    cout << "Retrieving data part of " << x;
    HT.retrieveData(d);  cout <<" = " << d;
    cout << endl;
    cout << "Traversing\n";
    HT.traverse();
    x = 44;
    if(HT.insert(x, 10)) cout << x <<" is inserted, occupancy = "
                << HT.occupancy() << endl;
    cout << "Traversing\n";
    HT.traverse();
    return 0;
}