Ad:

C++ Discussion Thread
Unsolved
Views: 14460

Feb 27th, 2007

Hash Table template implementation help

Expand Post »

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:

C++ Syntax (Toggle Plain Text)
//
// 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;
}
//
// 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;
}

Similar Threads

compile error-chained hash table c++ in C++

zakula11

Reputation Points: 16

Solved Threads: 0

Newbie Poster

Offline

10 posts
since Feb 2007

Permalink

Feb 28th, 2007

Re: Hash Table template implementation help

Click to Expand / Collapse Quote originally posted by zakula11 ...

C++ Syntax (Toggle Plain Text)
... 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;
}
... 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

Last edited by Lazaro Claiborn; Feb 28th, 2007 at 6:44 pm.

Lazaro Claiborn

Reputation Points: 11

Solved Threads: 13

Junior Poster

Offline

171 posts
since Jan 2007

Permalink

Feb 28th, 2007

Re: Hash Table template implementation help

Thanks. Any idea how to code the Iterator? I have not a clue :\

zakula11

Reputation Points: 16

Solved Threads: 0

Newbie Poster

Offline

10 posts
since Feb 2007

Permalink

Feb 28th, 2007

Re: Hash Table template implementation help

Click to Expand / Collapse Quote originally posted by zakula11 ...

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:
C++ Syntax (Toggle Plain Text)
//
// 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;
}
// // 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":

C++ Syntax (Toggle Plain Text)

 // 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:

C++ Syntax (Toggle Plain Text)
// Array of the hash buckets.
  HashTableEntry<Data> *_buckets;
....
// This is probably what you'd meant anyway
buckets = new HashTableEntry<Data> [TableSize];
// 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

Last edited by Lazaro Claiborn; Feb 28th, 2007 at 9:10 pm.

Lazaro Claiborn

Reputation Points: 11

Solved Threads: 13

Junior Poster

Offline

171 posts
since Jan 2007

Permalink

Feb 28th, 2007

Re: Hash Table template implementation help

I was given skeleton code for this project, and

<LI class=li1> // Array of the hash buckets.
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.

zakula11

Reputation Points: 16

Solved Threads: 0

Newbie Poster

Offline

10 posts
since Feb 2007

Permalink

Mar 1st, 2007

Re: Hash Table template implementation help

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:

Get iterator to first and last element. (for for/while loop)
Get iterator to nth element. (for find function)
Support dereferencing (for getting to data).
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().

C++ Syntax (Toggle Plain Text)
  int i = hash(key);
  HashTableEntry<Data> *e = _buckets[i];
 
  while(e != NULL && strcmp(key, e->_key) != 0)
  {
    e = e->_next;
  }
  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:

C++ Syntax (Toggle Plain Text)
if( NULL != e )
{
      //Entry for this key already exists
      e->_data = data
      return true ;
}
else
//key didn't exist do the needful...
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.
------------------------

thekashyap

Reputation Points: 254

Solved Threads: 74

Practically a Posting Shark

Offline

804 posts
since Feb 2007

Permalink

Mar 1st, 2007

Re: Hash Table template implementation help

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

Reputation Points: 254

Solved Threads: 74

Practically a Posting Shark

Offline

804 posts
since Feb 2007

Permalink

Mar 1st, 2007

Re: Hash Table template implementation help

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[i]; 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[i] = e, resulting in the original list plus the new entry as the head of the list.

zakula11

Reputation Points: 16

Solved Threads: 0

Newbie Poster

Offline

10 posts
since Feb 2007

Permalink

Mar 2nd, 2007

Re: Hash Table template implementation help

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.

thekashyap

Reputation Points: 254

Solved Threads: 74

Practically a Posting Shark

Offline

804 posts
since Feb 2007

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: Question about private scope

Next Thread in C++ Forum Timeline: Query regarding the 'this' operator or pointer?

DaniWeb Message

Cancel Changes

User Name
Password