Cost of inserting element at 0th position of LinkedHashSet?

Question

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 linked hash set 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?

Thank you

------ Edit ---------------

Complete mess up by me, was referencing 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?

Thanks

Answer 1

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

1. Add Set to a List using new ArrayList(Set)
2. Use Collections.reverse(List)
3. Iterate this list

Answer 2

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.

Answer 3

You can't add elements to the front of a LinkedHashSet... it has no method such as add(int, Object) nor any other methods that make use of the concept of an "index" in the set (that's a List concept). 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 LinkedHashSet explicitly states:

Like HashSet, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets.

Edit: There is not any way to iterate over a LinkedHashSet in reverse short of something like copying it to a List and iterating over that in reverse. Using Guava you could do that like:

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

Note that while creating the ImmutableList does require iterating over each element of the original set, the reverse method simply provides a reverse view and doesn't iterate at all itself.

Answer 4

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:

http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=4848853

Mark Peters links to functionality available in guava, though their reverse list actually generates a reverse list.

Answer 5

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.

Answer 6

Java 21 is adding a addFirst method to LinkedHashSet, which adds an element to the start of the set.

Adds an element as the first element of this collection (optional operation). After this operation completes normally, the given element will be a member of this collection, and it will be the first element in encounter order.