java - 高效获取 LinkedHashSet 中最近插入的元素

Question

根据LinkedHashSet的Javadoc中，它会通过内部使用双向链表来保持插入元素的插入顺序。

it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order)

如果我想获取第一个插入的元素，我可以使用如下代码:

linkedHashSet.iterator().next()

这将在 O(1) 时间内为我提供集合中第一个插入的元素。

我正在尝试解决一个问题，该问题需要我以 O(1) 的时间访问集合中最近插入的元素，并且我们假设集合中不会插入任何重复的元素。例如，

linkedHashSet.add(2); // the most recent inserted element in the set is 2
linkedHashSet.add(3); // the most recent inserted element in the set is 3
linkedHashSet.add(5); // the most recent inserted element in the set is 5
linkedHashSet.remove(5); // the most recent inserted element in the set is 3 because 5 is removed and not in the set now

由于它是集合中的双向链表，看来最近的元素应该是双向链表中的最后一个元素，并且如果有一些 API 可以获取它，则应该能够在 O(1) 内访问它.

我的问题是:JDK 有没有办法做到这一点，或者我是否需要创建自己的 ReversedIteratingLinkedHashSet 来做到这一点？

基本上，我尝试为所有操作找到一个时间复杂度为 O(1) 的 Set 数据结构，包括:插入/删除/搜索/检查集合中最近插入的元素。内置的 LinkedHashSet 看起来很适合，只需在内部进行很小的修改，但我不确定这是否可以使用默认的 JDK 类 API 来完成。

注意: 我检查了JDK的源代码，知道LinkedHashSet内部是用LinkedHashMap实现的，如果有任何解决方案可以使用LinkedHashMap以O(1)访问最近插入的元素，那么它对我来说也很有用。

非常感谢。

Answer 1

不幸的是，似乎没有直接/干净的方法可以在 O(1) 中访问 LinkedHashSet (或 LinkedHashMap)中最近添加的元素。

一种简洁的方法是将集合转换为数组并访问最后一个元素，但这将是 O(n)。

一种肮脏的方法是使用反射来访问内部 HashMap 、映射的头条目以及最后条目的前任条目(before)。