0

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;
}
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. ;-)

| improve this answer | |
  • The seed values have different effects. Some values tend to produce lots of collisions while others tend to minimize them. At this point, I'll let you research it on google. Just search for hash functions and let the authors explain it. They can probably do a better job than me. Also, for that line of code, you could/should work your way through it and figure out exactly what each part does. It'll be good for you! Here's a part though. % MAX_TABLE assures that the number is within the limits of the size of the table array. – Cliff B Jun 30 at 3:31
  • When you say seed values makes a hash function generate more unique hashes I get lost. Do you mean that if theres a collision in one hash table it will generate more hashes for that table to prevent a collision by making the matching values different? I hope that makes sense. Also, the line I was wondering about in the loop was the ``` hash = ((hash << 4) + (int)(*str)) % MAX_TABLE; ``` I have no idea what is going on here. Also I am unsure what to do with the int that hash returns since I can't understand this hash function or any others i've looked at. Also does my load function look ok? – ayeeitsalpha Jun 30 at 3:34
  • Sorry the last comment I added was incomplete and posted accidentally, I have been googling the hash function and that is how I got more confused. I started off thinking I understood them until the google search. I get you need the values to index into the hash table but I cannot figure out how. I saw the % used to make sure it is within the limits when I did the google search but it didn't make sense to me or explain how it does that. So in that line I know << is a bitwise left shift but idk what that is or what (int)(*str) is doing. I will google some more but the more I find the less I know – ayeeitsalpha Jun 30 at 3:45
  • SEED VALUE: This is all about the number generated, and minimizing the number of collisions, not handling collisions that occur. As I said, certain seeds can cause the hash function to produce the same hash for lots of different inputs, while other seeds will produce far more hash numbers given the same input data sets. Sometimes, a hash seed, sometimes called a salt, is used to vary the hash results on purpose. The coder may want to use hash values different from a standard value. In cryptography, a different seed or salt may be used to encrypt every char. Lots of reasons to change seeds. – Cliff B Jun 30 at 3:57
  • Think about how % works. When you modulo x % y, the result is the remainder of an integer division is given. That also means that the result cannot possibly be larger than y-1. Now, if y is the size of the table array, the hash must be between 0 and the size of the array - 1. – Cliff B Jun 30 at 3:57
1

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.

| improve this answer | |
  • Ok that makes more sense, I figured I was doing something wrong there and just realized this is in the notes for lecture 4. So for the hash function I wouldn't need to use seed values since I will be chaining the collisions? Also I am still confused on the hash = ((hash << 4) + (int)(*str)) % MAX_TABLE; line. Im sure MAX_TABLE is the hash table and that this line is creating the unique hashes but I don't really understand what is going on? I also don't undestand why they declared the variable c. Is it for assigning the int hash returns to an int variable like Cliff said? – ayeeitsalpha Jul 1 at 3:21
0
// 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.

| improve this answer | |

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .