获取LinkedHashSet的子列表最后5个元素？

Question

是否有一个衬垫可以在新的 LinkedHashSet 中获取 LinkedHashSet 的最后 5 个元素？

这是我目前拥有的，但效率不是很高：

new LinkedHashSet<String>(new LinkedList<String>(set)
.subList(Math.max(0, set.size() - 5), set.size());

或者我应该在这种情况下使用 TreeSet、SortedSet、HashSet 吗？

Answer 1

如果您使用 Java 8 并且可以返回

HashSet

（而不是

LinkedHashSet

），则可以使用 Stream API：

Set<String> newSet = set.stream()
                        .skip(set.size() - 5)
                        .collect(Collectors.<String>toSet());

Answer 2

使用

ArrayList

你可以获得更好的性能:

long s1 = System.nanoTime();
LinkedHashSet<String> last5 = new LinkedHashSet<String>(new LinkedList<String>(set)
        .subList(Math.max(0, set.size() - 5), set.size()));
System.out.println(System.nanoTime() - s1);

s1 = System.nanoTime();
LinkedHashSet<String> usingArrayList = new LinkedHashSet<String>(new ArrayList<String>(set)
        .subList(Math.max(0, set.size() - 5), set.size()));
System.out.println(System.nanoTime() - s1);

Answer 3

问题来了。

LinkedHashSet

的迭代器是单向的；即，即使底层数据结构具有双向链表，也无法向后迭代。这意味着要获取最后的 N，您需要迭代到列表的末尾。那就是

O(N)

。

在您的算法中，

LinkedList

构造函数正在使用（可能）迭代器将集合复制到新的数据结构中。

相比之下，

TreeSet

API 有一个

descendingIterator()

方法，该方法返回一个向后迭代列表的

Iterator

。如果使用正确，您可以在

O(1)

中获取该集合的最后 5 个元素。缺点是，对于基于哈希的集合，向集合中添加元素将是

O(logN)

，而不是

O(1)

。

Answer 4

我最终使用了这个：

com.google.common.collect.EvictingQueue<E>

这样你就可以只保留 最后 x 个元素。

EvictingQueue<String> queue = EvictingQueue.create(5);

Answer 5

这可以使用作为

reversed()

接口的一部分添加到 Java 21 中

LinkedHashSet

的

SequencedSet

方法来有效实现。

LinkedHashSet<String> lastFive = new LinkedHashSet<>(set.reversed().stream()
        .limit(5).toCollection(LinkedHashSet::new).reversed());

如果返回的集合不需要是

reversed

，而只是一个具有明确定义的迭代顺序和几乎相同的特征的可变

Set

，则可以简化为直接使用

LinkedHashSet

Set

LinkedHashSet

：

SequencedSet<String> lastFive = set.reversed().stream()
        .limit(5).toCollection(LinkedHashSet::new).reversed();