6.2 Multiply by a large prime number

One thing is right about the shift-add method: we need to do something about the sum before adding the next ASCII code. However, instead of multiplying by 2, we can consider multiplying by a larger number.

Instead of just multiplying a large number, we can select a large prime number p as the multiplier. As long as MAX_ENTRIES is not a multiple of p, the hash function scatters key values fairly evenly. Choosing 7907 as p, raw sums become 593045024 and 401034833, and the hash values become 32 and 81 for Kat Auyeung and Tak Auyeung, respectively.

Note that even with a prime number as a multiplier, the hash function is not injective (one-to-one). In other words, it is still possible to map two key values to the same integer, even if the capacity of the hash table is much better than the number of values to store.

One potential problem with this method is that strings that differ only by the last letter, such as "Tammi" versus "Tammy", are clustered closely. This is why some approaches has an additional and different multiplier for the letter (before adding to the sum).

The source of this version of the hash function is intentionally missing.