0

I found this great hash function. But I noticed something very weird during pset5. When I am testing my program by putting the outputs of my program and the staff solution into student.txt and staff.txt, and then use the diff -y student.txt staff.txt I noticed that it says all 16 letter words are misspelled, even if they are in /dictionaries/large. Almost 100% positive it isn't coming from my code. At the REF site, there is a description of how it works, but I think I am missing something more fundamental.

Why are 16 letter words showing up as misspelled when they are not?

//Ref: https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/
int hash(const char *word)
{
    unsigned int hashy=0;
    for (int i=0, n=strlen(word); i<n; i++)
    {
        hashy = (hashy<<2)^word[i];
        hashy %= HASHTABLESIZE;
    }
return hashy;
}

Part of the output looks like:

opposers                                                        opposers
disqualification                                              <
asperities                                                      asperities
disputants                                                      disputants
indiscriminately                                              <
concealments                                                    concealments
intemperances                                                   intemperances
WORDS MISSPELLED:     971                 WORDS MISSPELLED:     935
WORDS IN DICTIONARY:  143091              WORDS IN DICTIONARY:  143091
WORDS IN TEXT:        196784              WORDS IN TEXT:        196784
0
1

I'm getting this same bug even though I used a different hash function. not sure what this problem is. The rest of my program works perfectly. Here's my hash function:

 // Source of hash function: stackoverflow.com/questions/14409466/simple-hash-functions

unsigned int hash(const char* word)
{
    unsigned int count;
    unsigned int hashValue = 0;
    for(count = 0; word[count] != '\0'; count++)
        hashValue = word[count] + (hashValue << 6) + (hashValue << 15) - hashValue;

    return (hashValue % SIZE);
}
2
  • That's so weird that it's happening to you as well. I think it has to do with the Bitwise operators. But I can't explain it, yet. – Scott M Anderson Aug 23 '17 at 19:48
  • I removed the bitwise operators and replaced them with '*'. Still an issue. Also it took forever to run. – Scott M Anderson Aug 23 '17 at 19:59
1

I do not know why exactly this was an issue(only 16 letter words?), but the problem was in Check(). My variable for copying the constant char was set up as:

char editword[strlen(word)];

it should have been:

char editword[strlen(word)+1]; 

This fix fixed the 16 letter misspelling bug

2
  • When the compiler allocates space on the stack for your editword array, it may be allocated on a 16-byte aligned boundary. This means that the 17th byte is probably being used by another variable, which then "steps" on your null char, causing any string functions (such as strlen) to be unreliable. Smaller words wouldn't exhibit the problem since the last byte may not be allocated to any other variable. – curiouskiwi Aug 24 '17 at 0:55
  • yes this fixes my problem as well. Thanks! – wenyi pan Aug 24 '17 at 1:56
-1

Don't modulo hashy in the loop. That actually breaks it.

This is how the hash from that thread should be (I posted it)

int hash(const char *word)
{
    unsigned int hashy=0;
    for (int i=0, n=strlen(word); i<n; i++)
    {
        hashy = (hashy<<2)^word[i];
    }
    return hashy % HASHTABLESIZE;
}
2
  • Hi, thanks for helping out so quickly. However that didn't solve it either. Exact same result as before. The file I am checking is the federalist.txt. – Scott M Anderson Aug 23 '17 at 14:00
  • Well, your hash function will be many times faster now anyway. I just ran federalist.txt using it and it works fine, so I'd suggest investigating elsewhere (perhaps your check?) If you'd like to post it, I'll review it. – curiouskiwi Aug 23 '17 at 19:56

You must log in to answer this question.

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