Unhandled exception when trying to delete an item in a hashtable

[rlake]

Hello,

I am getting the following error message in my function to delete a value from a hashtable with chaining using a linked list:

Unhandled exception throw: read access violation
link->next was 0XCDCDCDCD

This is the code for the function:

void MyChain::deleteItem(int val)
{
int location = (val & arraySize);
nodeType *next = nullptr;
nodeType *link = hashtable[location];
nodeType *prev = nullptr;

//if there are no items in the list or the value in the node doesn't match the value being searched for

if (link == NULL || link->info !=val)
{
cout << "No element found for that value." << endl;
}

//while the list is not empty
while (link->next !=NULL)
{
if (link->info == val) //if the item to be deleted is found
{
link->next = link->next->next; //set the link to the following link
delete link;
}
else
{
prev=link;
link = link->next;
}
}
}

The debugger says the following:
link 0x00a5f140 {info=51 link = 0x00000000<NULL> next=0xcdcdcdcd{info=??? link=??? next=???}}
link->info 51
link->next 0xcdcdcdcd{info=??? link=??? next=???}
this 0x008ff778{next=0x00000000<NULL> arraySize=100 hashtable=0x008ff780{0x00000000<NULL>,0x00000000<NULL>,...}}
val 51

Doing research, it appears this message has to do with uninitialized heap memory; for example, interpreting uninitialized heap memory as a pointer, trying to dereference the pointer, etc., but I can't figure out where the problem lies.

Any suggestions on what to look for are appreciated.

Thanks,

Ragan

[Peter87]

int location = (val & arraySize);

I don't think this line is doing what you expect.

[rlake]

It's my hash function. It is working elsewhere in the code; for example, in my insert and print functions. What appears to be wrong with it?

[Peter87]

& is the bitwise AND operator. It gives a value that has a bit set to 1 if the bits at the same location in the two arguments are also 1. This is not a very good hash function because many of the locations could never be used by any value. 100 is 1100100 in binary so you are only really using three bits giving you 2³ (8) possible locations (0, 4, 32, 36, 64, 68, 96, 100). The biggest problem with this is that the location could be equal to the arraySize which is one too big to be used as an index in the hashtable array.

I suspect what you really intended to use was the modulo operator (%).

Another problem is when removing the value from the linked list.
link->next = link->next->next;
This will remove the node that comes after the one you found. Also note that link->next->next is not allowed if link->next is a null pointer. Maybe this is the place where you planned to use the prev variable?

[rlake]

Thanks.

The & was a typo in the question I posted. The actual code uses the modulo % operator.

I fixed the problem with the link->next=link->-next->next; It now reads next=link->next;

The delete function now runs without generating an error message; however, when I run my print function after deleting an item, I get a read access violation with the pointer I use to traverse the linked list (current). The print function runs just fine before I delete an item. Here is the code for that:

void MyChain::print() const
{

int counter = 0;
for (int i = 0; i < arraySize; i++)
{
nodeType *current = hashtable[i];
while (current != NULL)
{

cout << "Position [" << i << "]";
cout << current->info << " " << endl;
current = current->link;
counter++;
}

}
}

Thanks.

[cire]

I fixed the problem with the link->next=link->-next->next; It now reads next=link->next;

Then you've replaced your problem with another. Did you also see Peter87's suggestion that you may want to use the prev variable there?