Java TreeSet结合Comparator处理非唯一值的实现方案

问题分析 #

当前getComparator()仅比较区间长度，而TreeSet判定元素重复的依据是Comparator返回0（而非equals()方法）。这导致只要区间长度相同，哪怕左右边界不同的LongRange对象都会被视为重复元素，从而被过滤。

需要按照以下排序规则修改Comparator，同时确保只有完全相同的区间才会被判定为重复：

• 优先按区间长度升序排列（短区间在前）
• 长度相同时，按左边界升序排列（左边界小的在前）
• 若长度和左边界都相同，再按右边界区分（确保非完全相同的区间不会被判定为重复）

修改后的代码 #

修改getComparator()方法，使用thenComparing()链式添加比较条件：

import java.util.*;

class LongRange {

    public static void main(String[] args) {
        Set<LongRange> numbers = new TreeSet<>(LongRange.getComparator());

        numbers.add(new LongRange(0, 5));
        numbers.add(new LongRange(2, 4));
        numbers.add(new LongRange(1, 4));
        numbers.add(new LongRange(1, 7));
        numbers.add(new LongRange(3, 5));
        numbers.add(new LongRange(-10, 1));
        numbers.add(new LongRange(-20, -9));
        numbers.add(new LongRange(-21, -10));

        numbers.forEach(System.out::println);
    }

    private final long left;
    private final long right;

    public static Comparator<LongRange> getComparator() {
        return Comparator.comparingLong((LongRange range) -> Math.subtractExact(range.right, range.left))
                .thenComparingLong(LongRange::getLeft)
                .thenComparingLong(LongRange::getRight);
    }

    public LongRange(long left, long right) {
        this.left = left;
        this.right = right;
    }

    public long getLeft() {
        return left;
    }

    public long getRight() {
        return right;
    }

    @Override
    public boolean equals(Object other) {
        if (this == other) {
            return true;
        }
        if (other == null || getClass() != other.getClass()) {
            return false;
        }
        LongRange longRange = (LongRange) other;
        return left == longRange.left &&
                right == longRange.right;
    }

    @Override
    public int hashCode() {
        return Objects.hash(left, right);
    }

    @Override
    public String toString() {
        return String.format("%d %d", left, right);
    }
}

代码解释 #

1. comparingLong((LongRange range) -> Math.subtractExact(range.right, range.left))：
   • 先按区间长度升序排序，Math.subtractExact避免long溢出问题，确保长度计算准确。
2. thenComparingLong(LongRange::getLeft)：
   • 长度相同时，按左边界升序排列，满足左边界小的在前的要求。
3. thenComparingLong(LongRange::getRight)：
   • 当长度和左边界都相同时，比较右边界。只有当左右边界都完全相同时，Comparator才会返回0，此时TreeSet才会判定为重复元素，避免了非重复区间被过滤的问题。

运行结果 #

执行后会输出所有添加的区间，按规则排序：

2 4
3 5
1 4
-21 -10
-20 -9
0 5
-10 1
1 7

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