implementation of hash table

Question

I have been having trouble with the implementation of the hash table and linked lists. I don't know if I am on the right track or not, but I think my main problem is not knowing how to automate the creation of the list. I tried counting each word, but that takes too long and seems pointless because I could use an array instead.

bool load(const char* dictionary)
{
FILE* fp = fopen(dictionary, "r");

//hash table
node* hashtable[26];
int hashvalue;

// adding words to linked lists
while (!feof(fp))
{
    node* new_node = malloc(sizeof(node));
    fscanf(fp, "%s", new_node->word);
    hashvalue = new_node->word[0] - 97;
    if (hashtable[hashvalue]->next == NULL)
        hashtable[hashvalue]->next = new_node;
    else
        new_node->next = new_node;
}
return false;

}

Answer 1

Assuming you're reading the word correctly into new_node -> word and looking at the insertion part of your code

if (hashtable[hashvalue]->next == NULL)
    hashtable[hashvalue]->next = new_node;
else
    new_node->next = new_node;

there's a few things that I want to point out here.

First, if hashtable[hashvalue] is equal to NULL, there won't be hashtable[hashvalue] -> next. So trying to initialize hashtable[hashvalue] -> next with new_node might get you into troubles.

Second, what's the point of initializing new_node -> next with new_node? I see no point at all and besides, you're never inserting new_node into the hash table.

How to fix that?
There are two main approaches here.

1. keeping the list sorted.
2. inserting at the beginning of the list.

Keeping the list sorted:
the first insertion into each linked-list should be treated a little bit differently and separately. The pseudocode for this might be like that

if the list at hashtable[hashvalue] is empty
{
    set new_node -> next to NULL
    set hashtable[hashvalue] to new_node
}

This is actually the harder approach because if the list is not empty, we have to look for the correct position of the node, insert it and update the pointers.

Let's visualize this first. Given this linked-list

[1] ==> [2] ==> [4]

If we're willing to insert [3] into this list, we first traverse through the list comparing values to find the correct position of this new node. Obviously it's between the [2] and the [4]. By finding the correct position for this new node, we achieved 1 of 3.

Let's proceed to step 2 (i.e., insert it at this location)! This is done at the visual level only

[1] ==> [2] ==========> [4]
                [3]

and lastly, let's update the pointers (done on 2 steps)!

step 1 of 2:

[1] ==> [2] ==========> [4]
                [3] ==>

step 2 of 2:

[1] ==> [2] ==> [3] ==> [4]

These steps must be done in this specific order. If you reversed this order, you'll lose the pointers to the node(s) next to it.

Notice that the scenario we demonstrated here is the one that we insert our new node in the middle of two nodes. There are 2 other scenarios

1. insert at the beginning of the list (new_node -> word comes before all the words in the list in the dictionary).
2. insert at the end of the list (new_node -> word comes after all the words in the list in the dictionary).

To compare strings, take a look at strcmp(). Run

man strcmp

in the terminal for more information!

Now, let's do this on the level of pseudocode (continuing the previous piece of pseudocode)

else
{
    create a pointer to a node named previous and set it to NULL
    create a pointer to a node named current and set it to hashtable[hashvalue]

    // traverse through the list
    while (current is not NULL and current -> word is greater than new_node -> word)
    {
        set previous to current
        set current to current -> next
    }

    // as we exit this loop, the position of our node is between previous and current

    // the three scenarios

    set new_node -> next to current

    // insert at the beginning
    if previous is NULL
    {
        set hashtable[hashvalue] to new_node
    }
    // insert in the middle or at the end
    else 
    {   
        set previous -> next to new_node
    }
}

Inserting at the beginning of the list
This is the easier approach where we don't care of the list being sorted. The idea here is to always insert our new node at the beginning of the list. The pseudocode for this might be something like this

new_node -> next = hashtable[hashvalue]
hashtable[hashvalue] = new_node

yes, it's as simple as this :)

Hope that helps!

---

Update:

If new_node is a pointer to another node, where would I declare that node?

Well, new_node is a pointer to a node. This node is stored at the memory address returned by malloc() when the following statement (from your code) executes

node *new_node = malloc(sizeof(node));

This basically tells the computer that we want to reserve a block of memory to store a node. And we'll point to that block of memory using the variable named new_node.

Also, could you explain more of your comment?

Sure! Consider the following piece of code

node *ptr0;

// executes anyway
if (true)
{
    // allocate memory for a new node and point to it by ptr0
    node *ptr1 = malloc(sizeof(node));
    // point to the previously allocated memory with ptr1
    ptr0 = ptr1;
}

What I did here is that I created a pointer to a node (ptr0), I entered the body of the if statement, I created another pointer to a node (ptr1) and I allocated memory for the node it will point to and lastly, I set ptr0 to ptr1.

Guess what happens after we leave the body of the if statement?! ptr1 goes out of scope (it's not longer available for us to use).

But what about the node it points to? Luckily, the node still exists (since we stored in on the heap) and we still have access to it using the other pointer (ptr0) which we'd declared before the if statement and set it to point to the same block of memory that was pointed to by ptr1 (when we did ptr0 = ptr1;). So ptr0 stays in scope for a while after the if statement.

What does this have to do with your question? Well, when we read a new word from the dictionary, we create a temporary node to store this word in (i.e., new_node). As we insert this node, we set one of the nodes of one of our linked-lists to new_node for example

hashtable[hashvalue] = new_node;

or

previous -> next = new_node;

Then as we hit the closing brace of the loop, new_node itself goes out of scope (it no longer exists), but the node still exists and we still have access to it (Remember why?)

In the next iteration of the loop, we, again, declare a new pointer to a node named new_node and repeat the process.

Hope that explains it! :)

Answer 2

Kareem, after combing through your answer in the updated part, I think it should be

*// traverse through the list

while (current is not NULL and current -> word is less than than new_node -> word)*

instead of greater than as you said. If it is greater than, current-> word would be 'b' for example, while new_node is 'a'. But then the current pointer would move past to the next node via:

set current to current -> next

while the pointer named previous would move to 'b' and it would try to insert 'a' after 'b'. Can you or someone confirm this?