HashTable Remove Function crashes program

[kingkush]

I have two functions find and remove implemented for a linked list and they work fine. However I'm using the linked list to solve collisions for my hashtable and these two functions are causing me issues. Neither one can find the key or it fails to delete. We can focus on remove and based on taht i should be able to solve find.

It sometimes works with no issues, but it sometimes fails and crashes the program which is confusing me a lot.

Remove Function HashTable:

int HashTable::remove(std::string key)
{
    for(int i = 0; i < size; i++)
    {
        std::cout << "Check bucket: " << i << std::endl;
        int removed = List->remove(key);
        if(removed == 0)
        {
            std::cout << "Removal Successful" << std::endl;
            return 0;
        }
    }
    return -1;
}

Remove Function LinkesList:

int DynamicList::remove(std::string key)
{
    if(head == nullptr)
    {
        std::cout << "No List to remove from!" << std::endl;
        return -1;
    }
    else
    {
        Node* cur = head;
        Node* previousNode = nullptr;
        while(cur->next != nullptr && cur->key != key)
        {
            previousNode = cur;
            cur = cur->next;
            if(cur->next == nullptr && cur->key != key)
            {
                std::cout << key << " Not Found!" << std::endl;
                return -1;
            }
        }
        if (cur == head)
        {
            head = cur->next;
            delete cur;
            return 0;
        }
        previousNode->next = cur->next;
        delete cur;
        return 0;
    }
    return -1;
}

It appears as if head = nullPtr some of the time when i attempt to remove a value and it fails. The find and remove function both only work periodically. If one fails the other might still work. Anyone have any ideas what could be causing this? I'm at a loss

[Thomas1965]

http://www.cprogramming.com/debugging/debugging_strategy.html
http://www.unknownroad.com/rtfm/gdbtut/
http://web.eecs.umich.edu/~sugih/pointers/summary.html
http://www.thegeekstuff.com/2010/03/debug-c-program-using-gdb
https://msdn.microsoft.com/en-us/library/sc65sadd.aspx

[kingkush]

I've attempted to debug it several times but for some reason head points to nullPtr every once in awhile causing my code to function incorrectly and I cant figure out why especially since that same function works fine as a linked list.

[Thomas1965]

If you post the complete code maybe someone can spot the problem.

[kingkush]

Theres a lot of code. but but this is where the problem is occurring. For some reason the program keeps thinking head is nullPtr even after an insert. This is the only function I'm using that manipulates head.

[kingkush]

any ideas?

[Thomas1965]

If you think that the problem is in the insert function then set a break point in the first line, step through your code and see if the variables have the value you expect.

[kingkush]

Thats my issue. They do sometimes work. Ive used the function giving me an error with no issues but when i use it with my hash table it begins to function erratically every now and then.

Basically the only way i can get an issue is if my hashtable functions are causing it but none of them mess with the head pointer.

I posted additional code but no one replied so i removed it.

[Thomas1965]

I would write a separate program to test the list class. If the list works properly then you know that the problem is in the hash table.

BTW. For testing I can recommend the doctest framework:
https://www.codeproject.com/Articles/1156938/doctest-the-lightest-Cplusplus-unit-testing-framew

[kingkush]

I have. The list class was from a previous assignment. It worked perfectly fine but once implemented into this new hashtable class im getting all these work run time bugs. Ill check out the link tho!

[dhayden]

HashTable::remove() doesn't look right. YOu shouldn't try to remove the item from each bucket. Instead, you should hash the item to figure out which bucket it will appear in.

Now look at line 12 in DynamicList:remove(). If cur->next ==nullptr then you'll exit, regardless of whether or not you actually found the node to delete. So the code starting at line 22 will delete the last node in the list if the key isn't found. Combine this with the fact that you're calling remove() on each list in the hash table and you end up deleting a whole lot of items.

The code should be something like this (untested):

int DynamicList::remove(std::string key)
{
    Node* previousNode = nullptr;
    Node *cur;
    for (cur = head; cur != nullptr; previousNode=cur, cur = cur->next) {
        if (cur->key == key) {
            if (cur == head) {
                head = cur->next;
            } else {
                previousNode->next = cur->next;
            }
            delete cur;
            return 0;
        }
    }
    return -1;              // not found
}

The code can be simplified by changing previousNode. Instead of keeping a pointer to the previous node that's nullptr when you're looking at the head, keep a pointer to the pointer to the current node. So this points to head itself, or the next pointer of the previous node:

int DynamicList::remove(std::string key)
{
    Node *cur;

    for (Node **headOrNext = &head; cur = *headOrNext; headOrNext = &cur->next) {
        if (cur->key == key) {
            *headOrNext = cur->next;
            delete cur;
            return 0;
        }
    }
    return -1;
}

[kingkush]

