PSET 5 Hash help

Question

I started my load function without looking at any reference code (first time starting a pset this way) to give me an idea on how to implement my own version. I was mostly confident until I reached the hash function inside of load. I couldn't figure out what to do exactly so I thought i'd move onto the hash function and come back to hash in load when I figured how to implement the function but I quickly got confused while researching hash. I found this example:

int hash(const char * str) {
    int hash = 401;
    int c;

    while (*str != '\0') {
        hash = ((hash << 4) + (int)(*str)) % MAX_TABLE;
        str++;
    }

    return hash % MAX_TABLE;
}

which was the easiest to follow for me but I am not sure where the 401 came from or what was going on in the brackets of the while loop. At this point I am not even sure I started the load function right. I know I still need to free the memory I allocated and finish the hash portion but I was hoping someone can look it over and tell me if I have made any errors, and see if that'll help me figure out how to start the hash function. I left notes and queston on my code for myself as well as in case I had to ask others, here is my code:

bool load(const char *dictionary)
{
    // TODO
    fopen(dictionary);
    {
        //Unsure if this works, may switch to if (load == false)
        if ((fopen(dictionary) == NULL)
        {
            return false;
        }
        //Unsure if I can use the condition like this
        for(int i = 0; return = 0; i++)
        {
            fscanf(dictionary, "%s", word)
            {
                  int feof(*dictionary, dictionary);
                  {
                      //originally checked to see if feof was null then returned 0 until eof reached
                      while(!feof(dictionary))
                      {
                          //originally had char *word = malloc(sizeof (char)), do I need a new struct for new nodes?
                          //Or do I need to change the name of the word pointer to differentiate from the original char word in
                          //the node struct?
                          node *word = malloc(sizeof (node));
                          //originally had list as malloc, changed to list when reviewing notes,
                          //unsure if "if(malloc == NULL)"" would work
                          if (list == NULL)
                          {
                              return false;
                          }
                          strcpy(node, word);
                          return 0;
                      }
                      //Unsure how to implement this part yet
                      hash(word)
                      {
                          node-> index
                      }
                  }
            }
        }
    }
    return true;
}

Answer 1

Let's talk about how you're using the hash function first. Here's your code:

        hash(word)

Ignoring the missing semicolon, this is a normal function call. Since hash() returns an int, the code needs to do something with that int, like assigning it to an int var. Surely you know how to do that by now.

As for the hash function itself, it's using some uncommon but normal techniques.

The 401 is a seed value for the function. Different hash functions in the world use different seed functions or no seed at all. It's just the way they're written. Seed values are used to make a hash function generate more unique hashes, a larger range of them, or for other reasons.

The while statement is using the address of the string. Note that it's incremented inside the loop. This is similar to using an array index. It's just stepping through the string from char to char until it gets to the end of string marker, '\0'.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

Answer 2

You've got a few different problems. First, take a look at your first call to fopen(). You call it again to check if the result is NULL, but that's incorrect. Instead, try declaring a variable with the result of calling fopen():

FILE *ptr = fopen(dictionary, "r");

Then you can check with an if statement if ptr is equal to NULL.

As Cliff said earlier, the number 401 is used in this instance as a hash seed, which ensures that values returned from the hash function are unique.

Answer 3

// Hashes word to a number
unsigned int hash(const char *word)
{
    //creates a hash seed value of 401 then loops through the words until NUL
    int hash = 401;
    while (*word != '\0')
    {
        //shifts hash 4bits left (multiplies by 16)
        //takes the int value of the char and converts it to uppercase
        hash = ((hash << 4) + toupper((int)(*word))) % N;
        word++;
    }

    return hash;
}

New code updated from an explanation I received on reddit. In response to my last question for anyone who may need the same help, (int)(*str) is the x and MAX_TABLE (N from table[N] in my code) is the y but is not really doing anything besides keeping the remainder from hash within the boundaries. Basically %N (%MAX_TABLE) is not part of the equation but modifies the answer. I've quoted the reddit explanation below.

int hash = 401; - Sets the initial value of hash to 401.

int c; - Not used

while (*str != '\0') { - Iterate through the pointers of str. As long as it's not the null terminator, do the following.

hash = ((hash << 4) - Using bitwise operations move the binary values 4 digits to the left. This translates into turning 401 into 6416.

• (int)(*str)) - Add the integer value of the character at the pointer position to hash.

% MAX_TABLE; - Using modulo, assign the remainder from hash % the table size to hash.

str++; - Increment str so you're now doing the hash in the next letter in the dictionary or you reach the null terminator.

return hash % MAX_TABLE; - Return the value from hash modulo table size. This is to make sure you have an index value that is within the bounds of the table size.

The only drawback with this is that later on when you compare the words from the text to the dictionary, it will return more misspelled words. This is down to this part of the hash function, (int)(*str). The numeric value of 'A' is different to 'a' so if you're trying to compare Ant with ant it will come up with a different value and say that the word is misspelled so you need to add some way or lowering the case of each letter in your hash function before you add it's value to hash.