java - 在某些情况下，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);

让我们看看 JavaDoc的 TreeSet .它说:

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);

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

编辑:
您有两个不同的任务:1. 重复删除，2. 排序。一 Comparator不能同时解决这两个任务。那么有哪些替代方案呢？

您可以覆盖 equals和 hashCode在 Obj .然后是 HashSet或 Stream可用于删除重复项。
对于排序，您仍然需要一个 Comparator (如上图所示)。实现 Comparable根据 Comparable，仅用于排序会导致排序不“与等于一致” JavaDoc .

自 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 的顺序.

编辑(回答评论中的问题)

Q:为什么没有正确完成工作？
自己看吧。更改您的 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)将作为 next 与前一个条目进行比较。但是(1a)已经是最小的条目并且没有前一个条目。因此没有发现 (2a) 的重复项并将其添加到集合中。

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

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

这违反了您对相等进行排序的要求 value s 降序 id .现在它上升了 id .运行我的代码，它返回正确的顺序，如上所示。

挣扎于Comparator前段时间我收到了以下评论:“……这是一个很好的练习，展示了手动比较器实现是多么棘手……”(source)