java - 获取 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 并且可以返回 a HashSet（而不是 a 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

这就是问题所在。a 的迭代器LinkedHashSet是单向的；即你不能向后迭代，即使底层数据结构有一个双向链表。这意味着要获得最后一个 N，您需要迭代到列表的末尾。那就是O(N)。

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

相比之下，TreeSetAPI 有一个descendingIterator()方法返回一个Iterator向后迭代列表的方法。如果你正确使用它，你可以得到集合的最后 5 个元素O(1)。缺点是向集合中添加元素将O(logN)不是O(1)基于散列的集合。

Answer 4

我最终使用了这个：

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

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

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