如何去除ArrayList中Edge对象的重复项？HashSet去重失败

哦，我懂你碰到的麻烦了——本来以为用HashSet能轻松去重，结果完全没生效对吧？问题出在两个关键点上：HashSet判断元素重复的依据不是Comparable接口，而是equals()和hashCode()方法，另外你当前的compareTo实现也有瑕疵。

为什么HashSet没起作用？ #

HashSet（以及所有基于哈希的集合）判断两个元素是否重复，是先通过hashCode()生成哈希值比较，如果哈希值相同，再调用equals()方法确认是否真的相等。而Comparable接口的核心作用是给元素排序（比如用于TreeSet或者Collections.sort()），和去重判断没有直接关系。你现在的Edge类只实现了compareTo，但没重写equals和hashCode，所以HashSet会默认用Object类的这两个方法——也就是只有当两个对象是同一个内存引用时才会被视为重复，显然这不是你想要的。

正确的解决方案 #

第一步：重写Edge类的equals()和hashCode()

这是去重的核心，必须保证逻辑一致：如果两个Edge对象的顶点相同（注意是否是无向边的情况），就视为相等，并且生成相同的哈希值。

import java.util.Objects;

public class Edge implements Comparable<Edge>{
    private int vertex1, vertex2;

    // 构造方法、Getter方法...
    public Edge(int vertex1, int vertex2) {
        this.vertex1 = vertex1;
        this.vertex2 = vertex2;
    }

    public int getVertex1() {
        return vertex1;
    }

    public int getVertex2() {
        return vertex2;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true; // 同一对象直接返回true
        if (o == null || getClass() != o.getClass()) return false; // 类型不同返回false
        Edge edge = (Edge) o;
        // 如果你处理的是**无向边**，要把(1,2)和(2,1)视为同一元素，就用下面的逻辑：
        // return (vertex1 == edge.vertex1 && vertex2 == edge.vertex2) 
        //         || (vertex1 == edge.vertex2 && vertex2 == edge.vertex1);
        // 如果你处理的是**有向边**，就用下面的逻辑：
        return vertex1 == edge.vertex1 && vertex2 == edge.vertex2;
    }

    @Override
    public int hashCode() {
        // 和equals逻辑保持一致：
        // 无向边的哈希值生成方式：
        // return Objects.hash(Math.min(vertex1, vertex2), Math.max(vertex1, vertex2));
        // 有向边的哈希值生成方式：
        return Objects.hash(vertex1, vertex2);
    }

    @Override
    public int compareTo(Edge o) {
        // 优化排序逻辑，原来的实现只在完全相同时返回0，其他都返回1，排序会出问题
        int vertex1Compare = Integer.compare(this.vertex1, o.getVertex1());
        if (vertex1Compare != 0) {
            return vertex1Compare;
        }
        return Integer.compare(this.vertex2, o.getVertex2());
    }
}

第二步：选择一种方式去重

有两种常用的去重方式，根据你的Java版本选择：

方式1：使用HashSet转换

适合所有Java版本，简单直接：

ArrayList<Edge> edges = new ArrayList<>();
// 填充edges（可能包含重复元素）...

// 利用HashSet自动去重，再转回ArrayList
ArrayList<Edge> uniqueEdges = new ArrayList<>(new HashSet<>(edges));

方式2：使用Stream API（Java 8+）

代码更简洁，还可以结合其他操作：

import java.util.stream.Collectors;

ArrayList<Edge> edges = new ArrayList<>();
// 填充edges...

ArrayList<Edge> uniqueEdges = edges.stream()
    .distinct() // 依赖equals和hashCode去重
    .collect(Collectors.toCollection(ArrayList::new));

额外提醒 #

• 如果是无向边，一定要记得在equals和hashCode里处理双向顶点的情况，不然(1,2)和(2,1)会被当成不同的元素保留下来。
• 你的compareTo方法原来的实现不符合排序逻辑，会导致排序结果混乱，建议替换成示例里的逻辑，先比较第一个顶点，再比较第二个顶点。

内容的提问来源于stack exchange，提问作者Adrien Varet