asked on

Hash Table

This is kind a continuation of a project I have been working on that compares the efficiency of a binary tree, linked list, and now a hash table. Here is what I have for main()...and the HashTable. When its finished the HashTable will also display in main the same basic cout statements as the other two. What I need help with is the main() implementation and what is noted in the HashTable comments...I will raise points to whomever helps me complete it. Thanks.

-----------------------------------------
main()

#include "BST.h"
#include "LL.h"
#include "HashTable.h"
#include <iostream>
#include <ctime>

using namespace std;

int randomNumberGenerator();

void main()
{

bool promptUser = true;
char userSelection[10];
int avgFoundBST = 0;
 int avgFoundmyList = 0;
int avgNotFoundBST = 0;
 int avgNotFoundmyList = 0;
int counter = 0;
int foundBST = 0;
 int foundmyList = 0;
int notFoundBST = 0;
 int notFoundmyList = 0;
int compFoundBST = 0;
 int compFoundmyList = 0;
int compNotFoundBST = 0;
 int compNotFoundmyList = 0;
int linkedListCount = 0;
int numCompares = 0;
int ranNum = 0;
int ran = 0;

BST<int> myBST;
LinkedList myList;

while(promptUser)
{
int i;
//seed generator
srand(11111111);
int t1 = clock();
for (i = 0; i < 40000; i ++)
{
myBST.insert(rand());
}

int t2 = clock();
srand(11111111);
int t3= clock();
for (i = 0; i < 40000; i ++)
{
myList.insertEnd(rand());
}

int t4 = clock();
cout << "How many tests would you like to perform? (Enter 'Q' to quit)" << endl;

//test search
cin.getline(userSelection, 10);

//Converts the selection to a number to test
int numTests = atoi(userSelection);
if(numTests > 0)
{
cout << endl << "Performing tests: " << endl << endl;

srand(33333333); // take another seed number or all numbers would be found
for(i = 0; i < numTests; i ++)
{
//Search array new generated random number
ran = rand();
if (myBST.search(ran, numCompares))
{
foundBST++;
compFoundBST += numCompares;
}
else
{
notFoundBST++;
compNotFoundBST += numCompares;
}
cout << ran << endl;
//resets the numCompares counter
numCompares = 0;
}
 srand(33333333); // take another seed number or all numbers would be found
for(i = 0; i < numTests; i ++)
{
//Search array new generated random number
ran = rand();
if (myList.search(ran, numCompares))
{
foundmyList++;
compFoundmyList += numCompares;
}
else
{
notFoundmyList++;
compNotFoundmyList += numCompares;
}
cout << ran << endl;
//resets the numCompares counter
numCompares = 0;
}

counter = numTests;

avgFoundBST = ((foundBST * 100 + counter / 2)/ counter);
avgNotFoundBST = ((notFoundBST * 100 + counter / 2)/ counter);

 avgFoundmyList = ((foundmyList * 100 + counter / 2)/ counter);
avgNotFoundmyList = ((notFoundmyList * 100 + counter / 2)/ counter);

cout << endl << "Binary Search Tree" << endl;
cout << "Number Found " << foundBST << endl;
cout << "Number Not Found " << notFoundBST << endl;
cout << "Ttl Compares (Found) " << compFoundBST << endl;
cout << "Ttl Compares (Not Found) " << compNotFoundBST << endl;
cout << "Avg Compares (Found) " << avgFoundBST << endl;
cout << "Avg Compares (Not Found) " << avgNotFoundBST << endl << endl;
cout << "Tree Depth : " << myBST.depth() << endl;
cout << "Tree Node Count : " << myBST.count() << endl << endl;

 cout << "Linked List" << endl;
cout << "Number Found " << foundmyList << endl;
cout << "Number Not Found " << notFoundmyList << endl;
cout << "Ttl Compares (Found) " << compFoundmyList << endl;
cout << "Ttl Compares (Not Found) " << compNotFoundmyList << endl;
cout << "Avg Compares (Found) " << avgFoundmyList << endl;
cout << "Avg Compares (Not Found) " << avgNotFoundmyList << endl << endl;
 cout << "Linked List Count : " << myList.getLength() << endl << endl;
}

else if(toupper(userSelection[0]) == 'Q')
{
promptUser = false;
}

//invalid user input
else
{
cout << "Enter a number greater than zero" << endl;
cout << "Q to quit" << endl;
promptUser = true;
}
}
}
--------------------------------------------

