Why use a prime number in hashCode?

by

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.

More Related Contents:

  1. What is a sensible prime for hashcode calculation?
  2. Prime number program does not work
  3. How can I generate an MD5 hash in Java?
  4. Best implementation for hashCode method for a collection
  5. Memory address of variables in Java
  6. What is an object’s hash code if hashCode() is not overridden?
  7. Understanding the workings of equals and hashCode in a HashMap
  8. What is the use of hashCode in Java?
  9. Good Hash Function for Strings
  10. How should equals and hashcode be implemented when using JPA and Hibernate
  11. Calculating and printing the nth prime number
  12. What would be the fastest method to test for primality in Java?
  13. How is hashCode() calculated in Java
  14. How to ensure hashCode() is consistent with equals()?
  15. How do you get the “object reference” of an object in java when toString() and hashCode() have been overridden?
  16. Finding largest prime number out of 600851475143?
  17. Why doesn’t String’s hashCode() cache 0?
  18. How does Java order items in a HashMap or a HashTable?
  19. How to get the unique ID of an object which overrides hashCode()?
  20. Why should I override hashCode() when I override equals() method?
  21. What is an “internal address” in Java?
  22. what is the difference between == operator and equals()? (with hashcode() ???)
  23. Should I write equals() and hashCode() methods in JPA entities?
  24. Can Java’s hashCode produce same value for different strings?
  25. Mutable objects and hashCode
  26. Hashcode and equals
  27. How default .equals and .hashCode will work for my classes?
  28. How to determine if a number is prime
  29. Java: Use hashCode() inside of equals() for convenience?
  30. Bit-shifting in Effective Java hashCode() implementation

Leave a Comment