Choosing the Base for a Polynomial String Hash

This post is the formal companion to the string hashing discussion in my data structures course. In the course notes, we usually say that a string hash multiplies by a base and adds the next character. Here we slow down and ask what the base is doing, why 31 is such a common choice, and why "use a prime" is useful advice but not the whole story.

The prerequisites are modest. You should know what a hash table is, what a hash collision is, and what the remainder operation does. You should also be comfortable with binary numbers at the level of "multiplying by 2 shifts bits left." You do not need a discrete mathematics course. When we use words such as factor, prime, or relatively prime, I will explain them.

A hash table stores a value under a key by turning the key into an array index. For string keys, one common way to get that index is to fold the string down into a single integer, then reduce that integer to a slot.

The fold reads the characters one at a time. Each character has a numeric code ('A' is 65 in the usual encoding, 'B' is 66, and so on up the alphabet). Keep a running integer h, start it at 0, and for each character multiply h by a fixed number, the base, and add the character's code:

int h = 0;
for (int i = 0; i < s.length(); i++) {
  h = base * h + s.charAt(i);
}

At the end, h is the string's hash code. To turn it into a slot in an array of capacity slots, reduce it modulo capacity. Mathematically, that means choosing a number from 0 through capacity - 1 with the same remainder as h. In Java, % can be negative when h is negative, so real code has to correct for that or use a power-of-two mask. The mathematical idea is still "use the remainder to choose a slot."

This hash is called a polynomial hash because, if you expand the loop, the characters are weighted by powers of the base. For a three-character string with codes $c_{1}$ , $c_{2}$ , and $c_{3}$ , the loop computes

((c_{1}) b + c_{2}) b + c_{3} = c_{1} b^{2} + c_{2} b + c_{3},

where $b$ is the base.

The base can be any number bigger than 1. With a base of 1, multiplying does nothing, so the fold just adds the character codes. Then every rearrangement of the same characters gets the same hash, which is terrible for strings.

But not every base above 1 is a good choice. The most important practical rule is that the base should be odd. A second rule is that the base should avoid sharing factors with the table size; choosing a prime base is a common way to help with that, but it is not a magic requirement. We will look at both rules.

Why the base should be odd

Start with what multiplying does to the bits of h. Multiplying a binary number by 2 shifts every bit one place to the left and puts a 0 in the rightmost place. This is like multiplying a decimal number by 10: the digits shift left and a 0 appears at the end.

Multiplying by 4 shifts two places left and puts two 0s at the bottom. More generally, multiplying by an even number always puts a 0 in the lowest bit of the product, because every even number has a factor of 2.

That matters because many hash tables use a power-of-two capacity. If the table has 4 slots, the slot is determined by the last two bits of the hash. If the table has 8 slots, the slot is determined by the last three bits. In general, reducing modulo $2^{k}$ keeps only the lowest $k$ bits.

Take a base of 4 and a table of 4 slots. To keep the arithmetic short, use small character codes: A is 1, B is 2, and X is 3. Hash the two strings "AB" and "XB", which differ only in their first letter:

base 4:
 "AB":  h = 0; 4*0 + 1 = 1;  4*1 + 2 = 6    ->  6  mod 4 = 2
 "XB":  h = 0; 4*0 + 3 = 3;  4*3 + 2 = 14   ->  14 mod 4 = 2

Both land in slot 2. In fact, with base 4 and capacity 4, every two-character string that ends in B lands in slot 2, no matter what the first character is. The reason is that multiplying the first character by 4 makes it a multiple of 4, and multiples of 4 leave remainder 0 when divided by 4. So the first character disappears from the slot calculation.

The same problem happens more generally with even bases and power-of-two capacities. The repeated multiplications push earlier characters out of the low bits, and the low bits are exactly what a power-of-two table reads.

Now change the base to 5, an odd number, and keep everything else the same:

base 5:
 "AB":  h = 0; 5*0 + 1 = 1;  5*1 + 2 = 7    ->  7  mod 4 = 3
 "XB":  h = 0; 5*0 + 3 = 3;  5*3 + 2 = 17   ->  17 mod 4 = 1

The two strings land in different slots, 3 and 1. Since 5 mod 4 is the same as 1 mod 4, the first character still affects the final remainder.

That is the reason for the odd rule. An even base loses information in the low bits, especially when the table size is a power of two. An odd base does not automatically make the hash good, but it avoids this particular failure: earlier characters can still influence the low bits that choose the slot.

Why shared factors are dangerous

An odd base fixes the low-bit problem, but on its own it is not enough. A base can be odd and still line up badly with the table size.

A factor of a number is a number that divides it evenly. For example, 5 is a factor of 10. Two numbers are relatively prime if they share no factor bigger than 1. For example, 3 and 10 are relatively prime, but 5 and 10 are not.

The trouble appears when the base and the capacity share a factor. Take a table of 10 slots and a base of 5. Five is odd, but it shares the factor 5 with 10.

Hash a two-letter string with character codes $c_{1}$ and $c_{2}$ . The hash is

