The past life and present life of hashcode() method in Java

When we want to learn the hashcode() method, we need to figure out the following aspects step by step:

1. The origin of hashcode()

hashcode is an int calculated by jdk based on the address of the object or a string or a number Type of numerical value, how is it calculated? The answer is hashtable. A hash table is a data structure that is directly accessed based on the key value. This may be too official. Let me tell you my understanding here. Hashcode is a value obtained by mapping a function. This function is called a hash function. When we pass a key value to the function, we will get a value value. The value obtained by the hash function is the hash value, that is, value=f(key). So after understanding hashcode, we know what the hashcode() method is used for. The hashcode() method is to calculate and return the hashcode method.

2. The role of hashcode()

The main benefit of the hash table is that it can improve search efficiency. By looking at the API, we can find that hashcode() is a method of Object. It can also be said that under normal circumstances, objects of all classes can call the hashcode() method. In Java, according to its characteristics of improving search efficiency, we mainly apply it in In order to work properly with hash-based collections, such hash collections include HashSet, HashMap, and HashTable. Duplicate elements are not allowed to exist in the set, so when we need to add a new element, how to judge that the element already exists? Perhaps most people will think of calling the equals method to compare one by one. This method is indeed feasible. But if there are already 10,000 pieces of data or more in the collection, and if you use the equals method to compare them one by one, efficiency must be a problem. At this time, the role of the hashCode method is reflected. When a new object is added to the collection, the hashCode method of this object is first called to get the corresponding hashcode value. In fact, in the specific implementation of HashMap, a table will be used to save the already saved The hashcode value of the object. If the hashcode value does not exist in the table, it can be stored directly without any comparison. If the hashcode value exists, its equals method is called to compare with the new element. If it is the same, it will not be compared. If it is saved, other addresses will be hashed if they are not the same, so there is a problem of conflict resolution, so the number of actual calls to the equals method is greatly reduced. The following code is the specific implementation of the put method in java.util.HashMap:

public V put(K key, V value) {     
   if (key == null)     
          return putForNullKey(value);    
    int hash = hash(key.hashCode());   
         int i = indexFor(hash, table.length);    
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;          
          if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);     
                     return oldValue;
            }
        }
 
        modCount++;
        addEntry(hash, key, value, i);  
                           return null;
    }

The put method is used to add new elements to the HashMap. From the specific implementation of the put method, it can be seen that the hashCode method will first be called to obtain the element. hashCode value, and then check whether the hashCode value exists in the table. If it exists, call the equals method to re-determine whether the element exists. If it exists, update the value value, otherwise add the new element to the HashMap. It can be seen from here that the hashCode method exists to reduce the number of calls to the equals method, thereby improving program efficiency.

3.hashcode() method and equals() method

There are several issues that need to be noted here. To determine whether objects are equal, you can use the hashcode() method. The answer is no, you must use the equals() method. Two different objects may have equal hashcodes, but two objects with different hashcodes must be different.

Another issue to note: When designing a class, it is necessary to override the equals method, such as the String class, but be sure to note that when rewriting the equals method, you must also override the hashCode method. Let’s look at an example that only overrides the equals method:

 import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
 
class People{
    private String name;
    private int age;
     
    public People(String name,int age) {
        this.name = name;
        this.age = age;
    }  
     
    public void setAge(int age){
        this.age = age;
    }
         
    @Override
    public boolean equals(Object obj) {
        // TODO Auto-generated method stub
        return this.name.equals(((People)obj).name) && this.age== ((People)obj).age;
    }
}
 
public class Main {
 
    public static void main(String[] args) {
         
        People p1 = new People("Jack", 12);
        System.out.println(p1.hashCode());
             
        HashMap<People, Integer> hashMap = new HashMap<People, Integer>();
        hashMap.put(p1, 1);
         
        System.out.println(hashMap.get(new People("Jack", 12)));
    }
}

If two People objects have the same name and age, they are considered to be the same person. The original intention of this code is that the output result of this code is "1", but in fact it outputs "null".

Although by overriding the equals method, two objects with the same name and age are logically judged to be equal objects (similar to the String class), you must know that by default, the hashCode method maps the storage address of the object. It is not surprising that the output of the above code is "null". The reason is very simple. The object pointed to by p1 and System.out.println(hashMap.get(new People("Jack", 12))); new People("Jack", 12) in this sentence generate two objects. , their storage addresses must be different. Therefore, when the hashmap performs a get operation, null is returned directly because the hashcdoe values ​​obtained are different. If you want the output result of the above code to be "1", it is very simple. You only need to rewrite the hashCode method so that the equals method and the hashCode method are always logically consistent.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
 
 
class People{
    private String name;
    private int age;
     
    public People(String name,int age) {
        this.name = name;
        this.age = age;
    }  
     
    public void setAge(int age){
        this.age = age;
    }
     
    @Override
    public int hashCode() {
        // TODO Auto-generated method stub
        return name.hashCode()*37+age;
    }
     
    @Override
    public boolean equals(Object obj) {
        // TODO Auto-generated method stub
        return this.name.equals(((People)obj).name) && this.age== ((People)obj).age;
    }
}
 
public class Main {
 
    public static void main(String[] args) {
         
        People p1 = new People("Jack", 12);
        System.out.println(p1.hashCode());
             
        HashMap<People, Integer> hashMap = new HashMap<People, Integer>();
        hashMap.put(p1, 1);
         
        System.out.println(hashMap.get(new People("Jack", 12)));
    }
}

The following is a quote from the book Effective Java:

During program execution, as long as the information used in the comparison operation of the equals method is not modified, then the same object is called multiple times, and the hashCode method must consistently return the same value. an integer.

If two objects are equal according to the equals method comparison, then calling the hashCode method of the two objects must return the same integer result.

If two objects are not equal according to the equals method, the hashCode method does not necessarily have to return different integers.

　The second and third items are easy to understand, but the first one is often ignored. There is also a paragraph similar to the first one on page P495 of the book "Java Programming Thoughts":

　　The most important factor when designing hashCode() is that whenever hashCode() is called on the same object, it should produce the same value. If an object is added to a HashMap using put(), a hashCdoe value is generated. When using get() to retrieve it, another hashCode value is generated, so the object cannot be obtained. Therefore, if your hashCode method relies on volatile data in the object, users should be careful because when this data changes. , the hashCode() method will generate a different hash code."