Java Collection - Detailed Explanation of equals and hashCode Methods in Java

In Java, the equals() and hashCode() methods are in the Object class, so every object has these two methods. Sometimes, we may need to implement specific requirements and may need to override these two methods. Today, we will introduce some of the functions of these two methods.

The equals() and hashCode() methods are used for comparison within the same class, especially when used in containers such as sets to store objects of the same type to determine if the object being inserted is a duplicate.

Here, we first need to understand a question:

If two objects are equal according to equals(), their hashCode() must also be equal. However, if two objects are not equal according to equals(), it does not necessarily mean that their hashCode() are not equal. In other words, if two objects are not equal according to the equals() method, hashCode() may still be equal. (My understanding is that this is caused by collisions when the hash code is generated)

Here, hashCode is like the index of each character in the dictionary, while equals() is used to compare different words under the same character in the dictionary. For example, if we look up the words 'oneself' and 'spontaneous' under the character 'zi' in the dictionary, if the words compared by equals() are equal, then they are the same word, such as when equals() compares the words 'oneself', then the hashCode() method will also get the same value; if equals() compares the words 'oneself' and 'spontaneous', the result will be different, but both words belong to the words under the character 'zi', so when looking up the index, they are the same, that is: hashCode() is the same. If equals() compares the words 'oneself' and 'they', the result will also be different, and in this case, hashCode() will also be different.

Conversely: if hashCode() is not equal, it can definitely be concluded that equals() is not equal; if hashCode() is equal, equals() may be equal or not equal. In the Object class, the hashCode() method is a native method, which returns the address value of the object. The equals() method in the Object class also compares the address values of two objects. If equals() is equal, it means that the address values of the two objects are also equal, of course, hashCode() is also equal.

At the same time, the hash algorithm provides a high efficiency for searching elements.

If you want to search for an object in a set, how should the program code be written?

You usually take out each element one by one and compare it with the object to be searched. When you find that an element is equal to the object to be searched when compared using the equals method, you stop searching further and return a positive message. Otherwise, return a negative message. If there are many elements in a set, for example, ten thousand elements, and the object to be searched is not included, it means that your program needs to take out ten thousand elements from the set for a one-by-one comparison to reach a conclusion.

Someone invented a hash algorithm to improve the efficiency of searching for elements in a set. This method divides the set into several storage areas, and each object can be calculated to produce a hash code. The hash codes can be grouped (calculated using different hash functions), and each group corresponds to a specific storage area. The storage area for an object can be determined based on its hash code. HashSet uses the hash algorithm to store objects, internally using the modulo operation on a number n (this type of hash function is the simplest) to group hash codes and divide the storage areas for objects. The Object class defines a hashCode() method to return the hash code for each Java object. When searching for an object in a HashSet collection, the Java system first calls the hashCode() method of the object to obtain the hash code table, then finds the corresponding storage area based on the hash code, and finally compares each element in the storage area with the object using the equals method. This way, it is not necessary to traverse all elements in the collection to reach a conclusion, which shows that the HashSet collection has excellent 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, it is necessary to first calculate the hash code of the object and determine the storage position of the object based on this hash code. To ensure that an instance object of a class can be stored normally in HashSet, it is required that the two instance objects of the class have the same result when compared using the equals() method, and their hash codes must also be equal. That is to say, if obj1.equals(obj)2if the result of the following expression is true, then the result of the following expression must also be true:
obj1.hashCode() == obj2.hashCode()

In other words: when we override an object's equals method, we must also override its hashCode method. However, if the hashCode method is not overridden, the hashCode method in the Object object always returns a hash address of an object, and this address is always different. Therefore, even if the equals method is overridden, there will be no specific effect, because if the hashCode methods are not equal, the equals method will not be called for comparison, so it is meaningless.

If a class's hashCode() method does not follow the above requirements, then when two instance objects of this class are compared using the equals() method and the result is equal, they should not be able to be stored in a set collection at the same time. However, if they are stored in a HashSet collection, due to the different return values of their hashCode() methods (the hashCode method in Object returns a value that is always different), the second object may first be placed in a different area from the first object according to the hash code calculation, so it may not be able to be compared with the first object using the equals method, and may be stored in the HashSet collection. The hashCode() method in the Object class does not meet the requirements for an object to be stored in a HashSet, because its return value is calculated based on the memory address of the object, and the hash value returned by the same object at any time during the program execution is always the same. Therefore, as long as two different instance objects, even if their equals method comparison results are equal, their default hashCode method return values are different.

Let's take a look at a specific example below:

RectObject object:
package com.weijia.demo; 
public class RectObject { 
  public int x; 
  public int y; 
  public RectObject(int x,int y){ 
    this.x = x; 
    this.y = y; 
  } 
  @Override 
  public int hashCode(){ 
    final int prime = 31; 
    int result = 1; 
    result = prime * result + x; 
    result = prime * result + y; 
    return result; 
  } 
  @Override 
  public boolean equals(Object obj){ 
    if(this == obj) 
      return true; 
    if(obj == null) 
      return false; 
    if(getClass() != obj.getClass()) 
      return false; 
    final RectObject other = (RectObject)obj; 
    if(x != other.x){ 
      return false; 
    } 
    if(y != other.y){ 
      return false; 
    } 
    return true; 
  } 
} 

