Order of elements in a set in java

Question

If i create 2 lists from the same set, can I be sure that I get the same ordering in both the lists? (I do not care about the ordering as long as both the lists have the same order and I am not performing any operations on the sets between creating the two lists.)

List l = new ArrayList(set);

List l1 = new ArrayList(set);

I understand that there are guaranteed ways of creating these lists and getting the same order and that there isn't a good reason for me to create two lists this way, but I would like to know why the ordering of elements in a set would change if no modify operations are performed on it.

Edit: The set is an unordered HashSet

Conscientious

If it's a hashset, no if it is mutated inbetween (ordering is not guaranteed, but it won't change without the set being modified). If it's anything else, the ordering would be defined so you can adjust based on that. – Broucek

This is completely implementation dependent. I can conceive of an implementation where iterating through the set would somehow change the order of the set. Very unlikely, but possible, and there is no guarantee it won't happen. – Tidal

No. A Set provides no guarantees as to its iteration order. Not even that it is consistent. It may choose to use your access as an excuse to tidy up the internal structure thereby changing the order on next iteration. – Agnusago

@Boris, this isn't a property of Set per se. For example, some sets like TreeSet and LinkedHashSet guarantee the iteration order. – Septuagint

@aetheria it absolutely is: from the JavaDoc for Set - "The elements are returned in no particular order". I.e. Set specifically states that it provides no guarantees. Talking about specific implantations is completely irrelevant - much like saying that a Set can be stored in a database because PersistentSet happens to be. – Agnusago

I agree 100% that you should not rely on an iteration order if you are given an arbitrary Set. What I meant (pedantically) was that some implementations of Set do guarantee iteration order. They are still Sets, i.e. there are Sets that do guarantee iteration order. The distinguishing property of a Set is that it contains no duplicates. All implementations must comply with this constraint. But implementations are free to offer guarantees about iteration order or persistence. – Septuagint

Answer 1

You will propably get the same ordering in the lists l and l1. But since most Sets are unordered, you have no guarantee that there will be the same order.

Technically you could write an implementation of the Set interface which changes its order everytime any method is called. This would still fulfil the interface.

Since in the constructor new ArrayList(Collection) the toArray method of the collection is called, we can have a look at the Javadoc of Set#toArray():

Returns an array containing all of the elements in this set. If this set makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.

While the Javadoc of Set#iterator() says there is no general guarantee:

Returns an iterator over the elements in this set. The elements are returned in no particular order (unless this set is an instance of some class that provides a guarantee).

Given this, I would strongly advise you not to rely on the ordering of the lists.

Probate

Answer 2

As per documentation

public ArrayList(Collection c) Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator

So it really depends on the Set interface implementation class, if the order is constant.

For example, if you use LinkedHashSet the iteration order is predictable.

Conscription

I am pretty sure that there is no set implementation currently provided by the major implementations for which this is not true, but it does not mean that there can't be one. – Tidal

In my case, I'm using the unordered hashset. – Conscientious

For the HashSet public Iterator<E> iterator() returns an iterator over the elements in this set. The elements are returned in no particular order. It looks you can not rely on this order. – Conscription

Answer 3

tl;dr

For a consistent encounter order, use an implementation of SequencedSet: ConcurrentSkipListSet, LinkedHashSet, TreeSet.

new ArrayList < String > 
(
    new TreeSet < String >   // An implementation of `SequencedSet`, `NavigableSet`, and `SortedSet`. 
    (
        List.of( "Bob" , "Carol" , "Alice" , "Alice" )
    )
)
.toString()

[Alice, Bob, Carol]

SequencedSet

Java 21 brought sequenced collections. The new interfaces include SequencedSet.

SequencedSet is the super-interface of the existing interfaces of NavigableSet and SortedSet.

Here is a set of String objects with natural ordering (alphabetical).

List < String > namesList = List.of( "Bob" , "Carol" , "Alice" , "Alice" );
SequencedSet < String > namesInAlphabeticalOrder = new TreeSet <>( namesList );

namesInAlphabeticalOrder = [Alice, Bob, Carol]

We see two behaviors here:

• Duplicates eliminated, by definition of any Set. (One "Alice" instead of two.)
• Natural ordering instilled and maintained in a SequencedSet like TreeSet.

Reliable encounter order

Back to the point of your Question, deriving List objects from a sequenced set in a reliable order…

A SequenceSet maintains its order. This means when you iterate, its encounter order will be consistent and reliable. So any List you derive will be in the same sequence as in the original SequencedSet.

List< String > listOfNamesInAlphabeticalOrder = new ArrayList< String > ( namesInAlphabeticalOrder ) ;

listOfNamesInAlphabeticalOrder.toString() = [Alice, Bob, Carol]

Christiachristian

Answer 4

There are structures that their orders are guaranteed or not. If we mention of Set interface implemented by Java, there is no guarantee. Most likely the constructor of ArrayList make uses of iterator of Set. So both list certainly contain always same elements but order. That's actually why Set uses contains keyword instead of find to check an element whether it exists.

It's sub-interface, SortedSet, represents a set that is sorted according to some criterion. In Java 6, there are two standard containers that implement SortedSet. They are TreeSet and ConcurrentSkipListSet.

In addition to the SortedSet interface, there is also the LinkedHashSet class. It remembers the order in which the elements were inserted into the set, and returns its elements in that order.

Measure

Answer 5

One way to impose a desired (natural, or otherwise) order on an unordered collection like a Set is to create an ordered Set (in other words, a SortedSet) from the given set. If your sets are not too large and all you care for is a predictable iteration order, you can do:

// set = ...
List<? extends Comparable> list = new TreeSet<>(set).stream().collect(Collectors.toList());

This assumes that the set consists of elements that are comparable. Alternatively, you could use your own comparator in the TreeSet constructor. There may be some issues in creating such a comparator however, if the elements themselves are not comparable.

Wage

Answer 6

There are some intertesting and good answers here, I can propose a solution.

List list = new ArrayList(set);

List secondList = new ArrayList(list);

Walczak