C++ Access Violation With Hash Tables and Linked Lists

Question

So I've been trying to create a class that handles 1000 linked lists, and initially declares pointers to them.

This is the code that deals directly with my issues:

struct node
{
    char name[40];
    char numb[12];
    node * next;
};
class hashTable
{
public:
    //Creates a table of 1000 pointers to linked-list nodes
    node * table[1000];

//Functions
void addNode(char name[40], char numb[12])
{
    node * temp;        //Initializes temp node as pointer
    temp = new node;    //Points temp node to a new node

    int hash = h(g(name));  //The hash of the key (name) used to check nodes
    temp = table[hash];     //sets the temporary node to the first node of the list

    while (temp->next != 0)
    {
//...

Right at the while loop is where I get the error "Access violation reading location 0xcccccd00" I'm not sure why it can't access the table member, unless perhaps it is because these values have not been initialized or anything?

Perhaps it is because these values have not been initialized or anything? — Thomas, Mar 20 '13 at 18:52
I would say this is an offset from uninitialized memory. Since 0xcccccccc means uninitialized in the VC debug mode. http://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations — drescherjm, Mar 20 '13 at 18:57
Do you NULL all 1000 pointers in table[]? It seems like you do not since you do not check for that. Wait a min shouldn't temp = table[hash]; be table[hash]=temp; — drescherjm, Mar 20 '13 at 18:58
Can you include your class constructor in the posted code above please? Then, add `table` to the initializer list, specifically, `hashTable::hashTable() : table()`. Also, check the `temp` you just received from the table *prior* to dereferencing it with `temp->next`. For all you know there was nothing there prior and it is not a valid address. — WhozCraig, Mar 20 '13 at 19:01

WhozCraig · Accepted Answer · 2013-03-20T19:35:54.800

You're likely not doing two things. First make sure your hash table is properly initialized to contain all-NULL-pointers. Secondly, make sure any pointer retrieved from the hash table is valid prior to dereferencing it:

For the first issue:

hashTable::hashTable() : table()
{
}

Also, you want to make sure this thing cleans up properly

hashTable::~hashTable()
{
    for (size_t i=0;i<sizeof(table)/sizeof(table[0]); ++i)
    {
        node *temp = table[i];
        while (temp)
        {
            node *victim = temp;
            temp = temp->next;
            delete victim;
        }
    }
}

For the second issue:

void addNode(const char *name, const char *numb)
{
    int hash = h(g(name));    //The hash of the key (name) used to check nodes
    node *temp = table[hash]; //sets the temporary node to the first node of the list

    if (temp)
    {
        // preexisting entry. walk that list looking for matching key.
        node **pp = &temp->next;
        while (temp)
        {
            if (0 == strcmp(temp->name, name))
                break;
            pp = &temp->next;
            temp = temp->next;
        }

        // link to last node if not found in list
        if (!temp)
            *pp = new node(name, numb);
    }
    else
    {   // no prior entry. create a new one and store it at table[hash].
        table[hash] = new node(name, numb);
    }
}

Note: the above code assumes the node class is implemented as

struct node
{
    char name[40];
    char numb[12];
    node * next;

    node(const char* name_, const char *numb_)
        : next()
    {
        strncpy(name, name_, sizeof(name)/sizeof(name[0])-1);
        name[ sizeof(name)/sizeof(name[0])-1 ] = 0;
        strncpy(numb, numb_, sizeof(numb)/sizeof(numb[0])-1);
        numb[ sizeof(numb)/sizeof(numb[0])-1 ] = 0;
    }
};

Personally, I'd use std::string

This seems more likely than my guess. As a result temp = new node; makes no sense in this case. — drescherjm, Mar 20 '13 at 19:08
Thank you very much for the detailed answer. It's starting to make sense now. :) — DatapawWolf, Mar 20 '13 at 19:48
Erhm, one last thing. Using the code to initialize the pointers to NULL, this "if (temp)" is now never false, when I use the same exact entry more than once. — DatapawWolf, Mar 20 '13 at 20:26
@KevSana It will be false the *first* time a slot is mapped and collision list exists yet. After that, the initial node in each slot added is always the first node of that slot's collection list. That is the point of a collision list to begin with. By the way, you can make this significantly faster if you sort the collection list as well, but that would change the layout of your hash table, requiring a array pointer and list size per slot. If speed were the end-goal, it is worth considering. — WhozCraig, Mar 20 '13 at 21:19

score 0 · Answer 2 · answered Mar 20 '13 at 18:56

0

If the value of hash is greater than (or equal to) 1000, temp will point to an invalid area.

And you are leaking the memory allocated by new node since you are overwriting the temp variable.

answered Mar 20 '13 at 18:56

Akobold

936
8
25

C++ Access Violation With Hash Tables and Linked Lists

2 Answers2