How can I preserve insertion order in a HashSet?

Question

I wrote the following code,

public int longestConsecutive(int[] nums) {
Set<Integer> num_set = new HashSet<Integer>();
for (int num : nums) {
    num_set.add(num);
    System.out.println("num_set: " + num_set.toString());
}

then I have the test case,

int[] nums  = {100, 4, 200, 1, 3, 2};

then in the last line output, the console shows,

num_set: [1, 2, 3, 100, 4, 200]

I'm wondering why the previous order was changed after the add operation.

Answer 1

Stating the HashSet documentation

It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.

If you want to use a Set that remains natural order, use a SortedSet instead.

A Set that further provides a total ordering on its elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time.

Edit: A Set does by definiton not say anything about the order of its elements. For exmaple, two Sets are equals if both contain the same elements and have the same size. The iteration order of a Set is dependent on the implementations and may change between versions, so you should not make any assumptions on it. It may depend on the value of #hashCode, but it may as well depend on the insertion order or something else in the future. However, we should not care, because if you do you should use a List or a SortedSet instead.

Answer 2

It looks like you want to preserve insertion order. There's a class called LinkedHashSet for this. Here's some sample code for you:

int[] nums  = {100, 4, 200, 1, 3, 2};
Set<Integer> ints = new LinkedHashSet<>();
for(int i : nums) {
    ints.add(i);
}
System.out.println(ints);

The above code prints: [100, 4, 200, 1, 3, 2]

As the documentation says:

Hash table and linked list implementation of the Set interface, with predictable iteration order. 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). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)

Answer 3

Glains has already answered your question. Still I'd like to add some: there are interfaces in Java library which provides contracts to the developers, making promises that they can be used in which ways.

Just like your question, basic interface Set

A collection that contains no duplicate elements.

And your implementor HashSet, which already clearly specifies the fact that order is not guaranteed, in which case you should NOT expect any order-related promises.

It makes no guarantees as to the iteration order of the set; in particular, it does not guarantee that the order will remain constant over time.

And specifically, Java provides another interface SortedSet instead to ensure order you are asking for:

A Set that further provides a total ordering on its elements. The elements are ordered using their natural ordering, or by a Comparator typically provided at sorted set creation time.

So in your case, you should find an implementor that implements the interface SortedSet, like TreeSet.

Normally we care not much about the implementation details since they can be adjusted/changed without our knowing, while on the other hand the promises the library developers made in the official documentation will be kept always.