1.WHY hashCode()?
The elements in the set set are disordered and unrepeatable, so what is the basis for judging whether two elements are repeated? "Of course, Object.equal() is used to compare whether the objects are equal," said a certain ape. However, there are a large number of objects in the Set, and the number of comparisons of object elements added to the set set will gradually increase, greatly reducing the efficiency of the program operation. Java uses hashing algorithm (also called hashing algorithm) to solve this problem. The object (or data) is directly mapped to an address according to a specific algorithm, and the access efficiency of the object is greatly improved. In this way, when a set set containing a large number of elements needs to add an element (object), first call the hashCode() of this element, and you can position the actual storage location of this element at once. If there is no element at this position, it means that the object is stored in the collection Set for the first time, and the object is stored directly at this position; if there is an object at this position, call equal() to see if the two objects are equal. If the same is true, discard the element and do not exist. If it is not equal, hash to other addresses.
2.HOW use hashCode()?
Java language has five requirements that must be followed for equal() in ape design.
symmetry. If a.equal(b) returns "true", then b.equal(a) must also return "true".
Reflective. a.equal(a) must return "true".
Transitive. If a.equal(b) returns "true" and b.equal(c) returns "true", then c.equal(a) must return "true".
consistency. If a.equal(b) returns "true", as long as the content of a and b remains unchanged, no matter how many times a.equal(b) must return "true".
In any case, a.equals(null) always returns "false"; a.equals (objects of different types and a) always returns "false".
The relationship between the return value of hashCode() and equals().
If a.equals(b) returns "true", then the hashCode() of a and b must be equal.
If a.equals(b) returns "false", then the hashCode() of a and b may be equal or may be unequal.
Here is an example. In actual software development, it is best to rewrite these two methods.
public class Employee { int employeeId; String name; // other methods would be in here @Override public boolean equals(Object obj) { if(obj==this) return true; Employee emp=(Employee)obj; if(employeeId.equals(emp.getEmployeeId()) && name==emp.getName()) return true; return false; } @Override public int hashCode() { int hash = 1; hash = hash * 17 + employeeId; hash = hash * 31 + name.hashCode(); return hash; }}3. The following is a focus on the hashCode() implementation method of commonly used classes.
hasCode() of String class
public int hashCode() { int h = hash; if (h == 0) { int off = offset; char val[] = value; int len = count; for (int i = 0; i < len; i++) { h = 31*h + val[off++]; } hash = h; } return h; }The most interesting thing about this code is the implementation method of hash. The final calculated hash value is:
s[0]31n-1 + s[1]31n-2 + … + s[n-1]
s[i] is the i-th character of a string, and n is the length of a String. Then why use 31 here instead of other numbers?
31 is an odd prime number. If the multiplier is an even number and the multiplication overflows, the information will be lost because multiplication with 2 is equivalent to shift operation. The benefits of using prime numbers are not obvious, but the hash results are conventionally used to calculate the hash results. 31 has a good feature, which is to use shift and subtraction instead of multiplication to obtain better performance: 31*i==(i<<5)-i. VMs can automatically complete this optimization. (From Effective Java)
hasCode() of Object class
hashCode() is a Native method in the Object class. How to call Native methods?
public native int hashCode();
The Native method class of the Object class can be found here. Please read another blog for in-depth analysis
static JNINativeMethod methods[] = { {"hashCode", "()I", (void *)&JVM_IHashCode}, {"wait", "(J)V", (void *)&JVM_MonitorWait}, {"notify", "()V", (void *)&JVM_MonitorNotify}, {"notifyAll", "()V", (void *)&JVM_MonitorNotifyAll}, {"clone", "()Ljava/lang/Object;", (void *)&JVM_Clone},};The source code includes getClass()(See line58), etc. hashCode()(See line43) is defined as a pointer to JVM_IHashCode.
jvm.cpp defines the JVM_IHashCode(line 504) function. This function calls ObjectSynchronizer::FastHashCode, which is determined in synchronizer.cpp. For the implementation of FastHashCode in line 576 and get_next_hash in line 530, you can refer to the implementation of FastHashCode in line 576 and get_next_hash in line 530.