In-depth understanding of Java hashCode() method

Java.lang.Object There is a hashCode() and an equals() method, these two methods play a pivotal role in software design. Override these two methods in some classes to complete some important functions. This article describes why hashCode() is used, how to use it, and some other extensions. Reading this article requires basic knowledge of hash algorithms and basic Java collection knowledge. This article is an entry-level explanation for beginners. If you are an expert, please click the X in the upper right corner after reading this to avoid wasting your time^_^.

WHY hashCode()?

The elements in the setSet are unordered and non-repeatable. So what is the basis for judging whether two elements are repeated? "To compare whether objects are equal, of course use Object.equal()," said a certain monkey. However, there are a large number of objects in the Set, and the number of comparisons of object elements later added to the Set will gradually increase, which greatly reduces the efficiency of the program. Java uses a hash algorithm (also called a hash 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 an element (object) needs to be added to a Set containing a large number of elements, the hashCode() of this element is first called, and the actual storage location of this element can be located at once. If there is no element at this location, it means that this object When it is stored in the collection Set for the first time, the object is stored directly at this location; if there is an object at this location, call equal() to see if the two objects are equal. If they are equal, the element will be discarded and not stored. If they are not equal, the element will not be stored. Hashed to other addresses.

HOW use hashCode()?

The Java language has five requirements that must be followed when designing equal().

1. symmetry. If a.equal(b) returns "true", then b.equal(a) must also return "true".

2. Reflective. a.equal(a) must return "true".

3. Transitiveness. If a.equal(b) returns "true", and b.equal(c) returns "true", then c.equal(a) must return "true".

4. Consistent sex. If a.equal(b) returns "true", as long as the contents of a and b remain unchanged, a.equal(b) must return "true" no matter how many times it is repeated.

5. Any situation Below, a.equals(null) always returns "false"; a.equals (an object of a different type from a) always returns "false".

##hashCode() The relationship between the return value and equals().

1. If a.equals(b) returns "true", then the hashCode() of a and b must be equal.

2. If a.equals(b) returns "false", then the hashCode() of a and b may be equal or different.

Below 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;
    }
}

The following focuses on the hashCode() implementation methods of commonly used classes.

String class hasCode()

Java code

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]31

n-1 ^{+ s[1]31}n-2 ^{+ … + s[ n-1]}

s[i] is the i-th character of string, and n is the length of String. So why is 31 used 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 it is multiplied by 2 Equivalent to the

bit shift operation. The benefits of using prime numbers are not immediately obvious, but it is customary to use prime numbers to calculate hash results. 31 has a good feature, which is to use shifting and subtraction instead of multiplication, which can get better performance: 31*i==(i<<5)-i. Today's VM can automatically complete this optimization. (From Effective Java)

hasCode() of Object class

hashCode() in Object class is a Native method. How to call the Native method?

public native int hashCode();

The Native method class of the Object class can be found here. For in-depth analysis, please see another blog

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_IHashCode(line 504)

Function is defined in jvm.cpp. This function calls ObjectSynchronizer::FastHashCode, which is set in synchronizer.cpp. Please refer to Line 576 of FastHashCode and Line 530. Implementation of get_next_hash.

The above is the detailed content of In-depth understanding of Java hashCode() method. For more information, please follow other related articles on the PHP Chinese website!