203

I was just wondering why is that primes are used in a class's hashCode() method? For example, when using Eclipse to generate my hashCode() method there is always the prime number 31 used:

public int hashCode() {
     final int prime = 31;
     //...
}

References:

Here is a good primer on Hashcode and article on how hashing works that I found (C# but the concepts are transferrable): Eric Lippert's Guidelines and rules for GetHashCode()

Eric Lippert
  • 647,829
  • 179
  • 1,238
  • 2,067
Ian Dallas
  • 12,451
  • 19
  • 58
  • 82
  • 3
    related: [Why does Java's hashCode() in String use 31 as a multiplier?](http://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier/299748#299748) – matt b Sep 02 '10 at 01:50
  • This is more or less a duplicate of question http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus . – Dr. Hans-Peter Störr Aug 16 '12 at 07:35
  • 1
    Please check my answer at http://stackoverflow.com/questions/1145217/why-should-hash-functions-use-a-prime-number-modulus/20206663#20206663 It is related to the properties of polynomials over a field (not a ring!), hence prime numbers. – TT_ stands with Russia Nov 26 '13 at 01:08

9 Answers9

153

Prime numbers are chosen to best distribute data among hash buckets. If the distribution of inputs is random and evenly spread, then the choice of the hash code/modulus does not matter. It only has an impact when there is a certain pattern to the inputs.

This is often the case when dealing with memory locations. For example, all 32-bit integers are aligned to addresses divisible by 4. Check out the table below to visualize the effects of using a prime vs. non-prime modulus:

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

Notice the almost-perfect distribution when using a prime modulus vs. a non-prime modulus.

However, although the above example is largely contrived, the general principle is that when dealing with a pattern of inputs, using a prime number modulus will yield the best distribution.

advait
  • 6,355
  • 4
  • 29
  • 39
  • 26
    Aren't we talking about the multiplier used to generate the hash code, not the modulo used to sort those hash codes into buckets? – ILMTitan Aug 31 '10 at 21:50
  • 5
    Same principle. In terms of I/O, the hash feeds into the hash table's modulo operation. I think the point was that if you multiply by primes, you'll get more randomly distributed inputs to the point where the modulo won't even matter. Since the hash function picks up the slack of distributing the inputs better, making them less regular, they are less likely to collide, regardless of the modulo used to place them into a bucket. – Triynko Dec 16 '10 at 14:43
  • 11
    This kind of answer is very useful because it's like teaching someone how to fish, rather than catching one for them. It helps people *see* and *understand* the underlying principle behind using primes for hashes... which is to distribute inputs irregularly so they fall uniformly into buckets once moduloed :). – Triynko Dec 16 '10 at 14:44
  • This should be the answer. And the follow up questions in the above comments are excellent too (on why whether the prime being the multiplier or the modulus essentially doesn't make much of a difference). – Srikanth Sep 08 '20 at 05:26
110

Because you want the number you are multiplying by and the number of buckets you are inserting into to have orthogonal prime factorizations.

Suppose there are 8 buckets to insert into. If the number you are using to multiply by is some multiple of 8, then the bucket inserted into will only be determined by the least significant entry (the one not multiplied at all). Similar entries will collide. Not good for a hash function.

31 is a large enough prime that the number of buckets is unlikely to be divisible by it (and in fact, modern java HashMap implementations keep the number of buckets to a power of 2).

ILMTitan
  • 10,751
  • 3
  • 30
  • 46
  • 1
    What if there's 31 or 62 buckets (or some multiple of 31) then? – Steve Kuo Aug 31 '10 at 21:37
  • 9
    Then a hash function that multiplies by 31 will perform non-optimally. However, I would consider such a hash table implementation poorly designed, given how common 31 as a multiplier is. – ILMTitan Aug 31 '10 at 21:42
  • 11
    So 31 is chosen based on the assumption that hash table implementors know that 31 is commonly used in hash codes? – Steve Kuo Aug 31 '10 at 21:50
  • 3
    31 is chosen based on the idea that most implementations have factorizations of relatively small primes. 2s, 3s and 5s usually. It may start at 10 and grow 3X when it gets too full. The size is rarely entirely random. And even if it were, 30/31 are not bad odds for having well synced hash algorithms. It may also be easy to calculate as others have stated. – ILMTitan Aug 31 '10 at 21:55
  • 9
    In other words... we need to know something about the set of input values and the set's regularities, in order to write a function that's designed to strip them of those regularities, so the values in the set don't collide in the same hash buckets. Multiplying/Dividing/Moduloing by a prime number achieves that affect, because if you have a LOOP with X-items and you jump Y-spaces in the loop, then you'll never return to the same spot until X becomes a factor of Y. Since X is often an even number or power of 2, then you need Y to be prime so X+X+X... is not a factor of Y, so 31 yay! :/ – Triynko Dec 16 '10 at 14:58
  • 1
    31 is IMHO a quite bad choice since it allows for hashcode collisions as short as "Ca" and "DB". See here for a discussion of bettter choices: http://stackoverflow.com/a/2816747/21499 – Dr. Hans-Peter Störr Aug 16 '12 at 07:33
  • Suppose there are 8 buckets to insert into. If the number you are using to multiply by is some multiple of 8, then the bucket inserted into will only be determined by the least significant entry (the one not multiplied at all). .....can you give an example ? – Frank Q. Oct 04 '17 at 03:13
  • 3
    @FrankQ. It is the nature of modular arithmetic. `(x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8` – ILMTitan Oct 04 '17 at 16:36
  • @SteveKuo "What if there's 31 or 62 buckets (or some multiple of 31) then?" You always use a Prime bigger then the number of Buckets. it is not like we do not know of 10 digit primenumbers. Cryptography needs big primenumbers anyway, so they always look for "the next big thing". – Christopher Feb 06 '18 at 11:30
35

For what it's worth, Effective Java 2nd Edition hand-waives around the mathematics issue and just say that the reason to choose 31 is:

  • Because it's an odd prime, and it's "traditional" to use primes
  • It's also one less than a power of two, which permits for bitwise optimization

Here's the full quote, from Item 9: Always override hashCode when you override equals:

The value 31 was chosen because it's an odd prime. If it were even and 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 (§15.19) and subtraction for better performance:

 31 * i == (i << 5) - i

Modern VMs do this sort of optimization automatically.

While the recipe in this item yields reasonably good hash functions, it does not yield state-of-the-art hash functions, nor do Java platform libraries provide such hash functions as of release 1.6. Writing such hash functions is a research topic, best left to mathematicians and theoretical computer scientists.

Perhaps a later release of the platform will provide state-of-the-art hash functions for its classes and utility methods to allow average programmers to construct such hash functions. In the meantime, the techniques described in this item should be adequate for most applications.

Rather simplistically, it can be said that using a multiplier with numerous divisors will result in more hash collisions. Since for effective hashing we want to minimize the number of collisions, we try to use a multiplier that has fewer divisors. A prime number by definition has exactly two distinct, positive divisors.

Related questions

Community
  • 1
  • 1
polygenelubricants
  • 376,812
  • 128
  • 561
  • 623
  • 4
    Eh, but there're many suitable *primes* that are either *2^n + 1* (so called *Fermat primes*), i.e. `3, 5, 17, 257, 65537` or *2^n - 1* (*Mersenne primes*): `3, 7, 31, 127, 8191, 131071, 524287, 2147483647`. However `31` (and not, say, `127`) is opted. – Dmitry Bychenko Sep 23 '15 at 09:51
  • 4
    _"because it's an odd prime"_ ... there is only one even prime :P – Martin Schneider Sep 28 '16 at 09:57
  • 1
    I don't like the wording "is less clear, but it is traditional" in "Effective Java". If he doesn't want to go into the mathematical details he should write something like "has [similar] mathematical reasons" instead. The way he writes sounds like it only had historical background :( – Qw3ry Jul 25 '17 at 15:00
6

I heard that 31 was chosen so that the compiler can optimize the multiplication to left-shift 5 bits then subtract the value.

Steve Kuo
  • 61,876
  • 75
  • 195
  • 257
  • how could the compiler optimize that way? x*31==x*32-1 isn't true for all x afterall. What you meant was left shift 5 (equals multiply by 32) and then subtract the original value (x in my example). While this might be faster then a multiplication (it probaly isn't for modern cpu processors by the way), there are more important factors to consider when choosing a multiplication for a haschcode (equal distribution of input values to buckets comes to mind) – Grizzly Aug 31 '10 at 22:52
  • Do a bit of searching, this is a pretty common opinion. – Steve Kuo Aug 31 '10 at 22:54
  • 5
    Common opinion is irrelevant. – fractor Apr 15 '15 at 10:31
  • 3
    @Grizzly, it *is* faster than multiplication. IMul has a minimum latency of 3 cycles on any modern cpu. (see agner fog's manuals) `mov reg1, reg2-shl reg1,5-sub reg1,reg2` can execute in 2 cycles. (the mov is just a rename and takes 0 cycles). – Johan Jul 21 '15 at 17:11
3

Here's a citation a little closer to the source.

It boils down to:

  • 31 is prime, which reduces collisions
  • 31 produces a good distribution, with
  • a reasonable tradeoff in speed
John
  • 15,990
  • 10
  • 70
  • 110
3

First you compute the hash value modulo 2^32 (the size of an int), so you want something relatively prime to 2^32 (relatively prime means that there are no common divisors). Any odd number would do for that.

Then for a given hash table the index is usually computed from the hash value modulo the size of the hash table, so you want something that is relatively prime to the size of the hash table. Often the sizes of hash tables are chosen as prime numbers for that reason. In the case of Java the Sun implementation makes sure that the size is always a power of two, so an odd number would suffice here, too. There is also some additional massaging of the hash keys to limit collisions further.

The bad effect if the hash table and the multiplier had a common factor n could be that in certain circumstances only 1/n entries in the hash table would be used.

starblue
  • 55,348
  • 14
  • 97
  • 151
2

The reason why prime numbers are used is to minimize collisions when the data exhibits some particular patterns.

First things first: If the data is random then there’s no need for a prime number, you can do a mod operation against any number and you will have the same number of collisions for each possible value of the modulus.

But when data is not random then strange things happen. For example consider numeric data that is always a multiple of 10.

If we use mod 4 we find:

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

So from the 3 possible values of the modulus (0,1,2,3) only 0 and 2 will have collisions, that is bad.

If we use a prime number like 7:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

etc

We also note that 5 is not a good choice but 5 is prime the reason is that all our keys are a multiple of 5. This means we have to choose a prime number that doesn’t divide our keys, choosing a large prime number is usually enough.

So erring on the side of being repetitive the reason prime numbers are used is to neutralize the effect of patterns in the keys in the distribution of collisions of a hash function.

Amar Magar
  • 840
  • 1
  • 11
  • 15
1

31 is also specific to Java HashMap which uses a int as hash data type. Thus the max capacity of 2^32. There is no point in using larger Fermat or Mersenne primes.

DED
  • 143
  • 11
0

It generally helps achieve a more even spread of your data among the hash buckets, especially for low-entropy keys.