Hey. I kindof posted tihs before but it didnt have a good title. But, I had to implement the functions of a Hash Table template... I wasn't sure exactly how to do it, but I figured out a way to get it to work. I'm not positive if I did it correctly though (and I need to make sure it is because I need to use it again for another project). So if you could look at it and tell me if its right, that would be awesome
Also, I couldnt figure out how to code the 'iterator'.
Thanks
Here is what i got:
//
// CS251 Data Structures
// Hash Table template
//
#include <assert.h>
#include <stdlib.h>
#include <string.h>
///////////////////////////////////////////
//
// Class that defines a template for a hash table
// The keys are of type const char * and the data
// can be any type.
//
// Use like this:
// HashTable hashTableInt<int>;
//
//
///////////////////////////////////////////
// Each hash entry stores a key, object pair
template <typename Data>
struct HashTableEntry {
const char * _key;
Data _data;
HashTableEntry * _next;
};
// This is a Hash table that maps string keys to objects of type Data
template <typename Data>
class HashTable {
public:
// Number of buckets
enum { TableSize = 2039};
// Array of the hash buckets.
HashTableEntry<Data> **_buckets;
// Obtain the hash code of a key
int hash(const char * key);
public:
HashTable();
// Add a record to the hash table. Returns true if key already exists.
// Substitute content if key already exists.
bool insertItem( const char * key, Data data);
// Find a key in the dictionary and place in "data" the corresponding record
// Returns false if key is does not exist
bool find( const char * key, Data * data);
// Removes an element in the hash table. Return false if key does not exist.
bool removeElement(const char * key);
};
template <typename Data>
int HashTable<Data>::hash(const char * key)
{
// TODO: Compute the hash number from the key string
int sum=0;
int len = strlen(key);
for(int i=0; i < len; i++)
{
sum = sum + key[i];
}
return sum % TableSize;
}
template <typename Data>
HashTable<Data>::HashTable()
{
// TODO: Initialize the hash table
_buckets = new HashTableEntry<Data> * [TableSize];
for(int i=0; i < TableSize; i++)
{
_buckets[i] = NULL;
}
}
template <typename Data>
bool HashTable<Data>::insertItem( const char * key, Data data)
{
// TODO: Insert a key,data pair inside the hash table.
// Return true if the entry already exists or false if
// it does not exist.
int i = hash(key);
HashTableEntry<Data> *e = _buckets[i];
while(e != NULL && strcmp(key, e->_key) != 0)
{
e = e->_next;
}
if(e != NULL)
{
//key exists
e->_data = data;
return true;
}
//key does not exist
e = new HashTableEntry<Data>;
assert(e != NULL);
e->_key = key;
e->_data = data; //add entry to beg. of list
e->_next = _buckets[i];
_buckets[i] = e;
return false;
}
template <typename Data>
bool HashTable<Data>::find( const char * key, Data * data)
{
// TODO: Find the data associated to a key. The data is
// stored in the *data passed as parameter.
// Return true if the entry is found or false otherwise.
int i = hash(key);
HashTableEntry<Data> *e = _buckets[i];
while(e != NULL && strcmp(key, e->_key) != 0)
{
e = e->_next;
}
//key is found
if(e != NULL)
{
*data = e->_data;
return true;
}
//key was not found
return false;
}
template <typename Data>
bool HashTable<Data>::removeElement(const char * key)
{
// TODO: Remove the element that has this key from the hash table.
// Return true if the entry is found or false otherwise.
int i = hash(key);
HashTableEntry<Data> *eC = _buckets[i];
HashTableEntry<Data> *eP = NULL;
while(eC != NULL && strcmp(key, eC->_key) != 0)
{
eP = eC;
eC = eC->_next;
}
//key is found
if(eC != NULL)
{
if(eP != NULL)
eP->_next = eC->_next;
else
_buckets[i] = eC->_next;
return true;
}
//key is not found
return false;
}
/////////////////////////////////////
//
// Class used to iterate over the hash table
//
/////////////////////////////////////
template <typename Data>
class HashTableIterator {
int _currentBucket; // Current bucket that is being iterated
HashTableEntry<Data> *_currentEntry; // Current entry iterated
HashTable<Data> * _hashTable; // Pointer to the hash table being iterated
public:
HashTableIterator(HashTable<Data> * hashTable);
bool next(const char * & key, Data & data);
};
template <typename Data>
HashTableIterator<Data>::HashTableIterator(HashTable<Data> * hashTable)
{
// TODO: Initialize iterator. "hashTable" is the table to be iterated.
_hashTable = hashTable;
}
template <typename Data>
bool HashTableIterator<Data>::next(const char * & key, Data & data)
{
// TODO: Returns the next element in the hash table.
// The key and data values are stored in the references passed
// as argument. It returns true if there are more entries or
// false otherwise.
return false;
}