Why HashSet order always same for my program?

Question

For some tutorial, they said:

HashSet doesn’t maintain any order, the elements would be returned in any random order.

But I write a test program, the result is always same.

import java.util.*;

public class HashSetDemo {

    public static void main(String[] args) {
        HashSet<String> hs1 = new HashSet<String>();
        hs1.add("a");
        hs1.add("b");
        hs1.add("c");
        hs1.add("d");
        hs1.add(null);
        hs1.add(null);
        System.out.println(hs1);
        System.out.println(hs1);
    }
}

Output:

[null, a, b, c, d]
[null, a, b, c, d]

I tried many times, but the order is always same. Why? Hope someone can help me, Thanks in advance!

Answer 1

The reason for this behaviour is that a HashSet is backed by a HashMap, which in turn is backed by an array of Entry-objects. where the hash is used to find the index of the array. So there is always an order of elements in a HashSet (the order of the array), you just don't have any guarantees as to what this order is.

As far as I can tell from the code, the order of the HashSet is determined (or at least affected) by the order of the computed hashes of its elements. Then, with relatively simple inputs (like your single character string), one might assume that there is a strict ordering of the hashes, which will give you what seems to be a natural ordering. With more complex objects, and thus more complex hash computations, the hashes will be more spread, and the ordering "more random".

Also, like it's been pointed out, "no guarantee of ordering" does not imply "guaranteed random ordering".

The hashcode-method of the String class also comes into play here, for single character Strings the hashcode will just be the int value of the one char in the String. And since char's int values are ordered alphabetically, so will the computed hashes of single char Strings.

Answer 2

Just because they are not guaranteed to maintain order doesn't mean they won't be in order sometimes.

Use a different collection if you require ordering - treeset for example.

Answer 3

As we see the document

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.

It does maintain but not guaranteed. Over the time after you adding, deleting few times you can see the difference.

Answer 4

Of cause not random order, for a certain input, the iterator's order is fixed, I think they want to say the order is probably different from input order. In fact here the order depends on String.hashCode() , String.equals(), and order of set.add() invoke.

When you call System.out.print(set), you mean System.out.print(set.toString()) , and set.toString() invokes set's iterator to access all elements.

Answer 5

HashSet doesn't gaurrantee it, but it doesn't necessary mean it has to change the order. there is no point of changing order if nothing gets added. for example take a look at this example

hs1.add("c");
hs1.add("b");
hs1.add("d");
hs1.add("g");
hs1.add(null);
hs1.add(null);
System.out.println(hs1);

OUTPUT: [null, b, c, d, g]

then we add a new element and print again:

    hs1.add("a");
    System.out.println(hs1);

OUTPUT: [null, a, b, c, d, g]

as you see it changed the order to some extend.

nothing is guaranteed but it doesn't mean it has to go out of its way to change the order

Answer 6

HashSet order is not random it's implementation dependent and implementation is free to change. A notable changes were made in JDK 8. Thus if you upgrade to Java 8, you may see that HashMap order is changed. Also it may be different if you use non-Oracle JDK like IBM. In general you should never rely on it, otherwise your program may break in future.

Answer 7

HashSet() doesn't have any ordering. It also not support the input order. But the order is not random. Even if you change the version and upgrade, the output will be changed and remain same for that version. As by implementing your source code, I'm getting some different answer as follows. I have execute this code for several time in a row but the output is same.

[a, b, c, d, null]

One more thing, HashSet() doesn't support duplicate, so, adding duplicate "null" only increase the length of your code.

Answer 8

HashSet uses binary search for finding possible duplicate items and has to order the objects in list after their hash (hashCode()) in order to do so.