TreeSet Comparator 在某些情况下无法删除重复项？

Question

我的 TreeSet 有以下比较器：

public class Obj {
    public int id;
    public String value;
    public Obj(int id, String value) {
        this.id = id;
        this.value = value;
    }
    public String toString() {
        return "(" + id + value + ")";
    }
}

Obj obja = new Obj(1, "a");
Obj objb = new Obj(1, "b");
Obj objc = new Obj(2, "c");
Obj objd = new Obj(2, "a");
Set<Obj> set = new TreeSet<>((a, b) -> {
    System.out.println("Comparing " + a + " and " + b);
    int result = a.value.compareTo(b.value);
    if (a.id == b.id) {
        return 0;
    }
    return result == 0 ? Integer.compare(a.id, b.id) : result;
});
set.addAll(Arrays.asList(obja, objb, objc, objd));
System.out.println(set);

它打印出 [(1a), (2c)]，删除了重复项。

但是当我将最后一个Integer.compare更改为Integer.compare(b.id, a.id)（即调换a和b的位置）时，它会打印出[(2a), (1a), (2c)]。明明同一个id 2出现了两次

如何修复比较器以始终根据 id 删除重复项并根据值（升序）然后 id（降序）对有序集进行排序？

Answer 1

你问的是：
如何修复比较器以始终根据 id 删除重复项并根据值（升序）然后 id（降序）对有序集进行排序？

您希望比较器

根据Obj.id删除重复项
按 Obj.value 和 Obj.id

要求 1) 导致

Function<Obj, Integer> byId = o -> o.id;
Set<Obj> setById = new TreeSet<>(Comparator.comparing(byId));

要求 2) 导致

Function<Obj, String> byValue = o -> o.value;
Comparator<Obj> sortingComparator =  Comparator.comparing(byValue).thenComparing(Comparator.comparing(byId).reversed());
Set<Obj> setByValueAndId = new TreeSet<>(sortingComparator);

让我们看看TreeSet的JavaDoc。它说：

Note that the ordering maintained by a set [...] must be consistent with equals if it is to correctly implement the Set interface. This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.

集合将根据比较器排序，但它的元素也会使用比较器比较是否相等。

据我所知，无法定义满足这两个要求的 Comparator。由于 TreeSet 首先是 Set 要求 1) 必须匹配。要实现要求 2)，您可以创建第二个 TreeSet:

Set<Obj> setByValueAndId = new TreeSet<>(sortingComparator);
setByValueAndId.addAll(setById);

或者，如果您不需要集合本身，而是按所需顺序处理元素，您可以使用 Stream:

Consumer<Obj> consumer = <your consumer>;
setById.stream().sorted(sortingComparator).forEach(consumer);

顺便说一句：
虽然可以根据给定的 Comparator 对 Stream 的元素进行排序，但没有 distinct 方法采用 Comparator 来根据它删除重复项。

编辑：
您有两个不同的任务：1. 重复删除，2. 排序。一个 Comparator 不能解决两个任务。那么还有哪些选择呢？

您可以在 Obj 上覆盖 equals 和 hashCode。然后可以使用 HashSet 或 Stream 来删除重复项。
对于排序，您仍然需要 Comparator （如上所示）。根据 Comparable JavaDoc.

实施 Comparable 只是为了排序将导致排序不是 "consistent with equals"

既然 Stream 可以解决这两个任务，那将是我的选择。首先我们覆盖 hashCode 和 equals 以通过 id:

识别重复项

public int hashCode() {
    return Integer.hashCode(id);
}

@Override
public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Obj other = (Obj) obj;
    if (id != other.id)
        return false;
    return true;
}

现在我们可以使用 Stream:

// instantiating one additional Obj and reusing those from the question
Obj obj3a = new Obj(3, "a");

// reusing sortingComparator from the code above
Set<Obj> set = Stream.of(obja, objb, objc, objd, obj3a)
        .distinct()
        .sorted(sortingComparator)
        .collect(Collectors.toCollection(LinkedHashSet::new));

System.out.println(set); // [(3a), (1a), (2c)]

返回的 LinkedHashSet 具有 Set 的语义，但它还保留了 sortingComparator.

的顺序

编辑（回答评论中的问题）

问：为什么没有正确完成作业？
你自己看看吧。像下面这样更改 Comparator 的最后一行

int r = result == 0 ? Integer.compare(a.id, b.id) : result;
System.out.println(String.format("a: %s / b: %s / result: %s -> %s", a.id, b.id, result, r));
return r;

运行代码一次，然后切换Integer.compare的操作数。开关导致不同的比较路径。区别在于比较 (2a) 和 (1a) 时。

在第一个运行中，(2a) 大于 (1a)，因此它与下一个条目 (2c) 进行比较。这导致相等 - 找到重复项。

第二个运行 (2a)小于(1a)。因此 (2a) 将作为下一个与上一个条目进行比较。但是(1a)已经是最小的条目了，没有前面的了。因此，没有找到 (2a) 的重复项，并将其添加到集合中。

问：你说一个比较器不能完成两个任务，我的第一个比较器实际上完成了两个任务。
是的 - 但仅适用于给定的示例。像我一样将 Obj obj3a 添加到集合中，并运行您的代码。返回的排序集为：

[(1a), (3a), (2c)]

这违反了按 id 降序排列相等 value 的要求。现在它上升 id。运行我的代码和它 returns 正确的顺序，如上所示。

_{前段时间与 Comparator 作斗争时，我收到了以下评论：“...这是一个很好的练习，展示了手动比较器实现有多么棘手...”（)}

TreeSet Comparator 在某些情况下无法删除重复项？

TreeSet Comparator failed to remove duplicates in some cases?

java

sorting

comparator

treeset