Why should we mod a hash value by the size of the hash table?

Question

Week 7 Short on Hash Table provides the following suggested hash function:

int hash_function (char* key)
{
    // hash on first letter of string
    int hash = toupper(key[0]) - 'A' ;
    return hash % SIZE;
}

The first line of the function returns an integer between 26 and 0, because you are subtracting 'A' or 65 from a ASCII value between 90 (for Z) and 65 (for A). The next line says to return the remainder of the "hash" value (0 to 26) divided by SIZE.

SIZE is the size of the hash table. The CS50 study site says: "Modding by the size of the hash table is a good way to avoid indexing into a hash table slot that does not exist." if your hash table is 500 in size. What does dividing a hash value of 0 to 26 by 500 do for you?

Answer 1

It's actually not suggested. It's just an example on a hash function. They, however, expect something a little bit more complicated than this if you chose to implement a hash table for pset6.

Another thing is that

toupper(key[0]) - 'A'

doesn't really get evaluated to a value in [0, 26], but rather, it gets evaluated to a value in [0, 25] assuming key[0] is an alphabetical character.

Lastly, mathematically, when you take the remainder of dividing an integer a by an integer b, the result is in [0, b - 1].

Given an array of size SIZE, the indexes of this array's elements start from 0 up to SIZE - 1. That explains why you guarantee to get an index within the array boundaries when you take the remainder of dividing by SIZE.

Answer 2

Nothing. You only need to use modulo if your hash can be a value larger than your size. In that example, it's unnecessary.