获取 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() 方法，returns 一个 Iterator 向后遍历列表。如果你正确使用它，你可以在 O(1) 中获得集合的最后 5 个元素。不利之处在于，对于基于散列的集合，向集合中添加元素将是 O(logN) 而不是 O(1)。

Answer 4

我最终使用了这个：

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

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

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

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

Get a sublist last 5 elements of LinkedHashSet?

java

hashset

sublist

linkedhashset