CS50 good hash function for PSET5 Speller

Question

I was looking up different hash functions and was getting really confused following what the code was doing. I stumbled upon this hash function:

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

At first I was unsure what was going on but someone explained to me that

1. 401 is a seed value (unsure if i'll need one),
2. int c is unused and probably unnecessary,
3. ((hash << 4) shifts binary values 4 digits to the left (unsure why this was done),
4. +(int)(*str) adds the integer value of the character at the pointer position to hash, (which I don't really understand)
5. and that %MAX_TABLE returns the value from hash modulo table size to make sure you have an index value that is within the bounds of the table size.

The seed value I still do not fully understand as well as the line hash = ((hash <<4) + (int)(*str)) %MAX_TABLE. I think it is the look throwing me off (reading it like a math equation) if anyone can ellaborate I would appreciate it.

Also, would this be a good function to use if I utilize toupper/tolower? The person I reached out to said

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.

Answer 1

I'll take a run at explaining it. This is a very popular hash function for this pset and other uses.

1. It uses a seed value because changing the starting hash value, the seed value, has an effect on how many or how few hash collisions (different inputs producing the same hash as output) occur. For example, using a large prime number may produce less collisions than a small even number, or two numbers that are only different by 1 can produce entirely different distributions of hash values. (This example is only to demonstrate a concept.)
2. agreed
3. This is a very fast, highly efficient way to multiply by 16. << 4 is a 4 bit (NOT BYTE) shift to the left, that backfills from the right with 0 bits.
4. This is adding the int value of the next char to the running total
5. and the final modulo operation guarantees that you get a number between 0 and some limit - 1. In this case, the limit is the number of elements in table[].

Using the % MAX twice may be unnecessary. Either way will work.

Regarding the drawback, part of the assignment's program spec says that any given word should produce the same hash result no matter what letters are upper or lower case. "CaT" and "cat" should produce the same result. Since the hash function uses different ASCII values for upper and lower cases of the same letter, the program code needs to deal with case insensitivy, either in the load and check functions or directly in the hash function. (The latter would be the better practice.)

Does this answer your questions?

If it does, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)