java - 当 "Set"不合适时，是否有替代 NavigableSet 的方法？

Question

NavigableSet接口(interface)提供了许多有用的方法，普通的 Set不会(具体来说，我正在考虑像 headSet 和 tailSet 这样的方法)。但是，作为 Set，它不支持重复元素。此外，作为 SortedSet ，排序必须与equals和hashCode保持一致，以免违反Set接口(interface)的约定。

当可能存在重复元素或多个元素根据自然顺序或比较器“相等”但根据 equals 方法不“相等”时，是否有任何好的替代数据结构？作为一个激励性的例子，请考虑以下代码，它显示了为什么 NavigableSet 不合适:

public class Foo implements Comparable<Foo>{
  double x;
  double y;

  @Override
  public int compareTo(Foo o) {
    return Double.compare(x, o.x);  // only x matters for sort order
  }

  public static void main(String...args){
    Foo a = new Foo();
    a.x = 1;
    a.y = 2;

    Foo b = new Foo();
    b.x = 1;
    b.y = 42;

    Foo c = new Foo();
    c.x = 2;
    c.y = 12.34;

    NavigableSet<Foo> set = new TreeSet<Foo>();
    set.add(a);
    set.add(a);
    set.add(b);
    set.add(c);

    System.out.println(set.size());
  }
}

请注意元素 a 只被添加一次(当然，因为这是一个 Set)。另外，请注意 b 没有被添加，因为已经有一个比较返回 0 的元素。

我觉得这可能是一件相当普遍的事情，所以我希望找到一个现有的实现而不是自己动手。是否有适合我的目的的良好、广泛使用的数据结构？

我要补充一点，在写这个问题时我确实遇到了 Biscotti Project ，但是 a) 我不相信它能解决比较/等于问题，并且 b) FAQ 明确表示使用它并不安全。

Answer 1

让我重新表述您的问题，以确保我理解清楚。需要 headSet 和 tailSet 意味着必须对集合进行排序。这与根据 compareTo 允许重复成员的需要有点冲突。

冲突来自此类集合的有效使用。使用O(log n) 中的compareTo 方法将成员添加到排序集合中 - 一种二进制搜索然后添加。 TreeSet 是使用 TreeMap 实现的，它不能根据 compareTo 来计算两个相同的成员。

您正在寻找的东西不会有效。

• 您可以尝试使用一个简单的ArrayList 并通过Collections.sort 对其进行排序，然后使用sublist 方法。问题在于它根本不处理重复项。
• 您还可以使用处理重复项的 LinkedHashSet(根据 equals() 并且它免疫 compareTo( ))，但未排序。当然，您可以通过在构造函数中传递实例，将 LinkedHashSet 实例转换为 SortedSet。