Order of element in hashSet

Question

I have read in java 1.7 docs that "It makes no guarantees as to the iteration order of the set". what is meaning of this?

I created a HashSet print its elements 1000 times. but every time i get a fixed order. however order is not same as insertion order of element.

 Set<String> hashSet = new HashSet<>();

    for (int i = 0; i < 10; i++) {
        hashSet.add("Item+" + i);
    }

    for (String s : hashSet) {
        System.out.println(s);
    }

"order is not same as insertion order of element" is what you are expecting — HJK, Apr 16 '15 at 10:58
So you got an order you couldn't predict, or guarantee. Your question is? — user207421, Apr 16 '15 at 10:58
may be you should see that :http://stackoverflow.com/questions/1463284/hashset-vs-treeset — Master Mind, Apr 16 '15 at 10:58
@EJP i know that i can't predict the order. actually i am expecting a random order but every time i am getting a fix order on java 1.7. — Arun, Apr 16 '15 at 11:45
Why are you expecting a random order? The doc doesn't say the order will be random. — Louis Wasserman, Apr 16 '15 at 16:39

score 2 · Answer 1 · answered Apr 16 '15 at 10:58

2

You should try adding a lot more elements (say, 10.000) to the set. The HashSet has a default capacity of 16, but once you add more elements to the set, it is internally reconstructed. In that case, the order might change.

answered Apr 16 '15 at 10:58

Glorfindel

21,988
13
81
109

This is not the case for order. – erhun Apr 16 '15 at 10:59
@erhun Oh yes it is. – user207421 Apr 16 '15 at 11:00
@EJBAfter i read again yes he is right maybe an answer is edited or i misunderstand it . – erhun Apr 16 '15 at 11:03

score 2 · Answer 2 · answered Apr 16 '15 at 10:58

2

It means that you can not be sure that the order will be the same, for instance if you run the same code on another JVM.

The fact that the order is always the same on your machine, using one specific JVM is irrelevant. If order is important, consider using a TreeSet, a TreeSet will guarantee that the order is always the same, no matter where you run your code.

Of course: a TreeSet requires that the items can be ordered in some way (e.g. alphabetically). If you want to preserve the order in which elements are added, you may prefer a List such as an ArrayList.

answered Apr 16 '15 at 10:58

Bruno Lowagie

75,994
9
109
165

`TreeSet` requires `Comparable`s – Alex Salauyou Apr 16 '15 at 11:10
@SashaSalauyou Correct, as I wrote: it requires that the items can be ordered in some way. To me, it sounds like the OP wants a `List` instead of a `Set`, but the question isn't really clear about that. – Bruno Lowagie Apr 16 '15 at 11:33
I believe OP simply confuses "non-predictable order" with "random order". – Alex Salauyou Apr 16 '15 at 11:37
Yes, that seems to be the case. I just saw your answer. It clarifies the problem. – Bruno Lowagie Apr 16 '15 at 11:38

Alex Salauyou · Answer 3 · 2015-04-16T11:22:41.373

1

In hash collections, entries appear sorted by result of some internal hashing function.

For the same set of entries added to the same collection in the same order, returning order will be always the same though hash function values also remains the same, except if internal structure is reorganized between calls (i. e. by expanding or shrinking of the collection) - on reorganization, values of internal hashing function are recalculated and entries take another places in internal hash table.

BTW, entry iterator of hash collection guarantees only that you will receive all entries you've put there which wasn't removed.

edited Apr 16 '15 at 11:22

answered Apr 16 '15 at 11:12

Alex Salauyou

14,185
5
45
67

This is not correct. The entry order also depends on the order in which entries have been added to and removed from the hash table, and its initial capacity. And other things. – Stephen C Apr 16 '15 at 11:15
@StephenC sure, if you remove then add same entry, it can take another place in a bucket, and returning result will change. I updated my answer to make it more clear. – Alex Salauyou Apr 16 '15 at 11:20

score 1 · Accepted Answer · edited May 23 '17 at 10:28

The order of the entries in a HashMap or HashSet is predictable in theory for current generation and older implementations.

However, the prediction depends on at least:

the hash values of the keys,
the initial capacity of the set or map,
the precise sequence in which the keys were added to and removed from the set / map,
the specific implementation of HashSet or HashMap used (the behaviour is Java version dependent, and possibly depended on patch level), and
for Java 8 and later, whether or not the keys are Comparable.

If you have all of that information (and you are prepared to emulate the insertion / removal sequence), you can accurately predict the iteration order. However, it would be tricky to implement, and expensive to run ...

In your example, the hash values are the same, the initial HashSet capacity is the same, the insertion order is the same, and the HashSet implementation is the same. In those circumstances (and given the precise algorithms used) the iteration order is going to repeatable ... even if though it would difficult to predict.

In this case, the order is not "random" because there is no randomness in the process that builds the HashSet. Just calculations that are complicated and opaque ... but deterministic.

I have read in java 1.7 docs that "It makes no guarantees as to the iteration order of the set". what is meaning of this?

What is means is that the javadoc is not committing to any specific behaviour vis-a-vis the ordering. Certainly, there is no commitment to portable behaviour.

See also: Order of values retrieved from a HashMap

score 0 · Answer 5 · answered Apr 16 '15 at 11:02

Maybe you can see same "sorting" but this is not real, it's up to the JVM so, if you want a sorted list

If you have a logical sorting use Collections.sort() or implement your own Comparator
If you want the Collection sorted by insertion order use a List and Iterator

List iterators guarantee first and foremost that you get the list's elements in the internal order of the list (aka. insertion order). More specifically it is in the order you've inserted the elements or on how you've manipulated the list. Sorting can be seen as a manipulation of the data structure, and there are several ways to sort the list.

Order of element in hashSet

5 Answers5