How to use hashcode and equals in Java

preface

As we all know, Java Lang. object has a hashcode () and an equals () method, which play an important role in software design. Override these two methods in some classes to perform some important functions.

1. Why hashcode ()?

The elements in the set are unordered and non repeatable. What is the basis for judging whether two elements are repeated?

Some people say: whether the comparison objects are equal or not, of course, object Equal(). However, there are a large number of objects in the set, and the comparison times of object elements added to the set will gradually increase, which greatly reduces the running efficiency of the program. In Java, hash algorithm (also known as hash algorithm) is used 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, you can call the hashcode () of this element first to locate the actual storage location of this element. If there is no element in this location, it means that this object is stored in the collection set for the first time, and this object is directly stored in this location; If an object exists at this location, call equal () to see if the two objects are equal. If they are equal, discard the element. If they do not exist, hash them to other addresses.

This is why when the set collection stores object type data, it should not only rewrite the hashcode () method of the object, but also rewrite the equals () method.

2、HOW use hashCode()?

The relationship between the return value of hashcode() and equals()

Here is an example. In actual software development, it is best to rewrite these two methods.

The equals () and hashcode () methods are used for comparison in the same class, especially when storing objects of the same class in a container, such as set, to judge whether the objects are repeated.

Here, we should first understand a problem:

Two objects with equal () and hashcode () must be equal. Two objects with unequal equals () do not prove that their hashcode () is not equal. In other words, hashcode () may be equal for two objects whose equals () method is not equal.

Here, hashcode is like the index of each word in the dictionary, and equals () is like comparing different words under the same word in the dictionary. It's like looking up the two words "self" and "spontaneous" under the word "self" in the dictionary. If equals () is used to judge that the queried words are equal, then it is the same word. For example, both words compared by equals () are "self", then the values obtained by hashcode () method must be equal; If the equals () method is used to compare the words "self" and "spontaneous", the result is that you don't want to wait, but these two words belong to the words under the word "self", so they are the same when looking up the index, that is, hashcode () is the same. If the words "themselves" and "they" are compared with equals (), the result is also different. At this time, hashcode () also gets different results.

Conversely, if hashcode () is not equal, equals () will be introduced; Hashcode () is equal, and equals () may be equal or unequal.

In the object class, the hashcode () method is a local method that returns the address value of the object. The equals () method in the object class also compares the address values of the two objects. If equals () is equal, it means that the address values of the two objects are equal. Of course, hashcode () is equal.

Since equals is more accurate than element equality, why use the hashcode () method?

Because the hash algorithm provides high efficiency for finding elements, if you want to find whether an object is contained in a set, how to write the approximate program code? You usually take out each element one by one and compare it with the object to be found. When you find that the result of the equals method comparison between an element and the object to be found is equal, stop the search and return positive information. Otherwise, return negative information. If there are many elements in a collection, such as 10000 elements, and there is no object to be found, It means that your program needs to take 10000 elements from the set and compare them one by one to get a conclusion.

A hashcode () method is defined in the object class to return the hash code of each Java object. When searching for an object from the HashSet set, the Java system first calls the hashcode () method of the object to obtain the hash code table of the object, then finds the corresponding storage area according to the hash, and finally obtains each element in the storage area and compares it with the object with the equals method; In this way, we can get the conclusion without traversing all the elements in the set. It can be seen that the HashSet set has good object retrieval performance.

However, the efficiency of storing objects in the HashSet collection is relatively low, because when adding an object to the HashSet collection, you must first calculate the hash code of the object and determine the storage location of the object in the collection according to the hash code. In order to ensure that the instance objects of a class can be stored normally in the HashSet, when the comparison results of the two instance objects of this class with the equals () method are equal, Their hash codes must also be equal; That is, if obj1 If the result of equals (obj2) is true, the result of the following expression should also be true: obj1 hashCode() == obj2. hashCode() 。

In other words, when we rewrite the equals method of an object, we must rewrite its hashcode method. If we do not rewrite its hashcode method, the hashcode method in the object object always returns the hash address of an object, and this address is never equal. Therefore, even rewriting the equals method at this time will not have a specific effect, because if the hashcode method does not want to wait, it will not call the equals method for comparison, so it is meaningless.

Most data structures use the equals method to determine whether they contain an element, for example:

The result of this variable contains is true, because although "B" are different instances (in addition, ignoring string persistence), they are equal.

Instead of comparing each element contained in an instance, they compare by using a shortcut (reducing potential instance equality). The quick comparison only needs to compare the following aspects:

Shortcut comparison is to replace an instance with an integer value by comparing hash values. Instances with the same hash code are not necessarily equal, but equal instances must have the same hash value. (or there should be, we will discuss this soon) these data structures are often named by this technology, and their can be identified by hash. Among them, HashMap is the most famous representative.

They usually work like this:

When adding an element, its hash code is used to calculate the index of the internal array (the so-called bucket)

If so, unequal elements have the same hash code, and they end up in the same bucket and tied together, for example, by adding to the list. When an instance performs the contains operation, its hash code will be used to calculate the bucket value (index value). Instances will be compared only when there are elements on the corresponding index value.

Therefore, equals and hashcode are defined in the object class.

If hashcode is used as a shortcut to determine equality, there is only one thing we should care about: equal objects should have the same hash code, which is why if we override the equals method, we must create a matching hashcode implementation!

Otherwise, equal objects may not have the same hash code, because they will call the default implementation of object's.

Quoted from official documents