在 LinkedHashSet 的第 0 个位置插入元素的成本，或者我们可以向后迭代它吗？
我正在使用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) {
}
我们可以反过来做吗？
I'm using LinkedHashSet. I want to insert items at the 0th position, like:
Set<String> set = new LinkedHashSet<String>();
for (int i = 0; i < n; i++) {
set.add(0, "blah" + i);
}
I'm not sure how LinkedHashSet is implemented, is inserting going to physically move all addresses of current items, or is it the same cost as inserting as in a linked-list implementation?
Edit
Complete mess up by me: was referencing the ArrayList docs. The Set interface has no add(index, object) method. Is there a way to iterate over the set backwards then? Right now to iterate I'm doing:
for (String it : set) {
}
Can we do that in reverse?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
根据定义，集合与顺序无关。因此，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 方法来执行此操作。但是您可以
ArrayList(Set)将集合添加到列表中Collections.reverse(List)Sets are, by definition, independent of order. Thus, Set doesn't have add(int , Object) method available.
This is also true of LinkedHashSet http://download.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html
LinkedHashSet maintains insertion order and thus all elements are added at the end of the linked list. This is achieved using the LinkedHashMap. You can have a look at the method linkEntry in LinkedHashMap http://www.docjar.com/html/api/java/util/LinkedHashMap.java.html
Edit: in response to edited question
There is no API method available to do this. But you can do the following
ArrayList(Set)Collections.reverse(List)Java 21 添加了 LinkedHashSet 的“nofollow noreferrer">
addFirst方法，该方法将一个元素添加到集合的开头。Java 21 added the
addFirstmethod toLinkedHashSet, which adds an element to the start of the set.从LinkedHashMap的源代码来看（它支持LinkedHashSet——参见http ://www.docjar.com/html/api/java/util/LinkedHashMap.java.html ），插入很便宜，就像在链接列表中一样。
Judging by the source code of LinkedHashMap (which backs LinkedHashSet -- see http://www.docjar.com/html/api/java/util/LinkedHashMap.java.html ), inserts are cheap, like in a linked list.
为了回答您的最新问题，
LinkedHashSet没有提供反向迭代器功能，即使在内部实现使用双向链表。有一个关于此的公开增强请求：
https://bugs.java.com/ bugdatabase/view_bug?bug_id=4848853
Mark Peters 链接到 guava 中可用的功能，尽管他们的反向列表实际上生成了一个反向列表。
To answer your latest question, there is no reverse iterator feature available from
LinkedHashSet, even though internally the implementation uses a doubly linked list.There is an open Request For Enhancement about this:
https://bugs.java.com/bugdatabase/view_bug?bug_id=4848853
Mark Peters links to functionality available in guava, though their reverse list actually generates a reverse list.
正如已经提到的，LinkedHashSet 是基于 LinkedHashMap 构建的，而 LinkedHashMap 又基于 HashMap 构建:) Javadocs 表示，假设您的哈希函数已正确实现，则将元素添加到 HashMap 需要恒定的时间。如果你的哈希函数没有很好地实现，它可能需要O(n)。
目前不支持向后迭代。
As already mentioned, LinkedHashSet is build on LinkedHashMap, which is built on HashMap :) Javadocs says that it takes constant time to add an element into HashMap, assuming that your hash function is implemented properly. If your hash function is not implemented well, it may take up to O(n).
Iteration backwards in not supported at this moment.
您无法将元素添加到
LinkedHashSet的前面...它没有诸如add(int, Object)之类的方法，也没有任何其他使用该方法的方法集合中“索引”的概念（即List概念）。它仅根据插入元素的顺序提供一致的迭代顺序。当您对其进行迭代时，尚未包含在集合中的最近插入的元素将是最后一个元素。LinkedHashSet 的 Javadoc 明确指出：
编辑：除了将
LinkedHashSet复制到List并反向迭代之类的方法之外，没有任何方法可以反向迭代LinkedHashSet。使用 Guava 您可以这样做：请注意，在创建
ImmutableList< 时/code> 确实需要迭代原始集合的每个元素，reverse方法只是提供反向视图，并且本身根本不迭代。You can't add elements to the front of a
LinkedHashSet... it has no method such asadd(int, Object)nor any other methods that make use of the concept of an "index" in the set (that's aListconcept). It only provides consistent iteration order, based on the order in which elements were inserted. The most recently inserted element that was not already in the set will be the last element when you iterate over it.And the Javadoc for
LinkedHashSetexplicitly states:Edit: There is not any way to iterate over a
LinkedHashSetin reverse short of something like copying it to aListand iterating over that in reverse. Using Guava you could do that like:Note that while creating the
ImmutableListdoes require iterating over each element of the original set, thereversemethod simply provides a reverse view and doesn't iterate at all itself.从 Java 21 开始，
reversed()方法可用于返回集合上的反向视图，然后可以以标准方式迭代该视图（例如使用增强的 <代码>for语句）：Starting with Java 21, the
reversed()method can be used to return a reversed view on the set, which can then be iterated over in the standard manners (such as using an enhancedforstatement):