We have overridden the hashCode and equals methods in the superclass Object, and we can see that if the x, y values of two RectObject objects are equal, their hashCode values are also equal, and the equals method returns true;

The following is the test code:

package com.weijia.demo; 
import java.util.HashSet; 
public class Demo { 
  public static void main(String[] args){ 
    HashSet<RectObject> set = new HashSet<RectObject>(); 
    RectObject r1 = new RectObject(3,3); 
    RectObject r2 = new RectObject(5,5); 
    RectObject r3 = new RectObject(3,3); 
    set.add(r1); 
    set.add(r2); 
    set.add(r3); 
    set.add(r1); 
    System.out.println("size:")+set.size()); 
  } 
} 

We put four objects into the HashSet, print the size of the set collection, what is the result?

Running result: size:2

Why is it that2This is simple, because we have overridden the hashCode method of the RectObject class, as long as the x, y attribute values of the RectObject object are equal, then its hashCode value is also equal, so compare the hashCode value first, r1And r2The x, y attribute values of the object are not equal, so their hashCode is not the same, so r2The object can be put in, but r3The x, y attribute values of the object and r1The attribute values of the object are the same, so hashCode is equal, at this time when comparing r1And r3The equals method, because their x, y values are equal, so r1, r3The object is equal, so r3Can not be added, and then add another r1Also did not add, so the set collection only has one r1And r2These two objects

Below we comment out the hashCode method in the RectObject object, that is, do not override the hashCode method in the Object object, and run the code again:

Running result: size:3

This result is also very simple, first judge r1The object and r2The hashCode of the object, because the hashCode method in Object returns the conversion result of the local memory address of the object, the hashCode of different instance objects is not the same, and similarly because r3And r1The hashCode is also not equal, but r1==r1So the final set collection only has r1, r2, r3These three objects, so the size is3

Below we comment out the content of the equals method in the RectObject object, directly return false, do not comment out the hashCode method, and run the code:

Running result: size:3

This result is a bit unexpected, let's analyze it:

First r1And r2The object compares hashCode, not equal, so r2Put it into the set, and then take a look at r3, compare r1And r3The hashCode method is equal, then compare their equals method, because the equals method always returns false, so r1And r3Also not equal, r3And r2Need not be said, their hashCode is not equal, so r3Put it into the set, and then look at r4, compare r1And r4Found that hashCode is equal, in the comparison of equals method, because equals returns false, so r1And r4Not equal, the same r2And r4Also not equal, r3And r4Also not equal, so r4Can be put into the set collection, so the result should be size:4Why is it that3what about it?

At this point, we need to look at the source code of HashSet, and below is the source code of the add method in HashSet:

/** 
   * Adds the specified element to this set if it is not already present. 
   * More formally, adds the specified element <tt>e</tt> to this set if 
   * this set contains no element <tt>e2</tt> such that 
   * <tt>(e==null ? e2==null : e.equals(e2))</tt>. 
   * If this set already contains the element, the call leaves the set 
   * unchanged and returns <tt>false</tt>. 
   * 
   * @param e The element to be added to this set 
   * return <tt>true</tt> if this set did not already contain the specified 
   * element 
   */ 
  public boolean add(E e) { 
    return map.put(e, PRESENT) == null; 
  } 

Here we can see that HashSet is actually implemented based on HashMap, when we click on the HashMap's put method, the source code is as follows:

/** 
   * Associates the specified value with the specified key in this map. 
   * If the map previously contained a mapping for the key, the old 
   * The value is replaced. 
   * 
   * @param key The key with which the specified value is to be associated 
   * @param value The value to be associated with the specified key 
   * return the previous value associated with <tt>key</tt>, or 
   *     <tt>null</tt> if there was no mapping for <tt>key</tt>. 
   *     (A <tt>null</tt> return can also indicate that the map 
   *     previously associated <tt>null</tt> with <tt>key</tt>.) 
   */ 
  public V put(K key, V value) { 
    if (key == null) 
      return putForNullKey(value); 
    int hash = hash(key); 
    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; 
  } 

We mainly look at the judgment condition of if

Firstly, it is judged whether hashCode is equal, if not equal, it is directly skipped, if equal, then it is compared whether the two objects are equal or the equals method of the two objects, because it is an or operation, so as long as one is true, that is, here we can explain, in fact, the size of the above collection is3, because the last r1has not been put in, thinking that r1==r1return true, so it has not been put in. So the size of the collection is3If we set the hashCode method to always return false, this collection will be4.

Finally, let's take a look at the problem of memory leak caused by hashCode: let's take a look at the code:

package com.weijia.demo; 
import java.util.HashSet; 
public class Demo { 
  public static void main(String[] args){ 
    HashSet<RectObject> set = new HashSet<RectObject>(); 
    RectObject r1 = new RectObject(3,3); 
    RectObject r2 = new RectObject(5,5); 
    RectObject r3 = new RectObject(3,3); 
    set.add(r1); 
    set.add(r2); 
    set.add(r3); 
    r3.y = 7; 
    System.out.println("The size before deletion: ")+set.size()); 
    set.remove(r3); 
    System.out.println("The size after deletion: ")+set.size()); 
  } 
} 

The running result:

The size before deletion:3
The size after deletion:3

Oops, I found a problem, and it's a big problem, we called remove to delete r3object, thinking that r has been deleted3But in fact, it is not deleted, which is called memory leak, that is, the unused object but it is still in memory. So after we do this operation multiple times, the memory is full. Let's take a look at the source code of remove:

/** 
   * Removes the specified element from this set if it is present. 
   * More formally, removes an element <tt>e</tt> such that 
   * <tt>(o==null &63; e==null : o.equals(e))</tt>, 
   * tt> if this set contains such an element. Returns <tt>true</tt> if 
   * this set contained the element (or equivalently, if this set 
   * changed as a result of the call). (This set will not contain the 
   * element once the call returns.) 
   * 
   * param o object to be removed from this set, if present 
   * return <tt>true</tt> if the set contained the specified element 
   */ 
  public boolean remove(Object o) { 
    return map.remove(o)==PRESENT; 
  } 

Then let's take a look at the source code of the remove method:

/** 
   * Removes the mapping for the specified key from this map if present. 
   * 
   * param key key whose mapping is to be removed from the map 
   * return the previous value associated with <tt>key</tt>, or 
   *     <tt>null</tt> if there was no mapping for <tt>key</tt>. 
   *     (A <tt>null</tt> return can also indicate that the map 
   *     previously associated <tt>null</tt> with <tt>key</tt>.) 
   */ 
  public V remove(Object key) { 
    Entry<K,V> e = removeEntryForKey(key); 
    return (e == null &63; null : e.value); 
  } 

Let's take a look at the source code of the removeEntryForKey method:

/** 
   * Removes and returns the entry associated with the specified key 
   * in the HashMap. Returns null if the HashMap contains no mapping 
   * for this key. 
   */ 
  final Entry<K,V> removeEntryForKey(Object key) { 
    int hash = (key == null) ? 0 : hash(key);63; 0 : hash(key); 
    int i = indexFor(hash, table.length); 
    Entry<K,V> prev = table[i]; 
    Entry<K,V> e = prev; 
    while (e != null) { 
      Entry<K,V> next = e.next; 
      Object k; 
      if (e.hash == hash && 
        ((k = e.key) == key || (key != null && key.equals(k)))) { 
        modCount++; 
        size--; 
        if (prev == e) 
          table[i] = next; 
        else 
          prev.next = next; 
        e.recordRemoval(this); 
        return e; 
      } 
      prev = e; 
      e = next; 
    } 
    return e; 
  } 

We see that when calling the remove method, the object's hashCode value is first used to find this object, and then it is deleted. This kind of problem is because we have modified the r3The value of the y attribute of the object, and because the hashCode method of the RectObject object involves the y value, so r3The hashCode of the object has changed, so the remove method did not find r3So the deletion failed. That is, r3The hashCode has changed, but the storage position has not been updated, it is still in the original position, so when we use his new hashCode to find it, it is definitely not found.
The implementation of the above method is very simple: as shown in the following figure:

This is a simple linear hash table, using the hash function mod, the source code is as follows:

/** 
  * Returns index for hash code h. 
  */ 
  static int indexFor(int h, int length) { 
    return h & (length-1); 
  } 

This is actually a mod operation, but this operation is more efficient than % operation.

1,2,3,4,5Represents the result of mod, each element corresponds to a linked list structure, so to delete an Entry<K,V>, you first need to get the hashCode to obtain the head node of the linked list, and then traverse this linked list. If hashCode and equals are equal, delete this element.
This memory leak tells me a piece of information: if we involve the property value of the object in the hashCode calculation, we cannot modify the property value when deleting it, otherwise serious problems will occur.

In fact, we can also take a look at8The object type corresponding to the basic data type and the hashCode and equals methods of the String type.

Among them8The hashCode of the basic type is very simple, it is just to return their numerical size directly, and the String object is through a complex calculation method, but this calculation method can ensure that if the value of the string is equal, their hashCode is equal.8The equals method of the basic type is a direct comparison of the value, and the equals method of the String type is a comparison of the value of the string.

That's all for this article, I hope it will be helpful to everyone's learning, and I also hope everyone will support the Yelling Tutorial more.

Declaration: The content of this article is from the Internet, the copyright belongs to the original author. The content is contributed and uploaded by Internet users spontaneously. This website does not own the copyright, has not been manually edited, and does not assume any relevant legal liability. If you find any content suspected of copyright infringement, please send an email to: notice#oldtoolbag.com (Please replace # with @ when sending an email to report abuse, and provide relevant evidence. Once verified, this site will immediately delete the infringing content.)