How the String hash function works (2)

int hash = 0;
for (int i = 0; i < length(); i++) {
  hash = 32 * hash + charAt(i);
}
return hash;

Note that this is a arguably bad hash function for strings¹ (and possibly for most things). The problem is that we are multiplying by a power of 2, which in effect simply shifts the current hash along. Some mixing then does take place: the high bits of the ith character will be mixed with the lower bits of the previous character (now shifted left 5 places so that its lower 3 bits coincide with the upper 3 bits of the ith character). However, this isn't enough to completely remove the pattern of biases from the resulting hash code. The problem can be illustrated if we take random series of 5 characters (with the distribution we've been discussing). The graph to the right shows the probability of each successive bit of the hash code being set.

The graph still has characteristic "humps" where the bits with high probability in the original characters making up the hash code don't get enough chance to interact with more randomly distributed bits. (Although the "hump" does now span a width of 1 bit rather than 2 in the original distribution.)

Improving the multiplier

Now we plot the same graph using 31 as the multiplier, as in the Java implementation of the String hash code function. Multiplying by 31 effectively means that we are shifting the hash by 5 places but then subtracting the original unshifted value:

int hash = 0;
for (int i = 0; i < length(); i++) {
  hash = (hash << 5) - hash + charAt(i);
}
return hash;

There are now further interaction among the bits. Firstly, adding the ith character and subtracting the hash (with the previous character in its lower bits) brings the per-bit probabilities in the character closer to 50%. (For example, if we have two bits, each with a probability of 70% of being set, then subtracting one from the other leaves a probability of 42% that the resulting bit will be set, with a 21% chance of there being a carry from the bit to the left.) And now, rather than just combining the high bits of the ith number with the low bits of the previous character, there are interactions generally between the lower bits of the nth character and the higher bits of the n-1th character.