1

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.

4

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

5
  • I have a question about this, which I guess applies to hash functions in general: How do you know that this hash function will produce an even distribution of outputs regardless of the hash table size? I suppose since the function outputs an int, the output can't go higher than 2.1 billion (32 bit int limit)? I guess it also depends on the inputs, but if I am passing in words that are never more than 45 chars long, and want to experiment with a hash table that has 200k buckets, how do I know that the hash function outputs don't start maxing out at, say, 100k, given 45 char inputs? – Matt R. Oct 23 '20 at 2:21
  • This is a very good question! There are extensive analyses on hash functions and result distributions that you can google. It's way beyond answering here. It really comes down to how deep the tree is - how many linked lists are there at or near a maximum value, vs. how much memory is being used. Ideally, every word would have a unique hash value. As a practical matter, there will be some with the same hash. The trick is to get linked list lengths minimized. The law of diminishing returns comes in here. Is the amount of time spent hashing worth the more even distribution? (Hint: it is.) – Cliff B Oct 23 '20 at 2:35
  • As a practical matter for this exercise, getting the length of the longest linked list down into single digits is the goal. Getting below 3 gets interesting. The easiest way is to keep increasing the number of buckets. Eventually, large increases in the number of buckets doesn't move the needle much though. You might try writing a function to count the length of each bucket and tallying the number of buckets of each length, then sort the list and print the number of buckets with the longest length, then the next longest, etc. This might help you analyze it and enlighten you on this question. – Cliff B Oct 23 '20 at 2:42
  • BTW, the reason to do all this is to increase execution speed. Another aspect is this. While decreasing execution time for check, you could be increasing time for load. – Cliff B Oct 23 '20 at 2:43
  • Thanks @Cliff B for the thorough answers!! – Matt R. Oct 24 '20 at 4:33

You must log in to answer this question.

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