2

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

它维护一个双向链表，贯穿其所有条目。这个链表定义了迭代顺序，也就是元素被插入到集合中的顺序（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) 中最近插入的元素，它对我也很有用。

非常感谢。

4

1 回答 1

2

不幸的是，似乎没有直接/干净的方式来访问O(1)中的 a LinkedHashSet(or ) 中最近添加的元素。LinkedHashMap

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

一种肮脏的方法是使用反射来访问内部哈希映射、映射的头条目，最后是条目的前任（before）。

于 2013-07-25T13:20:58.210 回答