In this post we will discuss about Why Prime Numbers are considered in writing certain algorithms like hashcode()?
Prime numbers are usually very useful for generating hashcode, RSA algorithms, random number generators. If you look into String Class hashCode method which multiplies its hash value by prime number 31 :
Within JDK String Class hashCode() method implementation
|
1 2 3 4 5 6 7 8 9 10 11 12 |
public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } |
A number is either prime number or a composite number (can be factorized into prime numbers). Prime numbers are always unique and cannot be divided by any other number except 1. The product of prime number with any other number has the best chances of being unique (though not as unique as Prime number itself) due to the fact that prime number is used to compose it. This property of prime number makes it very suitable for use in hashing function so as to get fair distribution in its hashCode output and thus achieving low collisions.
Multiplying by the prime number will not tend to shift information away from the low end, as it would multiplying by a power of 2, thus achieving a fair randomness.
You may also like:
Why Java is not 100% Object-oriented language?
Can we call static method with null object?
Can we override static method in Java?
What will be the output of following java program?
What is the difference Between java.util.Date and java.sql.Date in Java ?
That’s all about Why Prime Numbers are considered in writing certain algorithms like hashcode()?
If you have any feedback or suggestion please feel free to drop in blow comment box.