LinkedHashSet iteration not in ascending order?

Question

In the following code, if the parameter is {1,3,2}, in the while loop, i is 1, 3, 2.

I am already using LinkedHashSet, why is the order not 1, 2, 3? What else do I need to do to make the iteration in ascending order?

Cannot use TreeSet as it add, remove, contains() in o(log n) time.

public static void iterate(int[] num) {
    LinkedHashSet<Integer> set = new LinkedHashSet<Integer>();

    for (int i : num) {
        set.add(i);
    }

    Iterator<Integer> iter = set.iterator();
    while (iter.hasNext()) {
        // WHY IS i THE SAME ORDER AS INSERATION ORDER, NOT ASSENDING ORDER?
        int i = iter.next();
    }
}

Answer 1

Because a LinkedHashSet iterates in insertion order and is not sorted! From the javadoc:

This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).

You will want to use TreeSet for a sorted set, have a look at the sorted set javadoc: https://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html

Answer 2

There is no Java implementation that does a sorting before returning the iterator. There are only implementations like TreeSet that are sorted due to their data structure.

At some point the sorting have to be done. There cannot be a (Hash-)Implementation that supports constant time adding and getting and being inherently sorted. If something like this would exist then we would be able to sort in constant time.

If you want to stay with a Hash-Implementation then you must do the "sorting work" directly before/after retrieving the elements. Since you cannot change the before the only solution is to sort after retrieving the elements.

Sample code with Guava's Ordering:

while (Integer i : Ordering.natural().sortedCopy(hashSet)) {
    // "i" in sorted order
}

Answer 3

So you want a HashSet for a fast contains and rightly saw that LinkedHashSet maintains an extra data structure, unfortunately for ordering by insertion.

If the above code shows all insertions, you could sort the inserted data in advance:

Arrays.sort(num);
Collections.addAll(set, num);

The more general solution would be to copy the set to a new collection afterwards and sort that.

If the numbers are in a specific range, especially positive and not sparse, you might use a BitSet. That really is a performant solution if applicable.