HashTable.h

#ifndef HASH_TABLE_INCLUDED
#define HASH_TABLE_INCLUDED

//-- INCLUDES -----------------------------------------------------------------
#include <iostream>
#include <new>
using namespace std;

template <typename TYPE>
class HashTable
{
 // the possible state values that a record can be in
 enum RecordState { EMPTY, OCCUPIED, DELETED };

 // the basic hash table record
 // NEED HELP: Modify this structure so it just stores a linked list of TYPE
 struct HashRecord
 {
 TYPE data; // piece of data in this record
 RecordState state; // state of the record

 // add a new item record with a hash entry of OCCUPIED
 HashRecord(const TYPE & newData)
 {
 data = newData;
 state = OCCUPIED;
 }

 // default constructor makes sure state is EMPTY
 HashRecord()
 {
 state = EMPTY;
 }
 };

 // the actual ptr to the dynamic array
 HashRecord * array;
 unsigned capacity;
 unsigned count;

 // private method to find hash location
 int generateHashLocation(const TYPE & item) const
 {
 return item % capacity; // simple mod hash function
 }

public:
 // constructor to create the hash table at a given capacity
 HashTable(unsigned maxCapacity);

 // gets for capacity and count
 unsigned getCapacity() const { return capacity; }
 unsigned getCount() const { return count; }

 // method to add to hash table. Returns false if no capacity remaining
 bool add(const TYPE & newItem);

 // method to remove from hash table. Returns false if item not existing
 bool remove(const TYPE & oldItem);

 // method to retrieve from the hash table. Returns false if not found
 bool find(TYPE & searchItem) const;

 // display prints contents of table
 void display(ostream & out);

 // copy constructor
 HashTable(const HashTable<TYPE> & oldTable);

 // assignment operator
 const HashTable<TYPE> & operator = (const HashTable<TYPE> & oldTable);

 // destructor
 ~HashTable();

};

// constructor to create the hash table at a given capacity
template <typename TYPE>
HashTable<TYPE>::HashTable(unsigned maxCapacity)
 : array(NULL), count(0), capacity(0)
{
 // will call default constructor on each record, setting them to
 // EMPTY
 array = new HashRecord[maxCapacity];

 // make sure no errors
 if(!array)
 {
 cerr << "Could not create hash table with size " << maxCapacity << endl;
 }

 else
 {
 capacity = maxCapacity;
 }
}

// method to add to hash table. Returns false if no capacity remaining
// -----------
// NEED HELP: Update to use chaining (close addressing). Instead of checking
// to see if the cell is occupied, insert it into the list
// at the home location if it does not already exist.
template <typename TYPE>
bool HashTable<TYPE>::add(const TYPE & newItem)
{
 if(count < capacity)
 {
 int loc = generateHashLocation(newItem); // natural loc

 // linear probe. If array is occupied at hash location, increment
 // the probe. Could also do quadratic probe here.
 while(array[loc].state == OCCUPIED)
 {
 loc = (loc+1) % capacity; // wrap around if goes off edge
 }

 array[loc].state = OCCUPIED;
 array[loc].data = newItem;
 count++;
 return true;
 }

 // no space found, can't insert
 return false;
}

// method to remove from hash table. Returns false if item not existing
// -----------
// NEED HELP: Update to use chaining (close addressing). Instead of checking
// to see if the cell is occupied, delete the item in the
// linked list if it exists.
template <typename TYPE>
bool HashTable<TYPE>::remove(const TYPE & oldItem)
{
 bool found = false;

 int homeloc = generateHashLocation(oldItem); // natural loc
 int loc = homeloc;

 // linear probe. If array is occupied at hash location, increment
 // the probe. Could also do quadratic probe here.
 while((array[loc].state != EMPTY) && !found)
 {
 // check if item we want
 if((array[loc].data == oldItem) && (array[loc].state == OCCUPIED))
 {
 found = true;
 array[loc].state = DELETED;
 count--;
 }
 else
 {
 loc = (loc+1) % capacity; // wrap around if goes off edge

 // if we loop all the way around back to home loc, stop
 if(loc == homeloc)
 break;
 }
 }

 // no space found, can't insert
 return found;
}

