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;
}
Comments
This helped me a lot !!.. Thanks
... 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;
}

Everything looks copacetic except for the above. The "next" member function might produce a compilation error because you specify a pointer and a referrence for parameter "key". But otherwise it looks good and it is very well formatted, kudo's. I usually use class instead of typename, but I haven't created any type of template in a while.

Good luck, LamaBot

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

I'll have to get back at you about how to write the iterative portion. But I've noticed that you have the following code when declaring "_buckets":

// Array of the hash buckets.
  HashTableEntry<Data> **_buckets;

When you initialize buckets in the HashTableEntry constructor, it returns an address to an array of type HashTableEntry. The above say's that buckets is going to hold an address, whose value is an address, whose value is the first address of a HashTableEntry object. But when you initialize it via "new" in the constructor, it returns an address, and places it in buckets which expects an address of pointer to type HashTableEntry. Also, when you're using new to create an array of size "HashTableSize" the generated code for the template class times HashTableSize is an expression. It seem like you'd want modify it to the following:

// Array of the hash buckets.
  HashTableEntry<Data> *_buckets;
....
// This is probably what you'd meant anyway
buckets = new HashTableEntry<Data> [TableSize];

Anyway, if you've got any problem with the above let me know.

Good luck, LamaBot

I was given skeleton code for this project, and

  1. <LI class=li1> // Array of the hash buckets.

  2. HashTableEntry<Data> **_buckets;

was given to me already. I don't believe I was allowed to change it.
Now I'm working on another project , making a webcrawler, and I have most of it done, but the HashTable template is again holding me back. I need it to 1) map a URL to an index in an array, and 2) map a word to a list of URLs that contain that word.

Looking at the declaration of HashTableEntry I assume your iterator is expected to be a ForwardIterator only (not Random, Bidirectional or Backward)
So here are few pointers for implementing a ForwardIterator.

A. Define the interface. For this look at the usecases.
Usecases:

  1. Get iterator to first and last element. (for for/while loop)
  2. Get iterator to nth element. (for find function)
  3. Support dereferencing (for getting to data).
  4. Support operator++. (for for/while loop)

B. Implementation changes required.
In HashTableIterator:
- Implement operator* (for point 3). Just return _currentEntry.
- Implement operator++. (for point 4): Just update _currentEntry with _currentEntry->next ;
- Implement a constructor that takes a HashTableEntry (for point 2). Update members based on HashTableEntry passed as argument.

In HashTable:
- Have a members (say m_first, m_end) of type HashTableIterator that represent first and last elements. For last element I remember (from some training) that HashTableIterator m_lastIter; should NOT be a valid iterator. In other words m_end does NOT point to the last element, but instead it's just an indicator that you've iterated thru the whole list. I forget the reason, but I guess it's just to simplify loop terminating condition. (for point 1).
- Update insertItem() so that it updates m_first on insertion if needed.
- Update the c'tor for the same thing.

Do get back if you need the code. But as always it would be nice for you to try first.

----------------------------
Just to comment on the existing implementation.
1. Inside insertItem().

int i = hash(key);
  HashTableEntry<Data> *e = _buckets[i];

  while(e != NULL && strcmp(key, e->_key) != 0)
  {
    e = e->_next;
  }

Isn't it that hash() ALWAYS returns same number for same key? If yes, why is the while loop present?
Instead of while loop shouldn't it be:

if( NULL != e )
{
      //Entry for this key already exists
      e->_data = data
      return true ;
}
else
//key didn't exist do the needful...

Reason why I ask is if you are supposed to take care of collisions you need a lot more code than this. See this.
2. Inside insertItem(): I didn't get why is e->_next = _buckets[i]; done? For the purpose of implementing iterator it would be required that HashTableEntry::_next always contains a valid pointer. So it should be updated in such a way that it points to either next valid HashTableEntry or to m_end.
------------------------

Sorry just saw that you have HashTableIterator::next(). You can either keep that or implement operator++. Both are one and the same from your code perspective, but just that clinets like me might prefer it++ then it = it->next().

thekashyap, thanks for your reply. My biggest problem with the iterator was knowing where to start and end (I think... I'm also not exactly sure how to find the ones in the middle of their are empty indexes). Adding member variables to store the first and last elements may help me figure it out. I will try to code this after a few hours of sleep, haha.

In regards to your comment on my implementation of the hash() fuction.... each HashTableEntry in _buckets[] actually represents a linked list (at least thats the way I imagined it while I was writing the code, though I was also very confused)

So, yes it is true that hash() will always return the same number for the same key. However, it is also possible that the same number will be returned for different keys. When this is the case, it adds the entry to the linked list for that index in the hash table: e->_next;

Hence,
e->_next = _buckets; is used in insertItem() because it is actually just adding the entry to the beginning of the current linked list. The next line after this sets _buckets = e, resulting in the original list plus the new entry as the head of the list.

Aha now I understood. . You are indeed trying to take care of collisions. Then may be the link I gave in previous post would be good to see.

You mentioned that "each HashTableEntry in _buckets[] actually represents a linked list" => To ensure that the list is actually complete you must ensure what I said earlier:
"For the purpose of implementing iterator it would be required that HashTableEntry::_next always contains a valid pointer. So it should be updated in such a way that it points to either next valid HashTableEntry or to m_end."
When I ran your program and I see that _next is not set correctly for all HashTableEntry objects.

Now it may not be that easy to ensure that _next of all elements always point to appropriate HashTableEntry object (particularly when you're inserting in the middle, you need to go on both sides and find out not-null HashTableEntry objects and update _next for 2 objects).

It might be easier if you just maintain another array of integers that contains all indexes where a valid HashTableEntry object is present in _buckets. That way there won't be any need for _next. Add these members int _size, _filled_buckets[TableSize] ; to HashTable. In insertItem() just push hash value (i.e i) into this array. _filled_buckets[++_size] = i; . (you need to think how to implement removeItem() though).

Finally the most imp thing I forgot to mention, Iterator type should be a contained type in the container to which applies. I.e. HashTableInterator should be contained/declared inside HashTable. Once this is done the HashTableInterator::next() should just pickup the next index from _filled_buckets[] and update itself.

This article has been dead for over six months. Start a new discussion instead.