Insert function for Hash Table keeps hanging

[kingkush]

I cant seem to figure out why my hash table's insert function keeps hanging. I know its this portion because it started to hang after i tweaked this portion of the code.

  void HashTable::Insert(string key)
{
    int code = HashCode(key) % tableSize;
    cout << "Key '" << key << "' hashes to " << code << endl;
    /// TO DO:
    /// Add a new node to the bucket with the index code
    /// Step 1: Create a new node
    /// Step 2: Locate the position for inserting the node
    /// Step 3: Attach the new node to the structure. Also, DO remember to
    //increase the number of the elements
    HashNode *newHashNode = new HashNode;
    newHashNode -> data = key;
    
    //Traverse pointer made to point at first linked list
    HashNode *traversePtr = new HashNode;
    traversePtr = table[code].next;
    
    //whle pointer doesnt reach end of bucket
    while(traversePtr != nullptr)
    {
        traversePtr = traversePtr -> next;
    }
    //if(table[code].next == nullptr || traversePtr == nullptr)
    //{
        table[code].next = newHashNode;
        numElements++;
    //}
}

When attempting to debug I get this error(line 5):

libsystem_kernel.dylib`__write_nocancel:
    0x7fffd160850c <+0>:  movl   $0x200018d, %eax          ; imm = 0x200018D 
    0x7fffd1608511 <+5>:  movq   %rcx, %r10
    0x7fffd1608514 <+8>:  syscall 
->  0x7fffd1608516 <+10>: jae    0x7fffd1608520            ; <+20>
    0x7fffd1608518 <+12>: movq   %rax, %rdi
    0x7fffd160851b <+15>: jmp    0x7fffd1600d6f            ; cerror_nocancel
    0x7fffd1608520 <+20>: retq   
    0x7fffd1608521 <+21>: nop    
    0x7fffd1608522 <+22>: nop    
    0x7fffd1608523 <+23>: nop   

[Peter87]

Does the HashNode constructor initialize the next pointer to nullptr?

The function has a memory leak because you allocate a new node object on line 15 that is never deallocated.

[kingkush]

It did not point to nullptr but when i changed it i got the same problem. I also deleted traversePtr in the function (placed at last line) but now i get: Thread 1:EXC_BAD_ACCESS in line 21. But that error rarely occurs. The program still stalls after displaying "Key 'horse' hashes to 4" so i know its inserting everything but once the insert is done then it appears to hang, or thats what it seems to me

[cire]

The program still stalls after displaying "Key 'horse' hashes to 4" so i know its inserting everything but once the insert is done then it appears to hang, or thats what it seems to me

That message occurs after Insert is called, but before anything is actually inserted. It seems likely, given your code, that the linked list that comprises your bucket has an invariant that is violated (i.e. the list is not properly terminated with a null pointer.)

[kingkush]

I think i found the error. I changed my while loop to:
while(traversePtr -> next != nullptr)

Now i consistently get the bad exc code

[cire]

Now i consistently get the bad exc code

Doing another thing wrong doesn't mean you've "found the error." It means you're doing another thing wrong.

[kingkush]

I said "I think Ive found the error" not " I Found the error". Maybe giving another hint instead of throwing shade would be more helpful.

If anyone would still like to help Ive gotten my program to run but now im stuck in an infinite loop inside my print statement and it appears as if nothing got added to the bucket. I thought it was a missing nullPtr but i cant seem to find where.

void HashTable::Insert(string key)
{
    int code = HashCode(key) % tableSize;
    cout << "Key '" << key << "' hashes to " << code << endl;
    /// TO DO:
    /// Add a new node to the bucket with the index code
    /// Step 1: Create a new node
    /// Step 2: Locate the position for inserting the node
    /// Step 3: Attach the new node to the structure. Also, DO remember to
    //increase the number of the elements
    HashNode *newHashNode = new HashNode;
    newHashNode -> data = key;
    newHashNode -> next = nullptr;
    
    //Traverse pointer made to point at first linked list
    HashNode *traversePtr = new HashNode;
    traversePtr = nullptr;
    traversePtr = &table[code];
    
    if(table[code].next == nullptr)
    {
        table[code].next = newHashNode;
    }
    else
    {
        //while pointer doesnt reach end of bucket
        while(traversePtr -> next != nullptr)
        {
            traversePtr = traversePtr -> next;
        }
    }
    traversePtr -> next = newHashNode;
    numElements++;
    delete newHashNode;
}

[Peter87]

I think this is your problem.

delete newHashNode;

You don't want to delete the node you have just inserted.

[kingkush]

Whoops i meant to delete traversePtr Thank you for catching that! but i am still getting the loop error.

This is the code it keeps looping in:

while(table -> next != nullptr)
            {
                cout << "INSIDE PRINT" << endl;
                cout << table -> data << endl;
            }

Does this mean newHashNode -> next != nullPtr despite setting it in line 13?

[cire]

This is the code it keeps looping in:

That code occurs nowhere in the code you've posted thus far, and suggests that table has a different type here than it does elsewhere. You could help yourself by showing a complete, compilable sample of code that reproduces the issue(s) you're having, rather than asking people to guess.

[kingkush]

I already stated: infinite loop inside my print statement(i meant function) and I posted this in the very beginning: I know its this portion because it started to hang after i tweaked this portion of the code.

So we're clear: The program runs perfectly fine without the insert function. Once the insert function is implemented and then print function is called the program continues to only print "inside print" forever.

#include <iostream>
#include <vector>
using namespace std;
const int INITIAL_SIZE = 11;
//****************
//HashNode Struct*
//****************
struct HashNode
{
    string data;
    HashNode * next = nullptr;
};
//Variables
const int HASH_SEED = 5381;
const int HASH_MULTIPLIER = 33;
const int HASH_MASK = unsigned(-1) >> 1;
//******************
//HashCode Function*
//******************
int HashCode(string str)
{
    unsigned hash = HASH_SEED;
    int n = str.length();
    for (int i = 0; i < n; i++)
    {
        hash = HASH_MULTIPLIER * hash + str[i];
    }
    return int(hash & HASH_MASK);
}
//****************
//HashTable Class*
//****************
class HashTable
{
private:
    HashNode * table; /// dynamically allocated array of pointers to nodes
    int tableSize; /// should be a prime number
    int numElements;
public:
    HashTable();
    void Insert(string key);
    void Remove(string key);
    bool Find(string key);
    void Display();
};
//**********************
//HashTable Constructor*
//**********************
HashTable::HashTable()
{
    tableSize = INITIAL_SIZE;
    table = new HashNode[tableSize];
    numElements = 0;
    /// TO DO:
    /// Set all elements to NULL
    for(int i = 0; i < tableSize; i++)
    {
        table[i].next = nullptr;
    }
}
//***************************
//HashTable-Display Function*
//***************************
void HashTable::Display()
{
    for(int i = 0; i < tableSize; i++)
    {
        if(table -> next == nullptr)
        {
            i++;
        }
        else
        {

            while(table -> next != nullptr)
            {
                cout << "INSIDE PRINT" << endl;
                cout << table -> data << endl;
            }
            i++;
        }
    }
}
//**************************
//HashTable-Insert Function*
//**************************
void HashTable::Insert(string key)
{
    int code = HashCode(key) % tableSize;
    cout << "Key '" << key << "' hashes to " << code << endl;
    /// TO DO:
    /// Add a new node to the bucket with the index code
    /// Step 1: Create a new node
    /// Step 2: Locate the position for inserting the node
    /// Step 3: Attach the new node to the structure. Also, DO remember to
    //increase the number of the elements
    HashNode *newHashNode = new HashNode;
    newHashNode -> data = key;
    newHashNode -> next = nullptr;
    
    //Traverse pointer made to point at first linked list
    HashNode *traversePtr = new HashNode;
    traversePtr = nullptr;
    traversePtr = &table[code];
    
    if(table[code].next == nullptr)
    {
        table[code].next = newHashNode;
    }
    else
    {
        //while pointer doesnt reach end of bucket
        while(traversePtr -> next != nullptr)
        {
            traversePtr = traversePtr -> next;
        }
    }
    traversePtr -> next = newHashNode;
    numElements++;
    //delete traversePtr;
}
//**************************
//HashTable-Remove Function*
//**************************
void HashTable::Remove(string key)
{
    int code = HashCode(key) % tableSize;
    cout << "Trying to remove key '" << key << "' at index " << code << endl;
    /// TO DO:
    /// Search the linked list, and remove the match element
    
}
//bool HashTable::Find(string key)
//{
//    int code = HashCode(key) % tableSize;
//    cout << "Looking for key '" << key << "' at index " << code << endl;
    /// TO DO:
    /// Search through the linked list and return true if the key is found. Otherwise,
    //return false.
//}

int main()
{
    HashTable animals;
    animals.Insert("cat");
    animals.Insert("fish");
    animals.Insert("elephant");
    animals.Insert("tiger");
    animals.Insert("panda");
    animals.Insert("otter");
    animals.Insert("horse");
    animals.Display();
    /// tiger should be found this time
    //if (animals.Find("tiger"))
    //    cout << "tiger is found" << endl;
    //else
    //    cout << "tiger is NOT found" << endl;
    animals.Remove("tiger");
    animals.Display();
    /// tiger should NOT be found since it has been removed
    //if (animals.Find("tiger"))
    //    cout << "tiger is found" << endl;
    //else
    //    cout << "tiger is NOT found" << endl;
    return 0;
}

[cire]

You should probably begin by revisiting the data members of your data structure. A hash table is typically an array of linked lists, not an array of nodes.

Your comment "/// dynamically allocated array of pointers to nodes" is not accurate. table is a dynamically allocated array of nodes, but you should have an array of pointers to nodes.

Made a couple changes to reflect this:

class HashTable
{
private:
    HashNode** table;  // dynamically allocated array of pointers to nodes.
    int tableSize; /// should be a prime number
    int numElements;
// ...
};

//**********************
//HashTable Constructor*
//**********************
HashTable::HashTable() 
   : table(new HashNode*[INITIAL_SIZE]), tableSize(INITIAL_SIZE), numElements(0)
{
    for (int i = 0; i < tableSize; i++)
        table[i] = nullptr;
}

//***************************
//HashTable-Display Function*
//***************************
void HashTable::Display()
{
    for (int i = 0; i < tableSize; ++i) {    // for each bucket in the table        
        HashNode* node = table[i];

        if (node) { std::cout << "Bucket " << i << '\n'; }

        while (node) {
            std::cout << '\t' << node->data << '\n';
            node = node->next;
        }
    }
}

//**************************
//HashTable-Insert Function*
//**************************
void HashTable::Insert(string key)
{
    int code = HashCode(key) % tableSize;
    cout << "Key '" << key << "' hashes to " << code << endl;

    // create a new node and insert at front of bucket.
    HashNode* node = new HashNode{ key, table[code] };

    table[code] = node;
    ++numElements;
}
// ... 

[kingkush]

Now i am a little confused. My professor provided some of the code like the HashTable class so I am unsure if he wants me to do it this way or if theres another way he wants it to be done.

And also I am not sure what you mean with this line of code. : table(new HashNode*[INITIAL_SIZE]), tableSize(INITIAL_SIZE), numElements(0)

Thank You for your feed back! I will start implementing what you have shown me

[cire]

And also I am not sure what you mean with this line of code. : table(new HashNode*[INITIAL_SIZE]), tableSize(INITIAL_SIZE), numElements(0)

In C++, this is the standard way to initialize members of a struct or class in a constructor.

Consider this (silly) type:

struct string_wrapper{
    std::string _w;

    string_wrapper();
};

With this constructor implementation:

string_wrapper::string_wrapper() {
    _w = "default";
}

_w is first initialized to an empty string, then assigned the value "default".

With this constructor implementation:

string_wrapper::string_wrapper() : _w("default") {
}

_w is initialized with the value "default".

As you may deduce, more work is done in the first constructor than in the second for the same end result.

Possibly useful link:
http://stackoverflow.com/questions/926752/why-should-i-prefer-to-use-member-initialization-list