Take the 2-minute tour ×




Why is 31 used as a multiplier?


share|improve this question
Compare also stackoverflow.com/questions/1835976/… - I think 31 is a bad choice if you write your own hashCode functions. –  hstoerr May 19 '10 at 14:50

8 Answers 8

up vote 166 down vote accepted

According to Joshua Bloch's Effective Java (a book that can't be recommended enough, and which I bought thanks to continual mentions on stackoverflow):

The value 31 was chosen because it is an odd prime. If it were even and the multiplication overflowed, information would be lost, as multiplication by 2 is equivalent to shifting. The advantage of using a prime is less clear, but it is traditional. A nice property of 31 is that the multiplication can be replaced by a shift and a subtraction for better performance: 31 * i == (i << 5) - i. Modern VMs do this sort of optimization automatically.

(from Chapter 3, Item 9: Always override hashcode when you override equals, page 48)

share|improve this answer
Well all primes are odd, except 2. Just sayin. –  Kip Nov 18 '08 at 20:15
I don't think Bloch is saying it was chosen because it was an odd prime, but because it was odd AND because it was prime (AND because it can easily be optimized into a shift/subtract). –  matt b Nov 18 '08 at 20:48
31 was chosen coz it is an odd prime??? That doesnt make any sense - I say 31 was chosen because it gave the best distribution - check computinglife.wordpress.com/2008/11/20/… –  computinglife Nov 20 '08 at 20:00
I think the choice of 31 is rather unfortunate. Sure, it might save a few CPU cycles on old machines, but you have hash collisions already on short ascii strings like "@ and #! , or Ca and DB . This does not happen if you choose, for instance, 1327144003, or at least 524287 which also allows bitshift: 524287 * i == i << 19 - i. –  hstoerr Nov 30 '09 at 13:43
@Jason See my answer stackoverflow.com/questions/1835976/… . My point is: you get much less collisions if you use a larger prime, and lose nothing these days. The problem is worse if you use non-english languages with common non-ascii chars. And 31 served as a bad example for many programmers when writing their own hashCode functions. –  hstoerr May 12 '10 at 7:42

On (mostly) old processors, multiplying by 31 can be relatively cheap. On an ARM, for instance, it is only one instruction:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

Most other processors would require a separate shift and subtract instruction. However, if your multiplier is slow this is still a win. Modern processors tend to have fast multipliers so it doesn't make much difference, so long as 32 goes on the correct side.

It's not a great hash algorithm, but it's good enough and better than the 1.0 code (and very much better than the 1.0 spec!).

share|improve this answer
Funny enough, the multiplication with 31 is on my desktop machine actually a little bit slower than multiplication with, say, 92821. I guess the compiler tries to "optimize" it into shift and add as well. :-) –  hstoerr May 11 '10 at 6:54
I don't think I've ever used an ARM which was not equally fast with all values in the range +/-255. Use of a power of 2 minus one has the unfortunate effect that a matching change to two values changes the hash code by a power of two. A value of -31 would have been better, and I would think something like -83 (64+16+2+1) might have been better yet (blenderize bits somewhat better). –  supercat Mar 27 '14 at 22:02
@supercat Not convinced by the minus. Seems you'd be heading back towards zeros. / String.hashCode predates the StrongARM which, IIRC, introduced an 8-bit multiplier and possibly increased to two cycles for the combined arithmetic/logical with shift operations. –  Tom Hawtin - tackline Mar 28 '14 at 11:27
@TomHawtin-tackline: Using 31, the hash of four values would be 29791*a + 961*b + 31*c + d; using -31, it would be -29791*a + 961*b - 31*c + d. I don't think the difference would be significant if the four items are independent, but if pairs of adjacent items match, the resulting hash code will be the contribution of all unpaired items, plus some multiple of 32 (from the paired ones). For strings it may not matter too much, but if one is writing a general-purpose method for hashing aggregations, the situation where adjacent items match will be disproportionately common. –  supercat Mar 28 '14 at 16:30
The situation isn't quite so bad as the one resulting by taking the xor of items which are supposed to be unsequenced (as opposed to using an arithmetic sum). If one has an UnorderedPair where A and B things are "equal" if (a.first.equals(b.first) && a.second.equals(b.second)) || ((a.first.equals(b.second) && a.second.equals(b.first)), using a hash of first.hashCode()+second.hashCode() will lose one bit of information if first and second match; using first.hashCode() ^ second.hashCode() (which I've seen done) would lose all 32 bits of information. –  supercat Mar 28 '14 at 16:34

