踩坑实录1

起因

今天在做365. 水壶问题 - 力扣（LeetCode）时想把一个二元组放进一个 HashSet 中进行去重，由于 JDK 中没有 C++ STL 中那样现成的 Pair 类，所以我最开始使用了 int[] 类型作为 HashSet 中的元素类型。结果在某个用例时进了死循环，排查后发现是 HashSet 没有如我设想那样对 int[] 类型的元素去重

现象

考虑下面这两段代码，看看输出是不是符合你的预设

public static void main(String[] args) {
	Set<int[]> set = new HashSet<>();
	int[] arr1 = new int[]{1, 1};
	int[] arr2 = new int[]{1, 1};
	set.add(arr1);
	set.add(arr2);
	System.out.println(set.size());
}
// output
// 2

public static void main(String[] args) {
	Set<int[]> set = new HashSet<>();
	int[] arr1 = new int[]{1, 1};
	int[] arr2 = new int[]{1, 1};
	set.add(arr1);
	System.out.println(set.contains(arr2));    
}
// output
// false

解释

HashSet 没有对 int[] 类型的元素进行「去重」是因为数组类型并没有重载 equals() 方法。

我们知道，Java 中的数组类型被视为对象，是被创建在堆上的^[1]。既然是对象，那就继承了 Object 超类的 equals() 方法，这个方法是默认是比较元素的引用（即元素的地址）。

Set 类的 add() 或者 contains() 方法是调用对应元素类型的 equals() 方法对元素进行比较。由于 int[] 类型没有重载这个方法，因此还是以地址进行比较，arr1 和 arr2 是创建在堆上的不同位置的，故 arr1.equals(arr2) 返回 false

（arr1.equals(arr2) 等价于 arr1 == arr2）

解决

如果一定要利用 Set 对二元组进行去重，可以考虑 Set<List<Integer>>^[2]，List<> 类型重载了 equals() 方法，并且是按照顺序对其中的元素进行比较。

public static void main(String[] args) {
	Set<List<Integer>> set = new HashSet<>();
	set.add(Arrays.asList(1, 1));
	set.add(Arrays.asList(1, 1));
	System.out.println(set.size());
}
// output
// 1

如果要对 int[] 类型进行比较，要使用 Arrays 工具类中的 Arrays.equals() 方法^[3]。该方法也是按顺序对两个数组的元素进行依次比较

public static void main(String[] args) {
	int[] arr1 = new int[]{1, 1};
	int[] arr2 = new int[]{1, 1};
	System.out.println(Arrays.equals(arr1, arr2));
}
// output
// true

1. [Chapter 10. Arrays (oracle.com)](https://docs.oracle.com/javase/specs/jls/se7/html/jls-10.html#:~:text=In the Java programming language,be invoked on an array.) ↩
2. arrays - java Set vs Set> - Stack Overflow ↩
3. equals vs Arrays.equals in Java - Stack Overflow ↩