Programmers’ Growth Journey

Internet/Programmers/Technology/Resource Sharing

Reading this article will take approximately 5 minutes.

Source: github.com/feigeswjtu/java-basics/edit/master/sourceCode

Background

While reading the Alibaba Java Development Manual, I came across the usage specifications for the hashCode() and equals() methods.

• Whenever equals is overridden, hashCode must also be overridden.
• Since Set stores unique objects and uses hashCode and equals for comparison, objects stored in Set must override these two methods.
• If a custom object is used as a key in a Map, hashCode and equals must be overridden.

It also provided an example where String overrides the hashCode and equals methods, allowing us to happily use String objects as keys.

Let’s look at the source code for String’s hashCode() and equals() methods:

String’s hashCode()

hashCode():

    private int hash; // Default to 0
    public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            char val[] = value;

            for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }
            hash = h;
        }
        return h;
    }

We will not explain the code line by line, but from a coding perspective, we can learn some knowledge points.

• The importance of caching; the value attribute serves as cache here.
• In most cases, the cache is generated during use.
• When calculating the hash, a class’s own attribute values can be multiplied by 31.

Why 31, and not 32, 33, or other numbers?

• 31 is a prime number, and the property of prime numbers is that if I multiply a number by this prime, the resulting value can only be divided by the prime itself, the multiplicand, and 1.
• 31 can be represented as i*31 == (i<<5)-1, and many virtual machines have optimizations related to this.
• When choosing coefficients, one should choose as large a coefficient as possible. The larger the calculated hash address, the fewer so-called “collisions” will occur, thus improving search efficiency.
• Moreover, 31 only occupies 5 bits, reducing the probability of data overflow.

Next, we will discuss the design principles of hashCode and continue with the equals() method.

String’s equals()

    public boolean equals(Object anObject) {
        if (this == anObject) {
            return true;
        }
        if (anObject instanceof String) {
            String anotherString = (String)anObject;
            int n = value.length;
            if (n == anotherString.value.length) {
                char v1[] = value;
                char v2[] = anotherString.value;
                int i = 0;
                while (n-- != 0) {
                    if (v1[i] != v2[i])
                        return false;
                    i++;
                }
                return true;
            }
        }
        return false;
    }

The equals method does not require much explanation; the design principles of equals are addressed later. Let’s explain the characteristics of hashCode and equals methods based on three sentences from the developer manual, and why both methods must be overridden.

Whenever equals is overridden, hashCode must also be overridden

Let’s take an example: Person class:

public class Person {
    private String name;
    private int age;

    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public boolean equals(Object o){
        if(this == o){
            return true;
        }
        if(o instanceof Person){
            Person p = (Person)o;
            return this.age == p.getAge() && this.name.equals(p.getName());
        }
        return false;
    }
}

Running class:

public class Application {
    public static void main(String[]args){
        Set<Person> set = new HashSet<>();
        Person p1 = new Person("Lilei", 25);
        Person p2 = new Person("Lilei", 25);
        set.add(p1);
        System.out.println("p1 equals p2: " + (p1 == p2));//1
        System.out.println("set contains p1: " + set.contains(p1));//2
        System.out.println("set contains p2: " + set.contains(p2));//3
    }
}

Output:

p1 equals p2: false
set contains p1: true
set contains p2: false

As we can see, although p1 is equal to p2 (we have overridden the equals method in the Person class), after putting p1 into a Set, it cannot be retrieved with p2, but we want the effect to be that we can retrieve it with p2, which is a common scenario.

Because Set stores unique objects, and uses hashCode and equals for comparison, objects stored in Set must override these two methods

Using the previous example, if we do not override the equals method or the hashCode method in the Person class. Person class:

public class Person {
    private String name;
    private int age;

    public Person() {
    }

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }
}

Running class:

public class Application {
    public static void main(String[]args){
        Set<Person> set = new HashSet<>();
        Person p1 = new Person("Lilei", 25);
        Person p2 = new Person("Lilei", 25);
        set.add(p1);
        set.add(p2);
        System.out.println("set size is: " + set.size());
        //System.out.println("p1 equals p2: " + (p1 == p2));
        //System.out.println("set contains p1: " + set.contains(p1));
        //System.out.println("set contains p2: " + set.contains(p2));
    }
}

Running result:

set size is: 2

In a Set, objects must be unique. If we do not override the hashCode and equals methods in the Person class, both p1 and p2 can be placed in the Set object simultaneously. What if we only override the hashCode method of the Person class?

    @Override
    public int hashCode(){
        return name.hashCode() * 31 + age;
    }

Running result:

set size is: 2

Finally, let’s override the equals() method in the Person class:

    @Override
    public boolean equals(Object o){
        if(this == o){
            return true;
        }
        if(o instanceof Person){
            Person p = (Person)o;
            return this.age == p.getAge() && this.name.equals(p.getName());
        }
        return false;
    }

    @Override
    public int hashCode(){
        return name.hashCode() * 31 + age;
    }

Running result:

set size is: 1

If a custom object is used as a key in a Map, then hashCode() and equals() must be overridden

In fact, this point is similar to the second point; there is no need for further examples here.
In fact, the operations of Set objects and Map keys are related to the hashCode and equals methods, such as checking whether this object is in the Set, first locating a segment based on hashCode, and then determining whether it exists using equals, thus avoiding the need to traverse all objects in the Set, which would be inefficient. The same reasoning applies to Map keys.

Thus, the design principles of hashCode and equals are self-evident.

Design Principles of equals()

• Symmetry: If x.equals(y) returns true, then y.equals(x) should also return true.
• Reflexivity: x.equals(x) must return true.
• Transitivity: If x.equals(y) returns true and y.equals(z) returns true, then z.equals(x) should also return true.
• Consistency: If x.equals(y) returns true, as long as the contents of x and y remain unchanged, no matter how many times you repeat x.equals(y), it should always return true.
• Non-nullity: x.equals(null) should always return false; x.equals(an object of a different type than x) should always return false.

Design Principles of hashCode()

• During the execution of a Java application, if an object provides the information for equals comparisons without being modified, calling hashCode() on that object multiple times must always return the same integer.
• If two objects are equal according to the equals(Object) method, calling the hashCode() method on both must produce the same integer result.
• It is not required that two objects that are not equal according to the equals(java.lang.Object) method must produce different integer results when calling their respective hashCode() methods. However, programmers should be aware that producing different integer results for different objects can improve the performance of hash tables.

<END>

Recommended Reading:

[198] Interviewer: Can you explain the principles of method overloading and method overriding?

[197] Huawei OD Technical Interview Records, providing a reference for future candidates!

[196] Solidifying Fundamentals, Detailed Tutorial on Java 8’s New Features Stream

5T Technology Resources Giveaway! Including but not limited to: C/C++, Linux, Python, Java, PHP, Artificial Intelligence, Microcontrollers, Raspberry Pi, etc. Reply “2048” in the public account to get it for free!!

Scan the QR code to follow my public account

I have read