It does make more sense to use the hash function to determine where to delete it but shouldnt my method still work? Just a slower algorithm since it has to traverse every bucket until it hits the first match?

Also in line 12 it checks to see if the key doesnt match either so wouldnt that work?

Your method does look better and cleaner though. I am curious why my implementation only works part of the time. Shouldnt it fail every time if line 12 made it exit?

[Thomas1965]

Why don't you show us the complete code of the list class?
The problem would probably easier to spot when we can run it in a debugger.

[kingkush]

Since the assignment is already past its due date i will post my entire code. I didnt want my solution (Or more accurately whatever function work) available for anyone to copy in my class with a simple google search.

HashTable Class:

#include "DynamicList.hpp"

class HashTable
{
private:
    DynamicList* List;
    int size;
    //Private Method
    int hash(std::string key);
public:
    HashTable(int s);
    ~HashTable();
    int insert(std::string key);
    int remove(std::string key);
    void print();
    void clear();
    bool find(std::string key);
    bool isFull();
    bool isEmpty();
};

//
//****************
//Private Methods*
//****************
//

//Hash: the hash function.  It accepts the key string and returns the hash value.
int HashTable::hash(std::string key)
{
    int hashValue;
    hashValue = rand() % size + 0;
    std::cout << key << std::endl;
    //std::cout << "HashValue: " << hashValue << std::endl;
    return (hashValue);
}

//
//***************
//Public Methods*
//***************
//

//Constructor: accepts an integer argument used to determine the number of elements in the hash table.  Dynamically allocates the hash table.
HashTable::HashTable(int s)
{
    size = s;
    List = new DynamicList[s];
    srand (time(NULL));
}

//Destructor: deallocates all dynamically allocated memory.
HashTable::~HashTable()
{
    List->clear();
    delete [] List;
}

//insert: insert's it's argument into the hash table.  calls the hash function to obtain an appropriate hash address.  Returns 0 if successful, -1 otherwise.
int HashTable::insert(std::string key)
{
    int index;
    index = hash(key);
    List[index].append(key);
    int numFound = List[index].find(key);
    if(numFound != -1)
    {
        std::cout << "Insert Successful" << std::endl;
        return 0;
    }
    else
    {
        std::cout << "Insert Failed HT" << std::endl;
        return -1;
    }
}

//remove: removes the first key matching it's argument from the hash table.  Returns 0 if successful, -1 otherwise.
int HashTable::remove(std::string key)
{
    for(int i = 0; i < size; i++)
    {
        std::cout << "Check bucket: " << i << std::endl;
        int removed = List->remove(key);
        if(removed == 0)
        {
            std::cout << "Removal Successful" << std::endl;
            return 0;
        }
        std::cout << "Unsuccessful removal" << std::endl;
    }
    std::cout << "Error in hash remove" << std::endl;
    return -1;
}

//find: returns true if a key matching it's argument is found, false otherwise.
bool HashTable::find(std::string key)
{
    for(int i = 0; i < size; i++)
    {
        int found = -666;
        found = List[i].find(key);
        if(found > 0)
        {
            std::cout << "Found!" << key << std::endl;
            return true;
        }
        else
        {
            std::cout << "Not Found" << std::endl;
            return false;
        }
    }
    return false;
}

//isFull: returns true if the structure is full, false otherwise
bool HashTable::isFull()
{
    if(List->isFull() == false)
    {
        return false;
    }
    else
    {
        std::cout << "List is Full" << std::endl;
        return true;
    }
}

//isEmpty: returns true if the structure has no keys, false otherwise.
bool HashTable::isEmpty()
{
    if(List->isEmpty() == true)
    {
        return true;
    }
    else
    {
        return false;
    }
}

//Clear: resets the object to it's initial state.
void HashTable::clear()
{
    for(int i = 0; i < size; i++)
    {
        std::cout << "Clear Bucket " << i << std::endl;
        List[i].clear();
    }
}

//Print: displays all the keys currently stored in the structure
void HashTable::print()
{
    for(int i = 0; i < size; i++)
    {
        std::cout << "BUCKET: " << i << std::endl;
        std::cout << "HEAD -> ";
        List[i].print();
        std::cout << std::endl;
    }
}

[kingkush]

LinkedList (DynamicList) Class:

#include <iostream>

class DynamicList
{
    struct Node
    {
        std::string key;
        Node* next;
    };
    //Pointer to head
    Node* head;
public:
    //constructor
    DynamicList();
    //Deconstructor
    ~DynamicList();
    void clear();
    int append(std::string key);
    int insert(std::string key);
    int remove(std::string key);
    int find(std::string key);
    int getLength();
    bool isFull();
    bool isEmpty();
    int peek(std::string &i);
    void print();
};

//
//**************
//Class Methods*
//**************
//

