# Logic Behind a Basic Hash Table Hashing Algorithm

I am trying to write a Hash Table in Java based on some Princeton article about it.

The most commonly used method for hashing integers is called modular hashing: we choose the array size M to be prime, and, for any positive integer key k, compute the remainder when dividing k by M. This function is very easy to compute (k % M, in Java), and is effective in dispersing the keys evenly between 0 and M-1

This part makes sense - whatever the number, the modulo of the Hash Table size will give some array index within that range.

Strings. Modular hashing works for long keys such as strings, too: we simply treat them as huge integers. For example, the code below computes a modular hash function for a String s, where R is a small prime integer (Java uses 31).

Then a code example is provided, which I don't get.

``````int hash = 0;
for (int i = 0; i < s.length(); i++)
hash = (R * hash + s.charAt(i)) % M;
``````

I refactored it as:

``````int someSmallPrimeInteger = 31;
int hash = 0;
for (int i = 0; i < key.length(); i++) {
int unicodeCharAsInt = Character.getNumericValue(key.charAt(i));
hash = (someSmallPrimeInteger * hash + unicodeCharAsInt) % hashTableCapacity;*
``````

1. Why the loop? Why not just convert each char to its unicode value and add it up?
3. Why does it need to be prime?
4. `(someSmallPrimeInteger * hash + unicodeCharAsInt)` Why this at all? What's the significant of this function?

I understand this so poorly, I can't even phrase questions intelligently, even though it's so little code.

• This is a common hash function for strings, and e.g. used by Java with `someSmallPrimeInteger = 31`. Good hash functions have various mathematical properties, such that every output hash is equally likely for the expected input distribution. Addition alone doesn't do that (for the same reason that the sum of throwing two six-sided dice will likely be around 7, i.e. twice the mean dice value). Addition is also commutative, i.e. order doesn't matter.
– amon
Jul 3, 2018 at 8:39
• @amon Thank you for the reply, but I understand the vague idea and that it's used by Java (the article I linked says that). What I am looking for is the rationale behind the details.
– VSO
Jul 3, 2018 at 13:17
• Prime sized hash tables were considered obsolete in the early 1990s... strange article, very old advice. Jul 4, 2018 at 16:42