在LinkedHashSet的第0个位置插入元素的成本，或者我们可以向后迭代它吗？

Question

我正在使用

LinkedHashSet

。我想在第 0 个位置插入项目，例如：

Set<String> set = new LinkedHashSet<String>();
for (int i = 0; i < n; i++) {
    set.add(0, "blah" + i);
}

我不确定

LinkedHashSet

是如何实现的，插入是否会物理移动当前项目的所有地址，或者它与链表实现中的插入成本相同吗？

编辑

我把事情搞砸了：正在引用

ArrayList

文档。

Set

接口没有

add(index, object)

方法。那么有没有办法向后迭代集合呢？现在迭代我正在做的事情：

for (String it : set) {
}

我们可以反过来做吗？

Answer 1

根据定义，集合与顺序无关。因此，Set 没有可用的 add(int , Object) 方法。

LinkedHashSet 也是如此 http://download.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html

LinkedHashSet 维护插入顺序，因此所有元素都添加到链表的末尾。这是使用 LinkedHashMap 实现的。你可以看看LinkedHashMap中的linkEntry方法http://www.docjar.com/html/api/java/util/LinkedHashMap.java.html

编辑：回应编辑后的问题

没有可用的 API 方法来执行此操作。但你可以执行以下操作

1. 使用 new 将集合添加到列表

   ArrayList(Set)

2. 使用

   Collections.reverse(List)

3. 迭代此列表

Answer 2

Java 21 在 addFirst

 中添加了 

LinkedHashSet 方法，该方法将一个元素添加到集合的开头。

添加一个元素作为该集合的第一个元素（可选操作）。此操作正常完成后，给定元素将成为该集合的成员，并且它将是遇到顺序中的第一个元素。

Answer 3

从 LinkedHashMap 的源代码（支持 LinkedHashSet ——参见 http://www.docjar.com/html/api/java/util/LinkedHashMap.java.html）来看，插入很便宜，就像在链接中一样列表。

Answer 4

为了回答您的最新问题，

LinkedHashSet

没有可用的反向迭代器功能，即使内部实现使用双向链表。

有一个关于此的公开增强请求：

https://bugs.java.com/bugdatabase/view_bug?bug_id=4848853

Mark Peters 链接到 guava 中可用的功能，尽管他们的反向列表实际上生成了一个反向列表。

Answer 5

正如已经提到的，LinkedHashSet 是建立在 LinkedHashMap 之上的，而 LinkedHashMap 又是建立在 HashMap 之上的:) Javadocs 说，假设你的哈希函数实现正确，将一个元素添加到 HashMap 需要恒定的时间。如果你的哈希函数没有很好地实现，它可能需要O(n)。 目前不支持向后迭代。

Answer 6

您不能将元素添加到

LinkedHashSet

的前面...它没有诸如

add(int, Object)

之类的方法，也没有任何其他使用集合中“索引”概念的方法（即

List 

概念）。它仅根据插入元素的顺序提供一致的迭代顺序。当您迭代它时，集合中尚未包含的最近插入的元素将是最后一个元素。

并且

LinkedHashSet

的 Javadoc 明确指出：

与 HashSet 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数在存储桶中正确分散元素。

编辑：除了将其复制到

LinkedHashSet

并反向迭代之外，没有任何方法可以反向迭代

List

。使用 Guava 你可以这样做：

for (String s : Lists.reverse(ImmutableList.copyOf(set))) { ... }

请注意，虽然创建

ImmutableList

确实需要迭代原始集合的每个元素，但

reverse

方法仅提供反向视图，并且根本不迭代本身。

Answer 7

从 Java 21 开始，

reversed()

方法可用于返回集合的反向视图，然后可以以标准方式迭代该视图（例如使用增强的

for

语句）：

for (String it : set.reversed()) {
    System.out.println(it);
}