TreeSet 忽略值

Question

我正在尝试创建一个 class 给定字符串对，并告知其中一个比另一个“更大”，然后保持所有已知字符串的运行顺序。

为了做到这一点，我保留了一个 Map<String, Set<String>> 将给定的 String 映射到它大于的所有值，然后我创建了一个 TreeSet 和一个使用该数据的比较器比较两个字符串。

这是我的 class:

public class StringSorter {

    private Map<String, Set<String>> greaterThan = new HashMap<>();
    private SortedSet<String> order;

    public StringSorter() {
        order = new TreeSet<>((o1, o2) -> {
            if (greaterThan.getOrDefault(o1, Collections.emptySet()).contains(o2))
                return 1;
            else if (greaterThan.getOrDefault(o2, Collections.emptySet()).contains(o1))
                return -1;
            return 0;
        });
    }

    public void addRule(String bigger, String smaller) {

        if (!greaterThan.containsKey(bigger))
            greaterThan.put(bigger, new HashSet<>());
        greaterThan.get(bigger).add(smaller);

        order.add(bigger);
        order.add(smaller);
    }

    public SortedSet<String> getOrder() {
        return order;
    }
}

但是，出于某种原因，TreeSet 似乎忽略了许多添加到其中的值。

示例：

StringSorter sorter = new StringSorter();
sorter.addRule("one", "two");
sorter.addRule("two", "three");
sorter.addRule("three", "four");
System.out.println(sorter.getOrder());

输出：

[two, one]

字符串 three 和 four 发生了什么？

Answer 1

问题是集合保持唯一值。调试比较器后，您会看到 "three" 被评估为等于 "one"，因此禁止将其添加到集合中。

考虑这个修改：

public StringSorter() {
    order = new TreeSet<>((o1, o2) -> {
        if (greaterThan.getOrDefault(o1, Collections.emptySet()).contains(o2))
            return 1;
        else if (greaterThan.getOrDefault(o2, Collections.emptySet()).contains(o1))
            return -1;
        else if(o1.equals(o2)) return 0;
        else return -1; //or 1, or o1.compareTo(o2)
    });
}

我们首先检查对象是否相等，而不是只返回 0，如果不相等，则比较本身是无关紧要的，结果可能是任意的。

这是使用更新的比较器时的输出：

[four, three, two, one]

[编辑]

我会考虑将规则的内部表示更改为面向自定义的树数据结构，由稀疏邻接矩阵表示。

Answer 2

您可以通过将此行添加到您的 Comparator.compare lambda 来自己回答这个问题：

System.out.printf("(%s, %s)%n", o1, o2);

如您所见，无法保证相邻值会传递给比较器。当 o1 是 "three" 并且 o2 是 "one" 时，比较回落到返回零，这告诉 TreeSet 这两个值是相等的，显然它不会添加一个它认为等于集合中已有值的值。

您需要使 greaterThan 的遍历具有传递性。我很确定它需要递归：

private boolean isGreater(String o1,
                          String o2,
                          Set<String> keysTried) {
    Set<String> greaterSet = greaterThan.get(o1);
    if (greaterSet == null) {
        return false;
    }

    if (greaterSet.contains(o2)) {
        return true;
    }

    for (String g : greaterSet) {
        if (keysTried.add(g) && isGreater(g, o2, keysTried)) {
            return true;
        }
    }

    return false;
}

public StringSorter() {
    order = new TreeSet<>((o1, o2) -> {
        if (isGreater(o1, o2, new HashSet<>())) {
            return 1;
        } else if (isGreater(o2, o1, new HashSet<>())) {
            return -1;
        } else {
            return 0;
        }
    });
}

keysTried的目的是防止无限递归。（理论上，如果 greaterThan 是有向图，那无论如何都不会发生。）

TreeSet 忽略值

TreeSet ignoring values

java

sorting

treeset