What is a sensible prime for hashcode calculation?

by

I recommend using 92821. Here’s why.

To give a meaningful answer to this you have to know something about the possible values of i and j. The only thing I can think of in general is, that in many cases small values will be more common than large values. (The odds of 15 appearing as a value in your program are much better than, say, 438281923.) So it seems a good idea to make the smallest hashcode collision as large as possible by choosing an appropriate prime. For 31 this rather bad – already for i=-1 and j=31 you have the same hash value as for i=0 and j=0.

Since this is interesting, I’ve written a little program that searched the whole int range for the best prime in this sense. That is, for each prime I searched for the minimum value of Math.abs(i) + Math.abs(j) over all values of i,j that have the same hashcode as 0,0, and then took the prime where this minimum value is as large as possible.

Drumroll: the best prime in this sense is 486187739 (with the smallest collision being i=-25486, j=67194). Nearly as good and much easier to remember is 92821 with the smallest collision being i=-46272 and j=46016.

If you give “small” another meaning and want to be the minimum of Math.sqrt(i*i+j*j) for the collision as large as possible, the results are a little different: the best would be 1322837333 with i=-6815 and j=70091, but my favourite 92821 (smallest collision -46272,46016) is again almost as good as the best value.

I do acknowledge that it is quite debatable whether these calculation make much sense in practice. But I do think that taking 92821 as prime makes much more sense than 31, unless you have good reasons not to.

More Related Contents:

  1. Why use a prime number in hashCode?
  2. What issues should be considered when overriding equals and hashCode in Java?
  3. Why do I need to override the equals and hashCode methods in Java?
  4. How can I generate an MD5 hash in Java?
  5. Best implementation for hashCode method for a collection
  6. How does a Java HashMap handle different objects with the same hash code?
  7. What is the use of hashCode in Java?
  8. How do hashCode() and identityHashCode() work at the back end?
  9. Calculating and printing the nth prime number
  10. What would be the fastest method to test for primality in Java?
  11. How is hashCode() calculated in Java
  12. Java Array HashCode implementation
  13. How to ensure hashCode() is consistent with equals()?
  14. How to determine if a number is a prime with regex?
  15. Consistency of hashCode() on a Java string
  16. Apache Commons equals/hashCode builder [closed]
  17. How to get the unique ID of an object which overrides hashCode()?
  18. Hashcode and Equals for Hashset [duplicate]
  19. How does the JVM ensure that System.identityHashCode() will never change?
  20. Why does String.hashCode() in Java have many conflicts? [closed]
  21. Double in HashMap
  22. what is the difference between == operator and equals()? (with hashcode() ???)
  23. What exactly is bucket in hashmap?
  24. How to implement hashCode and equals method
  25. Is it possible in java make something like Comparator but for implementing custom equals() and hashCode()
  26. How to create a HashMap with two keys (Key-Pair, Value)?
  27. Are two Java objects with same hashcodes not necessarily equal?
  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