Project help

[developer4321]

Hey, for part of my project, I have to implement a Hash Table template. I had to implement several other classes too, and I finished them. But I really don't know much at all about hash tables and templates, and am not sure how to go about this at all... If someone can give me some help or direction that would be great.

The code I am given is below... I have to fill in the TODO's.
Thanks.

//
// 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
  return (int)key;
}
 
template <typename Data>
HashTable<Data>::HashTable()
{
  // TODO: Initialize the hash table
}
 
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.
  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.
  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.
  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.
}
 
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;
}

[dwks]

http://www.sparknotes.com/cs/searching/hashtables/section1.html
http://www.cprogramming.com/tutorial/templates.html

[developer4321]

Thanks. Those links helped me alot. I got the class implemented (except for the iterator part... I was still unable to figure that out.), and was able to pass 7 of the 9 test cases (the other two involved the iterator).

However, although I got it to pass the testcases, I am still not positive that I implemented it correctly. The implementation of a hash table will also be important for my new current project (building a webcrawler) and future projects (building a search engine).
So I was wondering if you can look at my implementation and tell me if I did it correctly, and also how to implement the iterator.

Thanks for the help.

Here is my updated implementation:

//
// 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;
}