//Constructor: Sets head to nullPtr
DynamicList::DynamicList()
{
    head = nullptr;
}

//Destructor: Just call clear()
DynamicList::~DynamicList()
{
    clear();
}

//Clear:causes all memory to be freed up (Same as destructor, just call it)
void DynamicList::clear()
{
    {
        Node* cur = head;
        Node* deleteNext = nullptr;
        if(head == nullptr)
        {
            std::cout << "No List!" << std:: endl;
        }
        else
        {
            while(cur != nullptr)
            {
                deleteNext = cur->next;
                delete cur;
                cur = cur->next;
            }
            head = nullptr;
        }
    }
}

//Append: adds the value in parameter i to the end of the list.  Returns 0 if successful, -1 otherwise.
int DynamicList::append(std::string key)
{
    Node* newNode = new Node;
    newNode->key = key;
    newNode->next = nullptr;
    if(head == nullptr)
    {
        head = newNode;
        std::cout << "Successful First Insert!" << std::endl;
        if(head == newNode)
        return 0;
    }
    else
    {
        Node* cur = head;
        while(cur->next != nullptr)
        {
            cur = cur->next;
        }
        cur->next = newNode;
        //std::cout << "Success!" << std::endl;
        return 0;
    }
    std::cout << "Failure!" << std::endl;
    return 1;
}

//Insert:inserts the value in parameter i into the list, IN ASCENDING ORDER.  Returns 0 if successful, -1 otherwise.
int DynamicList::insert(std::string key)
{
    Node* newNode = new Node;
    newNode->key = key;
    newNode->next = nullptr;
    if(head == nullptr)
    {
        head = newNode;
        std::cout << "success! First Insert" << std::endl;
        return 0;
    }
    else
    {
        Node* cur = head;
        Node* previousNode = nullptr;
        while(cur != nullptr && newNode->key > cur->key)
        {
            previousNode = cur;
            cur = cur->next;
        }
        if(previousNode == nullptr)
        {
            head = newNode;
            newNode->next = cur;
            return 0;
        }
        else
        {
            previousNode->next = newNode;
            newNode->next = cur;
            return 0;
        }
    }
    return -1;
}

//getLength: returns length of list
int DynamicList::getLength()
{
    if(head == nullptr)
    {
        std::cout << "No List to Find from!" << std::endl;
        return 0;
    }
    else
    {
        Node* cur = head;
        int listLength = 0;
        while(cur != nullptr)
        {
            cur = cur->next;
            listLength++;
        }
        return listLength;
    }
}

//Find: returns the relative position of a node containing the value matching the value in parameter i if found in the list, -1 otherwise.  ( 0 for the first node, 1 for the second, 2 for the third, ... )
int DynamicList::find(std::string key)
{
    if(head == nullptr)
    {
        std::cout << "No List to Find from!" << std::endl;
        return -1;
    }
    else
    {
        Node* cur = head;
        int listLocation = 0;
        while(cur != nullptr && cur->key != key)
        {
            cur = cur->next;
            listLocation++;
            if(cur == nullptr)
            {
                std::cout << key << " Not Found!" << std::endl;
                return -1;
            }
        }
        return listLocation;
    }
}

//Remove: removes the first value found in the list matching the value in parameter i. Returns 0 if successful, -1 otherwise.
int DynamicList::remove(std::string key)
{
    if(head == nullptr)
    {
        std::cout << "No List to remove from!" << std::endl;
        return -1;
    }
    else
    {
        Node* cur = head;
        Node* previousNode = nullptr;
        while(cur->next != nullptr && cur->key != key)
        {
            previousNode = cur;
            cur = cur->next;
            if(cur->next == nullptr && cur->key != key)
            {
                std::cout << key << " Not Found! LinkedList Remove" << std::endl;
                return -1;
            }
        }
        if (cur == head)
        {
            std::cout << "first to remove LL" << std::endl;
            head = cur->next;
            delete cur;
            return 0;
        }
        std::cout << "PNode->next = cNode->next" << std::endl;
        previousNode->next = cur->next;
        delete cur;
        return 0;
    }
    std::cout << "Error in remove" << std::endl;
    return -1;
}

//isFull: returns true if the list is full, false otherwise.
bool DynamicList::isFull()
{
    Node* testDummy = new Node;
    if(testDummy)
    {
        std::cout << "Not Full" << std::endl;
        delete testDummy;
        return false;
    }
    else
    {
        std::cout << "Full" << std::endl;
        return true;
    }
}

//isEmpty: returns true if the list is empty, false otherwise.
bool DynamicList::isEmpty()
{
    if(head == nullptr)
    {
        std::cout << "Empty" << std::endl;
        return true;
    }
    else
    {
        std::cout << "Not Empty" << std::endl;
        return false;
    }
}

//peek: assigns the value at the front of the list to reference parameter i.  Returns 0 if successful, -1 otherwise.  Does not alter the list in any way.
int DynamicList::peek(std::string &i)
{
    Node* cur = head;
    cur->key = i;
    if (cur->key == i)
    {
        return 0;
    }
    else
    {
        return -1;
    }
}


//print: displays the values in the list on a single line, separated by spaces.
void DynamicList::print()
{
    Node* cur = head;
    if(head == nullptr)
    {
        std::cout << "Empty List!" << std::endl;
    }
    else
    {
        while(cur != nullptr)
        {
            std::cout << cur->key << " ";
            cur = cur->next;
        }
    }
    std::cout << std::endl;
}

[Thomas1965]

First bug I found in you clear function.

delete cur;
cur = cur->next;

Here is the begin of tests using doctest, link above.

#define DOCTEST_CONFIG_IMPLEMENT_WITH_MAIN
#include "DocTest/doctest.h"
#include "DynamicList.h"

TEST_CASE("Testing default constructor")
{
  DynamicList dl;
  CHECK(dl.isEmpty());
  CHECK(dl.getLength() == 0);
}

TEST_CASE("Testing single append")
{
  DynamicList dl;
  dl.append("Key 1");
  CHECK(!dl.isEmpty());
  CHECK(dl.getLength() == 1);
}

OUTPUT

[doctest] doctest version is "1.2.1"
[doctest] run with "--help" for options
Empty
No List to Find from!
No List!
Successful First Insert!
Not Empty
===============================================================================
dynamiclist\main.cpp(13)
TEST CASE:  Testing single append

TEST CASE FAILED!
crashed:
  SIGSEGV - Segmentation violation signal

===============================================================================
[doctest] test cases:      2 |      1 passed |      1 failed |      0 skipped
[doctest] assertions:      4 |      4 passed |      0 failed |
[doctest] Status: FAILURE!

[dhayden]

Also in line 12 it checks to see if the key doesn't match either so wouldn't that work?

No. Although you check for the end of the list at line 16, that doesn't help if there is exactly one item in the list. When there is one item, head != nullptr so it goes to line 12. Then cur->next == nullptr so it skips the while loop. Then it deletes the item in the list.

It would if your remove() function worked.

Regarding your later post of your full code:

Line 32: hashValue = rand() % size + 0;. You have a fundamental misunderstanding of what a hash function is. The idea of a hash function is that hashing the same key always generates the same hash value. Your hash function is generating a random number between 0 and size. The reason you want to generate the same hash value is that it leads you to a specific bucket where the item must be located.

Line 55: List->clear(); This clears one list. You need to clear them all. Just call clear() instead since that method clears all lists.

HashTable::find(). You should hash the key to lead you straight to the bucket where the item must be, if it's in the hash table. Again, this is the purpose for using a hash table: the hash function quickly leads you to the right bucket.

HashTable::isEmpty() and HashTable::isFull(): you're checking only the first bucket.

DynamicList::insert(): Are you sure that items should be inserted in sorted order? If the list should be sorted then you should remove the append() method. Usually singly linked lists are used when the order doesn't matter and you always insert at the head of the list because it's very fast.

DynamicList::isFull(): what determines if a list is full? You're testing whether the program runs out of memory.

[thmm]

I took a data structure class and it was very easy. Don't let people fool you. Its so easy i dont even go to class.

http://www.cplusplus.com/forum/beginner/220497/

Your code has more flaws than a Swiss cheese holes.
Maybe you should have gone to the class.

[kingkush]

@Learner My first difficulty with a HW assignment and its not even for my Data Structure class. If you could read you would see the key word TOOK. Since your english is poor that is past tense meaning it is not the present. Also you should have said

Your code has more holes than swiss cheese.

So go back to your english class and try to troll again.

@Thomas Thanks for the help. The doctest is really helpful!

@Dhayden I appreciate you help. The hash function was just temporary to get the rest of the program working. I see for the clear function i need to put it into a for loop to delete the rest of lists. Along with the is full and is empty. The insert function is just for the hashtable but i actually call the append function in my LinkedList class so its not in any particular order. And yes to determine if the list if full we are just checking to see if there is any memory left.

[dhayden]

The hash function was just temporary to get the rest of the program working.

Okay, but again, a hash function must return the same value each time it hashes the same string. The hash table won't work correctly otherwise. It appears that you worked around this in your remove() and find() methods by checking each bucket. If you want a simple hash function, just return the first character of the string (or 0 if it's empty)

i actually call the append function in my LinkedList class

The append function is horribly inefficient because it must traverse the entire list before it can insert the item. You should prepend the item (add it to the beginning of the list) instead.

Hash tables exist so you can quickly insert and find a data item based on its value. Your implementation doesn't contain these efficiencies.