Why does Java need to rewrite hashcode when rewriting equals?

First let me tell you the conclusion:

We must first make it clear that rewriting equals does not necessarily require hashcode, it depends on the actual situation. For example, it is not necessary when a container is not used, but if a container such as HashMap is used, and a custom object is used as the Key, it must be rewritten.

(Learning video sharing: java video tutorial)

Rewriting equals is to determine whether instances are equal in business logic. The purpose of rewriting hascode is to quickly determine the weight of the collection.

The regulations of hashCode() and equals():

1. If two objects are equal, the hashcode must also be the same
2. Two objects are equal, for two equals () method returns true
3. Two objects have the same hashcode value, and they are not necessarily equal
4. In summary, if the equals() method has been overridden, the hashCode() method must also be Override
5. The default behavior of hashCode() is to produce unique values ​​for objects on the heap. If hashCode() is not overridden, no two objects of this class will be equal anyway (even if the two objects point to the same data).

The following is an example to illustrate the need to rewrite.

When using a custom class as the key of HashMap when putting

If you only rewrite equals but not hashCode, a logic error will occur

Look at the following code first

public class Test {

    static class Order {
    
        private Long orderId;

        public Order(Long orderId) {
            this.orderId = orderId;
        }

        public Long getOrderId() {
            return orderId;
        }

        public void setOrderId(Long orderId) {
            this.orderId = orderId;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj != null && !(obj instanceof Order)) {
                return false;
            }

            return Objects.equals(this.orderId, ((Order) obj).orderId);
        }

        @Override
        public String toString() {
            return "Order{" +
                    "orderId=" + orderId +
                    '}';
        }
    }

    public static void main(String[] args) {
        Map<Order, String> map = new HashMap<>();

        Order order1 = new Order(1000000001L);
        Order order2 = new Order(1000000001L);

        map.put(order1, "");
        map.put(order2, "");

        System.out.println(map);
    }
}

Run output:

{Order{orderId=1000000001}=, Order{orderId=1000000001}=}

The equals method is rewritten in the code, but the hashCode method is not rewritten.
The logic of equals rewriting is: as long as the orderId is equal, the two objects are equal.
Judging from the running results, the two objects with the same orderId were successfully put into the map. This is a logical error, because logically the expected result should be that there is only one Order in the map.
Let’s take a look at the source code of HashMap
Just look at the judgment with comments

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
     int h;
     return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 通过hash算出索引  通过索引取值==null的话  直接直接插入到索引位置。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

We know from the source code that as long as the hash code is different, it can be directly inserted into the array. However, precisely because we did not override the hashCode method, the hashCode method of Object is called. The hashCode of Object uses the address of the object in the heap to derive an int type value through an algorithm. In this case, the int type values ​​​​of the two objects just created must be different, so both Orders can be inserted normally. into the array, resulting in a logic error.

Rewrite the hashCode method:

public class TestHash {

    static class Order {


        private Long orderId;

        public Order(Long orderId) {
            this.orderId = orderId;
        }

        public Long getOrderId() {
            return orderId;
        }

        public void setOrderId(Long orderId) {
            this.orderId = orderId;
        }

        @Override
        public boolean equals(Object obj) {
            if (obj != null && !(obj instanceof Order)) {
                return false;
            }

            return Objects.equals(this.orderId, ((Order) obj).orderId);
        }

        @Override
        public int hashCode() {
        	// 这里简单重写下   实际开发根据自己需求重写即可。
            return this.orderId.intValue() >> 2;
        }

        @Override
        public String toString() {
            return "Order{" +
                    "orderId=" + orderId +
                    '}';
        }
    }

    public static void main(String[] args) {
        Map<Order, String> map = new HashMap<>();

        Order order1 = new Order(1000000001L);
        Order order2 = new Order(1000000001L);

        map.put(order1, "");
        map.put(order2, "");

        System.out.println(map);
    }
}

Run the output again:

{Order{orderId=1000000001}=}

Let’s take a brief look at the source code (for better understanding, I only intercepted the key code): Put order2 Explained as a comment.

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 重写hashCode之后两个对象的orderId相同，hashCode也肯定相同。
    // 通过hash算出索引  通过索引取值  有值不进入if。
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 由于重写了hashCode  旧对象的hashCode和新的肯定相等
        if (p.hash == hash &&
        // (k = p.key) == key == false 因为比较的是对象地址
        // (key != null && key.equals(k)) == true 因为重写了equals orderId相等则相等 
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 保存旧Node
            e = p;
        .......
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
            	// value覆盖旧Node的值
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
   ........
}

So order2 covers order1. This is why when using a custom object as the key of a HashMap, if you override equals, you must also hashCode.

Conversely speaking: after rewriting hashCode, does equals need to be rewritten?

The answer is yes, all must be rewritten!

Let’s take the logic of rewriting the above code as an example. Assume that there are two objects with the same hashCode, and order1 has been put. When putting, the hash is the same, and the resulting index is also the same, then order1 can be obtained. After that, equals will continue to be used for comparison. Assuming there is no rewriting, it will be object address comparison. The result must be false. Then a hash collision will occur at this time, and a linked list will be formed.

Also in map.get(key), it will be searched based on hashCode and then equals will be determined.
Why should we judge equals? Because what is found based on hashCode is a linked list, you need to find the value with equal Key in the linked list based on equals.

What scenarios would use custom classes as keys?

The most common key is a coordinate, such as placing an object at a certain coordinate on the map.

public class Test {

    static class Coordinate {
        public Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }

        private int x;
        private int y;

        public int getX() {
            return x;
        }

        public void setX(int x) {
            this.x = x;
        }

        public int getY() {
            return y;
        }

        public void setY(int y) {
            this.y = y;
        }
    }

    public static void main(String[] args) {
        Map<Coordinate, String> map = new HashMap<>();
        map.put(new Coordinate(22, 99), "手机");
        map.put(new Coordinate(44, 48), "电脑");
    }
}

Related recommendations: java introductory tutorial

The above is the detailed content of Why does Java need to rewrite hashcode when rewriting equals?. For more information, please follow other related articles on the PHP Chinese website!