Hey everybody,

So I though that I understood linked lists and arrays well enough to make a hash table with separate chaining. Theoretically, it seems trivial, but I am getting a runtime error.
The error appears to arise from the line head = heads, where head is a node pointer and heads is an array of node pointers.

When I tried to go through this issue with my debugger, all I got was an indecipherable 'Unhandled Exception' error and a runtime crash.

The node that I am using holds an instance of a class Person as its data member and the phone number string member of Person is used as the key.

Here is the code for the HashTable class and my main function with basic tests cases.
The error appears to occur at line 98:

#include <iostream>
#include <cmath>
#include <stdio.h>
#include <string>
#include "person.h"

using namespace std;

//typedef hashItemType Person;

class ChainNode{
    ChainNode(Person & nodeItem, ChainNode *nextNode = NULL) : item(nodeItem), next(nextNode) {}
    Person item;
    ChainNode * next;

    friend class HashTable;
};//end ChainNode class

class HashTable {
	struct node {
		Person item;
		node * next;
    //implement destructor

    bool tableIsEmpty() const;
    int tableGetLength() const;
    void tableInsert(Person  newItem);
    void tableDelete(string key);
    Person tableRetrieve(string key);
    int hash(string&);

    int hashIndex(string key) const;

    static const int HASH_TABLE_SIZE = 101;
    //typedef ChainNode * HashTableType[HASH_TABLE_SIZE];
	//HashTableType table;
	node * heads[HASH_TABLE_SIZE];
    int size;
};//end HashTable

Person HashTable::tableRetrieve(string key)
    int i = hash(key);
    //ChainNode * p;
    //p = table[i];
	node * head = heads[i];

    while( (head != NULL) && (head->item.getPhonenumber() != key))
        head = head->next;
    }//end while
    if(head == NULL)
        cout << "No values with that key" << endl;
    }//end if
        return head->item;
    }//end else

int HashTable::hash(string &key)
    int hashVal = 0;
    for(int i = 0; i< key.size(); i++)
        hashVal = 37*hashVal+key[i];
        hashVal %= HASH_TABLE_SIZE;
        if(hashVal < 0)
            hashVal += HASH_TABLE_SIZE;
        return hashVal;
    }//end for
}//end hash

void HashTable::tableInsert(Person newitem)
    cout << "inside function" << endl;
    string key = newitem.getPhonenumber();
    cout << "got key" << endl;
    int i = hash(key);
    cout << i << endl;
    cout << "got index" << endl;
    //ChainNode * p;
	node * head = new node;
	head = heads[i];
    cout << "created new node" << endl;
	head->item = newitem;
	cout << "birds" << endl;
    head->next = heads[i];
    heads[i] = head;

int main() {

    HashTable ht;
    Person p;

    return 0;

and here is the code for the Person class:

#include <iostream>
#include <cstdlib>
#include <fstream>
#include <iomanip>
#include <stdio.h>
#include <string>
using namespace std;

class Person{
    string name;
    string phonenumber;
    string GPA;
    Person(string name, string phonenumber);
    string getName();
    string getPhonenumber();
    void setName(string newname);
    void setPhonenumber(string newphonenumber);
    void setGPA(string);
    string getGPA();


Person::Person(string newname, string newphonenumber)
    name = newname;
    phonenumber = newphonenumber;

string Person::getName() {
    return name;

string Person::getPhonenumber() {
    return phonenumber;

void Person::setName(string newname) {
    name = newname;

void Person::setPhonenumber(string newphonenumber) {
    phonenumber = newphonenumber;

string Person::getGPA() {
    return GPA;

void Person::setGPA(string newGPA) {
    GPA = newGPA;

Any input anybody has on what is going wrong would be greatly appreciated. I'm pretty stumped at this point.

6 Years
Discussion Span
Last Post by Agni

As far as I can see the heads array is empty and you have not-populated it before you access it in 'tableInsert' function. So heads is actually undefined. Moreover you have a memory leak at line 97-98 since you declare a pointer to node and try to assign it to something else.

Read about linked lists here to clear your doubts, Linked List

Edited by Agni: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.