Hashcode Inside the 31-Factor Problem

F First we look at hashcode, what is hashcode? What is the role?

hashcode is actually a hash code, using high efficiency hashcode hash algorithm to locate find the object!

We will calculate the hash code string when using containers to store data, then the data into a container.

Such as: String s = "java", then the computer will first calculate the hash code, and then placed in the appropriate array, the array index is calculated from the hash you come in, and then into the array of containers, such as List This is equivalent to you to save the data into several large parts, then every part of the store a lot of value when you query large part to check, and then in a large part of the investigation inside the small, so much faster than the first inquiry!

HashCode an object is a simple Hash algorithm, although it and the really complex! Hash algorithms can not be called a true compared to the algorithm, but how to achieve it, the level of programming issue is not just programmers, but rather to target in your very important question of access time performance is possible, may differ HashCode Object Access will make you produce hundreds of times the performance difference!

java String in this type of instance object print time is always displayed in the following form

test.Test$tt@c17164

The above is the class name $ tt test.Test I write inner classes, and what is behind @ this period be? He is actually tt instance of this class hashcode is hexadecimal!

It uses the toString () method inside ObjectJava Code. return getClass () getName () + "@" + Integer.toHexString (hashCode ());

String hashcode in java continue to see the source code:Java Codepublic int hashCode () {

int h = hash;
int len ​​= count;
if (h == 0 && len> 0)
 {
int off = offset;
char val [] = value;

for (int i = 0; i <len; i ++) {
h = 31 * h + val [off ++];
}
hash = h;
}
return h;
}

In fact, the above implementation is mathematics:Java Codes [0] * 31 ^ (n-1) + s [1] * 31 ^ (n-2) + ... + s [n-1]

Realization! We will pay attention to the idea that this factor Why do 31 on the inside to take the ride to go? Why not applicable 32 or any other number?

As we all know, the computer involves multiplication shift calculation. When a number is multiplied by 2 to get the number directly to the left one! Select 31 because 31 is a prime number!

The so-called prime numbers:

Also known prime number prime number
. It refers to a natural number greater than 1, in addition to 1 and the integer itself, but not by several other natural number divisible.

Primes in use when there is a role that if I use a number that is multiplied by this prime number, then the final out of the result can only be primes itself and there is a divisible Multiplicand! Such as: do we choose a prime number 3 factor, then 3 * n can be 1 to 3 and n or divisible, we can easily calculate that n 3n to come by. It should also be a reason!

When the stored data to calculate the hash address, we want to minimize the same hash address, so-called "conflict." If you use the same hash address data too much, then the data consisting of

hash chain even longer, thereby reducing the query efficiency! So factor in the choice of when to choose as long as possible so that the multiplication factor and try not to spill the coefficient, because if the calculated hash address the greater the

So-called "conflict" less, find them efficiency will improve.

1 31 can be represented by i * 31 == (i << 5), which has many virtual machines do related optimization, using 31 may be due to better distribution hash address, and 31 occupied 5 bits!

In java multiplication If the number is multiplied too large, the overflow problem, leading to loss of data.

And 31 is a prime number (prime number) and not very long numbers, in the end it was chosen for a reason, but coefficients are multiplied with this!