0

在下面的代码中，如果参数是{1,3,2}，在while循环中，i是1,3,2。

我已经在使用LinkedHashSet，为什么顺序不是1、2、3？我还需要做什么才能使迭代按升序排列？

不能TreeSet在add, remove, contains()o(log n) 时间内使用。

public static void iterate(int[] num) {
    LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();

    for (int i : num) {
        set.add(i);
    }

    Iterator<Integer> iter = set.iterator();
    while (iter.hasNext()) {
        // WHY IS i THE SAME ORDER AS INSERATION ORDER, NOT ASSENDING ORDER?
        int i = iter.next();
    }
}
4

3 回答 3

5

因为 LinkedHashSet 以插入顺序迭代并且没有排序！从javadoc：

此实现与 HashSet 的不同之处在于它维护一个双向链表，该列表贯穿其所有条目。该链表定义了迭代顺序，即元素插入集合的顺序（插入顺序）。

您将希望将 TreeSet 用于排序集，请查看排序集 javadoc：https ://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html

于 2014-11-13T13:46:52.227 回答
1

因此，您需要一个 HashSet 来快速contains正确地看到 LinkedHashSet 维护一个额外的数据结构，不幸的是通过插入进行排序。

如果上面的代码显示了所有的插入，你可以提前对插入的数据进行排序：

Arrays.sort(num);
Collections.addAll(set, num);

更通用的解决方案是之后将集合复制到新集合并对其进行排序。

如果数字在特定范围内，尤其是正数且不稀疏，则可以使用BitSet。如果适用，这确实是一个高性能的解决方案。

于 2014-11-13T13:57:53.473 回答
1

没有在返回迭代器之前进行排序的 Java 实现。TreeSet由于它们的数据结构，只有这样的实现是排序的。

在某些时候必须进行排序。不可能有支持恒定时间adding和getting固有排序的（哈希）实现。如果存在这样的事情，那么我们将能够在恒定时间内进行排序。

如果您想继续使用Hash-Implementation，那么您必须在检索元素之前/之后直接进行“排序工作”。由于您无法更改，唯一的解决方案是对检索元素before进行排序。after

番石榴订购的示例代码：

while (Integer i : Ordering.natural().sortedCopy(hashSet)) {
    // "i" in sorted order
}
于 2014-11-13T14:43:02.117 回答