0

It looks I have broken C while working on Pset5, I mean, I don't understand a bit why this happens.

First, I completed the problem with the simplest of hash functions which just processes the first letter, and returns an idnex based on the first letter of the word. Then, I wanted to speed it up as its running time was about 0,55 - 0,7 seconds.

I updated the hash function so that it processes the first 2 letters of the word, and returns an index between 0-676 please find it below:

int hashthis(char* word)
{
  int result;
  char sLetter=0;
  char fLetter = word[0];
  fLetter = tolower(fLetter);
  if(word[1])
  {
    sLetter = word[1];
    sLetter = tolower(sLetter);
    if(sLetter=='\'')
    sLetter=0;
    result = (fLetter-97)*26+(sLetter-96);
  }
  else
    result = fLetter-97;
  return result;
}

In my dictionary.c file, I set a constant of WIDTH to 677 and created an array of buckets as below:

#define WIDTH 677
node* hashtable[WIDTH]; 

So, after running the speller, my code gives a segmentation fault within load function. (just after opening dictionary file, and fp is not null)

 FILE* fp=fopen(dictionary,"r");
    if(!fp)
    {
        fprintf(stderr,"Cannot load dictionary file for reading\n");
        return false;
    }

    //Scan each word in dictionary file
    while(fscanf(fp, "%s",word)!=EOF)
    [...]

Now comes the trickiest parts,

  1. If I create a global variable at the top, like "int whatthehell=0" the program will proceed through this step successfully without any problem even though that variable is not used in the program but will give a segmentation fault in speller.c this time, while closing texts file (I didn't touch speller.c) (Actually all the operation is completed just could not close the file)

    // close text
    fclose(fp);
    
  2. If I comment out the fclose(fp) line, the program will finish successfully, no errors at all and total processing time is between 0,10 - 0,20 which is an improvement when compared to my initial hash function.

  3. My first (and more simple) hash function doesn't give any error in any of these parts, the only difference is that the size of WIDTH constant is 26 while using it.

Can anyone help me understand why I am having the problem?

1

Looks like you're writing to some place you were not supposed to, overwriting your other variables on the stack.

Your hash function might not respect the range of 0-676 you specified. Input like the empty string "", or "'", or "a'", would have negative output.

I used another simple type of hash function, which went like this

int hashthis (char* word)
{
    int prime = 101;
    int hashvalue = 0;
    for (int i = 0, len = strlen(word); i < len; i++)
    {
        hashvalue *= prime;
        hashvalue += tolower(word[i]);
        hashvalue %= WIDTH;
    }
    return hashvalue;
}

For every character, it would multiply the prior hash value with a prime, add the (lowercased) new character's value, and bring it back into range 0..WIDTH-1. It probably does not need to be a prime number, just co-prime to WIDTH (not have common prime factors). Worked well for me, though bitshift << and >> together with bitwise XOR ^ are probably more fancy. Important part is that the output range is limited and cannot be left, unlike your hash function, which might get arbitrary results for non-standard inputs.

Also, it's entirely possible that you have unmasked a bug at another place, caused by that bigger range.

5
  • spaces are handled by speller.c, so they are not forwarded into my hash function. And for the aphostrophe, you are right but I handled it with an if condition and tested, doesn't return negative values. I'll test with your function to compare, thank you :) btw, what is your hashes output range? 0-676? – devwanderer Feb 9 '17 at 12:06
  • Range is 0..WIDTH-1, whatever you set WIDTH to. Not sure what you mean by "spaces are handled by speller.c", I don't think I mentioned spaces anywhere. Have you tried the test cases I suggested, empty string, single apostrophe, or "a" followed by apostrohe? Are those results really in range? – Blauelf Feb 9 '17 at 13:30
  • You are right, I checked with more words and it looks I am still having problem with ' symbol sometimes. I will check different WIDTH values to see which one gives a better result. Thank you very much. – devwanderer Feb 9 '17 at 13:35
  • Used 6779 as WIDTH with the hash function you provided and the speed increased about %40 in average (when compared to 677 with the same function). – devwanderer Feb 9 '17 at 13:49
  • Double the size of your hash map, and if your hash function does well, you'll halve the time needed for traversing the linked list. Other parts (like insertion, if done right) are not affected by the size change, that's why you don't get double speed. – Blauelf Feb 9 '17 at 14:44

You must log in to answer this question.

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