Any implementation of Ordered Set in Java?

Question

If anybody is familiar with Objective-C there is a collection called NSOrderedSet that acts as Set and its items can be accessed as an Array's ones.

Is there anything like this in Java?

I've heard there is a collection called LinkedHashMap, but I haven't found anything like it for a set.

Answer 1

Take a look at the Java standard API doc. Right next to LinkedHashMap, there is a LinkedHashSet. But note that the order in those is the insertion order, not the natural order of the elements. And you can only iterate in that order, not do random access (except by counting iteration steps).

There is also an interface SortedSet implemented by TreeSet and ConcurrentSkipListSet. Both allow iteration in the natural order of their elements or a Comparator, but not random access or insertion order.

For a data structure that has both efficient access by index and can efficiently implement the set criterium, you'd need a skip list, but there is no implementation with that functionality in the Java Standard API, though I am certain it's easy to find one on the internet.

Answer 2

Take a look at LinkedHashSet class

Answer 3

Try using java.util.TreeSet that implements SortedSet.

To quote the doc:

"The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used"

Note that add, remove and contains has a time cost log(n).

If you want to access the content of the set as an Array, you can convert it doing:

YourType[] array = someSet.toArray(new YourType[yourSet.size()]); 

This array will be sorted with the same criteria as the TreeSet (natural or by a comparator), and in many cases this will have a advantage instead of doing a Arrays.sort()

Answer 4

Every Set has an iterator(). A normal HashSet's iterator is quite random, a TreeSet does it by sort order, a LinkedHashSet iterator iterates by insert order.

You can't replace an element in a LinkedHashSet, however. You can remove one and add another, but the new element will not be in the place of the original. In a LinkedHashMap, you can replace a value for an existing key, and then the values will still be in the original order.

Also, you can't insert at a certain position.

Maybe you'd better use an ArrayList with an explicit check to avoid inserting duplicates.

Answer 5

If we are talking about inexpensive implementation of the skip-list, I wonder in term of big O, what the cost of this operation is:

YourType[] array = someSet.toArray(new YourType[yourSet.size()]);

I mean it is always get stuck into a whole array creation, so it is O(n):

java.util.Arrays#copyOf

Answer 6

IndexedTreeSet from the indexed-tree-map project provides this functionality (ordered/sorted set with list-like access by index).