【Java】以HashSet为例讲解正确实现hashCode和equals方法的重要性

在Java 8之前，HashSet的内部实现是基于一个数组和链表的组合实现的。具体来说， HashSet使用一个Entry数组来存储元素，每个Entry对象包含了一个元素的哈希码、键和值。当多个元素被分配到同一个桶中时，它们将以链表的形式存储在该桶中。 HashSet使用链表来解决哈希冲突，当桶中已经存在一个元素时，新的元素将被插入到链表的头部。

但是，在Java 8之后，HashSet的内部实现进行了改进，现在使用了一个数组和红黑树的组合实现。当一个桶中的元素数量超过一个阈值（默认是8）时， HashSet会将链表转化为红黑树，以提高查找效率。这个改进在Java 8中引入，也被称为“链表转红黑树优化”。

因此，HashSet的内部实现可以说是由一个数组实现的，每个数组元素对应一个桶，桶中存储了哈希值相同的元素，每个元素包含键和值。当多个元素被分配到同一个桶中时，它们可能以链表或红黑树的形式存储在该桶中，具体取决于元素数量和元素分布情况。

在HashSet中，桶是指用来存储元素的数组。 HashSet内部实现了一个哈希表，它包含了多个桶。每个桶中存储了哈希值相同的元素。当HashSet需要查找一个元素时，它会首先计算该元素的哈希码，然后根据哈希码确定该元素所在的桶，最后在桶中查找该元素。

为了提高HashSet的性能，我们应该尽可能地减少哈希冲突。一种方法是实现一个好的hashCode()方法，它可以将不同的对象映射到不同的哈希码。另一种方法是调整HashSet的容量和负载因子，以确保它能够容纳所有的元素并且哈希冲突较少。

需要注意的是，当HashSet中的元素数量增加时，桶的数量也会增加。这会导致HashSet需要重新计算元素的哈希码，并重新分配到桶中。如果HashSet中的元素数量变得很大，这可能会导致性能下降。因此，我们应该根据具体的应用场景来选择合适的HashSet容量和负载因子，以便在性能和内存使用之间取得一个平衡。

看下面这两个情况：

1. 如果两个对象的hashCode不同，但它们的equals方法返回true ，则这两个对象会被视为不同的对象。这是因为HashSet在添加元素时首先会根据元素的hashCode确定其所在的桶，如果两个对象的hashCode不同，它们就会被分配到不同的桶中，即使它们的equals方法返回true。
2. 如果两个对象的hashCode相同但equals()方法返回false，则它们被视为不同的对象。

举例说明

LeetCode 356. Line Reflection

Given n points on a 2D plane, find if there is such a line parallel to the y-axis that reflects the given points symmetrically.

In other words, answer whether or not if there exists a line that after reflecting all points over the given line, the original points' set is the same as the reflected ones.

Note that there can be repeated points.

Example 1:

Input: points = [[1,1],[-1,1]]
Output: true
Explanation: We can choose the line x = 0.

Example 2:

Input: points = [[1,1],[-1,-1]]
Output: false
Explanation: We can't choose a line.

错误写法：

不overide Point类的hashCode和equals方法，则在HashSet中x，y值相同的Point被视为不同对象。

class Solution {
    public boolean isReflected(int[][] points) {
        HashSet<Point> set = new HashSet<>();
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int[] point : points) {
            set.add(new Point(point[0], point[1]));
            min = Math.min(min, point[0]);
            max = Math.max(max, point[0]);
        }
        int sum = min + max;
        for (int[] point : points) {
            Point reflection = new Point(sum - point[0], point[1]);
            if (!set.contains(reflection)) {
                return false;
            }
        }
        return true;
    }
}

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

正确写法：

如果要确保将各参数值相同的 Point视为同一个对象，则需要覆盖hashCode和equals方法。这样，当Point对象的各个参数值相同时，它们将具有相同的哈希码和相等性。

class Solution {
    public boolean isReflected(int[][] points) {
        HashSet<Point> set = new HashSet<>();
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int[] point : points) {
            set.add(new Point(point[0], point[1]));
            min = Math.min(min, point[0]);
            max = Math.max(max, point[0]);
        }
        int sum = min + max;
        for (int[] point : points) {
            Point reflection = new Point(sum - point[0], point[1]);
            if (!set.contains(reflection)) {
                return false;
            }
        }
        return true;
    }
}

class Point {
    int x, y;
    public Point(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;
        Point other = (Point) obj;
        if (x != other.x)
            return false;
        if (y != other.y)
            return false;
        return true;
    }
}