Java中自定义比较器的TreeSet判断列表是否存在结果错误如何解决

问题原因 #

• TreeSet的元素相等判断完全依赖传入的Comparator的返回值，只要compare方法返回0，TreeSet就判定两个元素是同一个，和元素本身的equals方法无关。
• 你写的Comparator存在逻辑错误：循环遍历列表元素时，只要当前索引位的两个元素相等，就直接返回了0，不会继续比较后续索引位的元素，更不会判断列表长度。
  你提供的测试用例里，[1,2,3]和[1,2,3,4]比较时，第一个元素都是1，触发了else分支直接返回0，TreeSet就误判两个列表是同一个元素，所以contains返回了true。

修复方案 #

只需要修改compare方法的循环逻辑：当前索引位元素相等时，不要直接返回，继续比较下一位即可，所有公共长度的元素都比较完相等后，再按长度比较返回结果。
修复后的完整代码如下：

public static void main(String[] args) {
    // 创建TreeSet
    TreeSet<ArrayList<Integer>> H = new TreeSet<ArrayList<Integer>>(new Comparator<ArrayList<Integer>>() {
        @Override
        public int compare(ArrayList<Integer> o1, ArrayList<Integer> o2) {
            // 先比较所有公共索引位的元素
            for (int i = 0; i < Math.min(o1.size(), o2.size()); ++i) {
                if (o1.get(i) < o2.get(i)) {
                    return -1;
                } else if (o1.get(i) > o2.get(i)) {
                    return 1;
                }
                // 相等的情况不返回，继续比较下一位
            }
            // 公共位元素全部相等，再比较长度
            return Integer.compare(o1.size(), o2.size());
        }
    });

    ArrayList<Integer> A = new ArrayList<>();
    A.add(1);
    A.add(2);
    A.add(3);
    H.add(A);

    ArrayList<Integer> B = new ArrayList<>();
    B.add(1);
    B.add(2);
    B.add(3);
    B.add(4);
    System.out.println(H.contains(B));  // 修复后输出false
}

内容的提问来源于stack exchange，提问作者Aayush Saini