Help with hash table implementation

Discussion in 'C++' started by Ryan Kaskel, Apr 26, 2006.

  1. Ryan Kaskel

    Ryan Kaskel Guest

    Hi! I am new to this newsgroup and need help implementing a hash table.
    This assignment is for school but only concerns one method. Basically we
    have to write methods like put(), get(), expandCapacity(), etc. The hash
    table is an array of pointer to HashNodes. Below is the header file for
    the HashTable and HashNode classes:

    > #ifndef HASHTABLE_H_
    > #define HASHTABLE_H_
    >
    > class Person;
    > class String;
    > class HashNode;
    > class HashtableIterator;
    >
    > class Hashtable {
    > HashNode** table;
    > int _capacity, _size;
    > virtual void putUnchecked(String* key, Person* value);
    > virtual HashNode* findNode(HashNode* node, String* key);
    >
    > public:
    > Hashtable();
    > virtual ~Hashtable();
    > virtual Person* get(String* key);
    > virtual void put(String* key, Person* value);
    > virtual void remove(String* key);
    > virtual int size();
    > virtual void clear();
    > virtual void printStats();
    > virtual int capacity();
    > virtual void expandCapacity();
    > virtual void printDistribution();
    > virtual void print(char* title);
    > virtual HashtableIterator* createIterator();
    > };
    >
    > class HashtableIterator {
    > int _capacity;
    > HashNode** table;
    > int index;
    > HashNode* node, *current;
    > bool seen;
    >
    > public:
    > HashtableIterator(HashNode** table, int capacity);
    > virtual ~HashtableIterator();
    > virtual bool hasCurrent();
    > virtual Person* getValue();
    > virtual String* getKey();
    > virtual void advance();
    > };
    >
    >
    > class HashNode {
    > String* key;
    > Person* value;
    > HashNode* next;
    >
    > public:
    > HashNode(String* key, Person* value, HashNode* next);
    > virtual ~HashNode();
    > virtual HashNode* getNext();
    > virtual String* getKey();
    > virtual String* toString();
    > virtual Person* getValue();
    > virtual void setNext(HashNode* node);
    > virtual void setValue(Person* value);
    > };
    >
    > #endif /*HASHTABLE_H_*/


    I am having difficulty with the put() method. Below is my attempt at it.

    > void Hashtable::put(String* key, Person* value) {
    > HashNode *newNode = new HashNode(key, value, NULL);
    > int index = key->hashCode() % capacity();
    > if (this->table[index] != NULL)
    > newNode->setNext(this->table[index]);
    > this->table[index] = newNode;
    > _size++;
    > }


    Note that at this point I am not concerned with expanding capacity if
    the table is almost full. I am just trying to get the first unit test
    the professor provided to pass. The Person object (which is the data
    type the HashNodes store) in the unit test hashes to 1. The constructor
    of the hash table sets the initial capacity to 4 so the table's capacity
    should not need to be increased. The problem is when I output the
    contents of the table using a print() function the professor provided,
    the inserted HashNode isn't there.

    > Starting TestAll...
    > ******** Starting HashtableTest ********
    >
    > Passed testSizeZero()
    > Passed testPutOne()
    >
    >
    > ** End Test **
    > table[0]
    > table[1]


    notice how nothing is listed in table[1]

    > table[2]
    > table[3]
    >
    >
    > Results of HashtableTest:
    > Number of tests: 2
    > Test failures: 0
    >
    > ********** HashtableTest done **********
    > TestAll done.


    Can someone point me in the right direction? I'm only passing the test
    because I increase the _size member to one and it only checks that it
    does in fact equal 1. I don't understand why table[1] isn't being set to
    the newly allocated HashNode.

    Thanks,
    Ryan Kaskel
     
    Ryan Kaskel, Apr 26, 2006
    #1
    1. Advertising

  2. Ryan Kaskel

    Ryan Kaskel Guest

    Ryan Kaskel wrote:
    > Hi! I am new to this newsgroup and need help implementing a hash table.
    > This assignment is for school but only concerns one method. Basically we
    > have to write methods like put(), get(), expandCapacity(), etc. The hash
    > table is an array of pointer to HashNodes. Below is the header file for
    > the HashTable and HashNode classes:
    >
    >> #ifndef HASHTABLE_H_
    >> #define HASHTABLE_H_
    >>
    >> class Person;
    >> class String;
    >> class HashNode;
    >> class HashtableIterator;
    >>
    >> class Hashtable {
    >> HashNode** table;
    >> int _capacity, _size;
    >> virtual void putUnchecked(String* key, Person* value);
    >> virtual HashNode* findNode(HashNode* node, String* key);
    >>
    >> public:
    >> Hashtable();
    >> virtual ~Hashtable();
    >> virtual Person* get(String* key);
    >> virtual void put(String* key, Person* value);
    >> virtual void remove(String* key);
    >> virtual int size();
    >> virtual void clear();
    >> virtual void printStats();
    >> virtual int capacity();
    >> virtual void expandCapacity();
    >> virtual void printDistribution();
    >> virtual void print(char* title);
    >> virtual HashtableIterator* createIterator();
    >> };
    >>
    >> class HashtableIterator {
    >> int _capacity;
    >> HashNode** table;
    >> int index;
    >> HashNode* node, *current;
    >> bool seen;
    >>
    >> public:
    >> HashtableIterator(HashNode** table, int capacity);
    >> virtual ~HashtableIterator();
    >> virtual bool hasCurrent();
    >> virtual Person* getValue();
    >> virtual String* getKey();
    >> virtual void advance();
    >> };
    >>
    >>
    >> class HashNode {
    >> String* key;
    >> Person* value;
    >> HashNode* next;
    >>
    >> public:
    >> HashNode(String* key, Person* value, HashNode* next);
    >> virtual ~HashNode();
    >> virtual HashNode* getNext();
    >> virtual String* getKey();
    >> virtual String* toString();
    >> virtual Person* getValue();
    >> virtual void setNext(HashNode* node);
    >> virtual void setValue(Person* value);
    >> };
    >>
    >> #endif /*HASHTABLE_H_*/

    >
    > I am having difficulty with the put() method. Below is my attempt at it.
    >
    >> void Hashtable::put(String* key, Person* value) {
    >> HashNode *newNode = new HashNode(key, value, NULL);
    >> int index = key->hashCode() % capacity();
    >> if (this->table[index] != NULL)
    >> newNode->setNext(this->table[index]);
    >> this->table[index] = newNode;
    >> _size++;
    >> }

    >
    > Note that at this point I am not concerned with expanding capacity if
    > the table is almost full. I am just trying to get the first unit test
    > the professor provided to pass. The Person object (which is the data
    > type the HashNodes store) in the unit test hashes to 1. The constructor
    > of the hash table sets the initial capacity to 4 so the table's capacity
    > should not need to be increased. The problem is when I output the
    > contents of the table using a print() function the professor provided,
    > the inserted HashNode isn't there.
    >
    >> Starting TestAll...
    >> ******** Starting HashtableTest ********
    >>
    >> Passed testSizeZero()
    >> Passed testPutOne()
    >>
    >>
    >> ** End Test **
    >> table[0]
    >> table[1]

    >
    > notice how nothing is listed in table[1]


    Okay, this is incorrect. I am calling a print() method on a different
    HashTable object than that in the unit test. I am instead getting a
    segmentation fault.

    >
    >> table[2]
    >> table[3]
    >>
    >>
    >> Results of HashtableTest:
    >> Number of tests: 2
    >> Test failures: 0
    >>
    >> ********** HashtableTest done **********
    >> TestAll done.

    >
    > Can someone point me in the right direction? I'm only passing the test
    > because I increase the _size member to one and it only checks that it
    > does in fact equal 1. I don't understand why table[1] isn't being set to
    > the newly allocated HashNode.
    >
    > Thanks,
    > Ryan Kaskel
     
    Ryan Kaskel, Apr 26, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Diane
    Replies:
    7
    Views:
    4,818
    Roland Pibinger
    Apr 4, 2006
  2. Jim Cobban
    Replies:
    8
    Views:
    548
    Jerry Coffin
    Apr 17, 2008
  3. aki

    Hash table Implementation

    aki, Mar 29, 2011, in forum: C Programming
    Replies:
    3
    Views:
    778
    Jorgen Grahn
    Apr 6, 2011
  4. rp
    Replies:
    1
    Views:
    544
    red floyd
    Nov 10, 2011
  5. Srijayanth Sridhar
    Replies:
    19
    Views:
    631
    David A. Black
    Jul 2, 2008
Loading...

Share This Page