As Goodrich and Tamassia point out, If you take over 50,000 English words (formed as the union of the word lists provided in two variants of Unix), using the constants 31, 33, 37, 39, and 41 will produce less than 7 collisions in each case. Knowing this, it should come as no surprise that many Java implementations choose one of these constants.

Coincidentally, I was in the middle of reading the section "polynomial hash codes" when I saw this question.

share|improve this answer
Note however that you might get WAY more collisions if you use any kind of international charset with common characters outside the ASCII range. At least, I checked this for 31 and German. So I think the choice of 31 is broken. –  hstoerr May 11 '10 at 6:58

By multiplying, bits are shifted to the left. This uses more of the available space of hash codes, reducing collisions.

By not using a power of two, the lower-order, rightmost bits are populated as well, to be mixed with the next piece of data going into the hash.

The expression n * 31 is equivalent to (n << 5) - n.

share|improve this answer

Neil Coffey explains why 31 is used under Ironing out the bias.

Basically using 31 gives you a more even set-bit probability distribution for the hash function.

share|improve this answer
excellent link! –  Dinesh Babu Aug 15 '14 at 14:17

Actually, 37 would work pretty well! z := 37 * x can be computed as y := x + 8 * x; z := x + 4 * y. Both steps correspond to one LEA x86 instructions, so this is extremely fast.

In fact, multiplication with the even-larger prime 73 could be done at the same speed by setting y := x + 8 * x; z := x + 8 * y.

Using 37 or 73 (instead of 31) might be better, because it leads to denser code: The two LEA instructions only take 6 bytes vs. the 7 bytes for move+shift+subtract for the multiplication by 31. One possible caveat is that the 3-argument LEA instructions (used here) became slower on Intel's Sandy bridge architecture, with an increased latency of 3 cycles.

share|improve this answer
Are you a pascal programmer or something? what's with the := stuff ? –  Mainguy May 16 '12 at 17:00
@Mainguy It's actually ALGOL syntax and is used fairly often in pseudo-code. –  Tutti Frutti Jacuzzi Dec 27 '13 at 3:53
but in ARM assembly multiplication by 31 can be done in a single instruction –  Lưu Vĩnh Phúc Apr 21 at 8:26
@Mainguy In pseudo code what does := mean? –  Lưu Vĩnh Phúc Apr 21 at 8:52

I'm not sure, but I would guess they tested some sample of prime numbers and found that 31 gave the best distribution over some sample of possible Strings.

share|improve this answer

Bloch doesn't quite go into this, but the rationale I've always heard/believed is that this is basic algebra. Hashes boil down to multiplication and modulus operations, which means that you never want to use numbers with common factors if you can help it. In other words, relatively prime numbers provide an even distribution of answers.

The numbers that make up using a hash are typically:

  • modulus of the data type you put it into (2^32 or 2^64)
  • modulus of the bucket count in your hashtable (varies. In java used to be prime, now 2^n)
  • multiply or shift by a magic number in your mixing function
  • The input value

You really only get to control a couple of these values, so a little extra care is due.

share|improve this answer

protected by sᴜʀᴇsʜ ᴀᴛᴛᴀ Aug 27 '13 at 13:36


Would you like to answer one of these unanswered questions instead?
