0

I have been working on the speller problem in pset5 for a while now, and I am not able to figure out the problem in my hash function:

unsigned int hash(const char* word)
{
    int M = 1000000001;
    int P = 31;
    int hash_value = 0;
    int p_pow = 1;

    int len = strlen(word);

    for (int i = 0; i < len; i++)
    {
        hash_value = (hash_value + (word[i] - 'a' + 1) * p_pow) % M;
        p_pow = (p_pow * P) % M;
    }
    return hash_value;
}

Source : https://cp-algorithms.com/string/string-hashing.html

If I run my program with this hash function, following errors come on doing check50

:) dictionary.c, dictionary.h, and Makefile exist
:) speller compiles
:( handles most basic words properly
     expected "MISSPELLED WOR...", not ""
:) handles min length (1-char) words
:( handles max length (45-char) words
     expected "MISSPELLED WOR...", not ""
:( handles words with apostrophes properly
     expected "MISSPELLED WOR...", not "MISSPELLED WOR..."
:) spell-checking is case-insensitive
:( handles substrings properly
     expected "MISSPELLED WOR...", not ""
:| program is free of memory errors
     can't check until a frown turns upside down

Whereas if I use any other hash function, such as:

unsigned int hash(const char* word)
{
        unsigned int hash_value = 0;
        for (int i = 0, n = strlen(word); i < n; i++)
        {
             hash_value = (hash_value << 2) ^ word[i];
        }
        return hash_value % N; //N is size of hashtable
}

The program compiles correctly with everything green.
Since both the hash functions should work fine, I am confused why the first one is not working properly.

Any help would be kindly appreciated.

  • hi I used this hash function (the simple one) however get the error message error: invalid operands to binary expression ('unsigned int (const char *)' and 'int') – Ak500 May 26 at 20:14
  • @Ak500, I am not exactly sure where the error is coming from, but try casting word[i] into an integer, i. e. try (int)word[i] instead of word[i] in line 4 inside the for loop. – Shrey Tripathi May 27 at 5:21
  • it came in the last line of code the hash % N part so I changed it to hash_value % N which compiles .... would this work too? – Ak500 May 27 at 10:39
  • @Ak500, Oh, yeah. That's fine, too. I overlooked that part ! – Shrey Tripathi May 27 at 12:16
  • ok...thanks for the hash function and help! – Ak500 May 27 at 14:11
0

Just use the one that works that simple. The reason we were told to just get hash functions from the internet is because hash functions are hard to make, so most probably the design of the function that works, works better in this situation than the other one.

| improve this answer | |
0

can i ask what value ur N was?

| improve this answer | |
  • My N was 65536. – Shrey Tripathi May 28 at 10:10
  • thanks a lot, you saved me – Cedrigo Darwin Jun 5 at 7:02
  • I would like to understand your hash function better, may I ask why did you choose 65536? – Giacomo Belleri Aug 24 at 20:05

You must log in to answer this question.

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