Help with hash table implementation

[Ryan Kaskel]

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:ut(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]

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:ut(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