5 c_{1} + c_{2},

and the slot is

(5 c_{1} + c_{2}) mod 10.

Focus on the first character's contribution:

5 c_{1} mod 10.

If $c_{1}$ is even, $5 c_{1}$ is a multiple of 10, so the contribution is 0. If $c_{1}$ is odd, $5 c_{1}$ leaves remainder 5. Those are the only two possibilities. So the first character can shift the slot by only 0 or 5; it cannot help spread keys across all ten slots.

Change the base to 3, which shares no factor with 10. Now

3 c_{1} mod 10

runs through

3, 6, 9, 2, 5, 8, 1, 4, 7, 0

as $c_{1}$ runs from 1 through 10. It reaches every possible remainder. The first character can now move the hash anywhere in the table.

That is the real rule: the base should not share factors with the capacity. If the base and capacity are relatively prime, multiplication by the base does not trap a character's contribution inside a smaller set of slots. If they share a factor, some contributions get trapped.

So does the base need to be prime?

A prime number is a number greater than 1 whose only positive factors are 1 and itself. Examples are 3, 5, 31, and 16777619. Composite numbers, such as 4, 10, and 33, have additional factors.

Choosing a prime base is a useful habit because a prime has very few factors. A prime base can share a factor with the capacity only when the capacity is a multiple of that prime. That is less likely than with a composite base.

But "prime" is not the exact requirement. The exact requirement is about the relationship between the base and the table size.

If the capacity is a power of two, then every odd base is relatively prime to the capacity. In that setting, 31, 33, and 37 all avoid the shared-factor problem because none of them has a factor of 2. This is one reason DJB2 can use 33 even though 33 is not prime.

If the capacity is a prime number, then almost any smaller base is relatively prime to it. The base itself does not need to be prime; it just needs not to be a multiple of the capacity.

So the careful version is:

The base should be odd, especially for power-of-two table sizes.
The base should be relatively prime to the table sizes you use.
Choosing a prime base is a common way to reduce shared-factor problems, but it is a heuristic, not a proof that the hash is best.

The bases real hashes use

Java's String.hashCode() uses a base of 31:

h = 31 * h + c;

The number 31 has several useful properties. It is odd, so it avoids the low-bit failure. It is prime, so it has very few shared-factor risks. It is also one less than 32, and 32 is $2^{5}$ , so

31 h = 32 h - h = (h ≪ 5) - h .

That means a multiply by 31 can be implemented as a left shift by five bits followed by a subtraction. This mattered more on older processors, where a general multiplication was relatively expensive, but the tradition remains.

For a long string, the running value grows past what a 32-bit int can hold and wraps around, sometimes becoming negative. Java integer arithmetic is deterministic, so the same string still gets the same hash code every time. The hash code is not meant to preserve the original number; it is meant to produce a repeatable, well-spread integer.

DJB2, by Dan Bernstein, uses a base of 33 and usually starts h at 5381 instead of 0. The base 33 is odd, but it is not prime:

33 = 3 \cdot 11.

It is still popular because it is fast and has tested well on many ordinary string sets:

33 h = 32 h + h = (h ≪ 5) + h .

This is a useful reminder that "prime" is not an absolute law. DJB2 follows the odd rule and performs well in practice despite using a composite base.

FNV-1a is another well-known string and byte hash. In its 32-bit version, it starts from the offset basis 2166136261; for each byte, it XORs the byte into the hash and then multiplies by the FNV prime 16777619:

h = h xor byte
h = h * 16777619

Here the multiplier is odd and prime, and it was chosen for good bit behavior under repeated multiplication and XOR.

The specific numbers 31, 33, 5381, 16777619, and 2166136261 do not fall out of one simple formula. They come from a mix of arithmetic properties, speed, and testing on real data. A hash constant survives because it spreads typical keys well, not because one theorem declares it perfect.

A note on the table size

The base and the table size interact, so one more point is worth making.

If the capacity is a power of two, reducing modulo the capacity keeps only the low bits of h. Dividing by $2^{k}$ leaves the last $k$ bits. This is fast because it can be done with a bit mask instead of a division. The cost is that all the responsibility falls on the low bits. An even base is especially bad here because it repeatedly clears or weakens those low bits.

If the capacity is prime, the modulo operation depends on more of the whole integer instead of only the lowest bits. That can forgive some weaker low-bit behavior, but division by an arbitrary prime is usually slower than a bit mask.

Java's HashMap takes the first road. It uses power-of-two capacities for speed, then applies an extra spreading step to the key's hash code so that some high-bit information is mixed down into the low bits before the slot is chosen.

So the practical answer is:

Use an odd base.
Avoid sharing factors with the table sizes you use.
Treat prime bases as a good tradition, not a magic shield.
Trust testing over numerology when choosing exact constants.

That is why 31, 33, and large FNV primes can all make sense in their own contexts. The base is not good by itself; it is good because it works well with the update rule, the table size, the slot calculation, and the kinds of keys you expect to store.