// method to retrieve from the hash table. Returns false if not found
// -----------
// NEED HELP: Update to use chaining (close addressing). Search the linked list
// and return true if it is found
template <typename TYPE>
bool HashTable<TYPE>::find(TYPE & searchItem) const
{
 bool found = false;

 int homeloc = generateHashLocation(searchItem); // natural loc
 int loc = homeloc;

 // linear probe. If array is occupied at hash location, increment
 // the probe. Could also do quadratic probe here.
 while((array[loc].state != EMPTY) && !found)
 {
 // check if item we want
 if((array[loc].data == searchItem) && (array[loc].state == OCCUPIED))
 {
 found = true;
 }
 else
 {
 loc = (loc+1) % capacity; // wrap around if goes off edge

 // if we loop all the way around back to home location, stop
 if(loc == homeloc)
 break;
 }
 }

 // no space found, can't insert
 return found;
}

// display prints contents of table
// -----------
// NEED HELP: Update to use chaining (close addressing). Print
// all linked lists in the cells with linked list size > 0
template <typename TYPE>
void HashTable<TYPE>::display(ostream & out)
{
 for(unsigned i=0; i<capacity; i++)
 {
 if(array[i].state == OCCUPIED)
 {
 out <
HashTable<TYPE>::HashTable(const HashTable<TYPE> & oldTable)
 : array(NULL), size(0), capacity(0)
{
 array = new HashRecord[oldTable.capacity];

 // if allocation failed, print error
 if(!array)
 {
 cerr << "Could not create copy of hash table of size "
 << oldTable.capacity << endl;
 }

 // otherwise copy the table
 else
 {
 size = oldTable.size;
 capacity = oldTable.capacity;

 for(unsigned i = 0; i<capacity; i++)
 {
 array[i] = oldTable.array[i];
 }
 }
}

// assignment operator
template <typename TYPE>
const HashTable<TYPE> & HashTable<TYPE>::operator = (const HashTable<TYPE> & oldTable)
{
 if(this != &oldTable)
 {
 // clear old mem
 delete [] array;
 count = capacity = 0;

 array = new HashRecord[oldTable.capacity];

 // if allocation failed, print error
 if(!array)
 {
 cerr << "Could not create copy of hash table of size "
 << oldTable.capacity << endl;
 }

 // otherwise copy the table
 else
 {
 size = oldTable.size;
 capacity = oldTable.capacity;

 for(unsigned i = 0; i<capacity; i++)
 {
 array[i] = oldTable.array[i];
 }
 }
 }

 return *this;
}

// destructor
template <typename TYPE>
HashTable<TYPE>::~HashTable()
{
 delete [] array;
}

#endif

itsmeandnobodyelse

jandhb,

the first you have todo is to turn LinkedList class to a template class. You cannot use it in template class HashTable if the data element couldn't be set arbitrarily.

I have done it, but it isn't quite an easy job. These are the steps to do:

- Remove typedef or definition of type Generic

- Change class Node (in Node.h) to a template class:

// forward declaration
template <typename Generic>
class LinkedList;

template <typename Generic>
class Node
{
Generic data;
Node<Generic>* next;

friend class LinkedList<Generic>;
};

- Move all LinkedList functions of ll.cpp to ll.h

- Add the template class specifier to class and all functions:

//declaration of LinkedList class
template <typename Generic>
class LinkedList
{
...
};

- Change all Occurences of class Node to Node<Generic>, e. g.

//first element in linked list
Node<Generic> *first;
//last element in linked list
Node<Generic> *last;

- Remove ll.cpp from your project/makefile

- Change LinkedList variable in main() to

LinkedList<int> myList;

Regards, Alex