-2

So I know that sets cannot take duplicates... more formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most has one null element. I realize Treeset sorts the set for me. Here is my set code:

import java.util.Set;
import java.util.HashSet;
import java.util.TreeSet;

public class SetExample {

  public static void main(String args[]) { 
    int count[] = {11, 22, 33, 44, 55};
    Set<Integer> hset = new HashSet<Integer>();
    try{
      for(int i = 0; i<4; i++){
         hset.add(count[i]);
      }
      System.out.println(hset);

      TreeSet<Integer> treeset = new TreeSet<Integer>(hset);
      System.out.println("The sorted list is:");
      System.out.println(treeset);
    }
    catch(Exception e){
        e.printStackTrace();
    }
  }
}

This is my output:

ArrayList Elements:
[Chaitanya, Rahul, Ajeet]
LinkedList Elements: [Kevin, Peter, Kate]
[33, 22, 11, 44]
The sorted list is:
[11, 22, 33, 44]

Why is the set ALWAYS in the order of [33,22,11,44]?

Jwan622
  • 11,015
  • 21
  • 88
  • 181
  • 7
    Because it doesn't promise to randomize it, and its internal ordering to keep track of everything is consistent. – resueman Jan 06 '16 at 03:57
  • 1
    Your output doesn't match your code. I don't believe `HashSet` has any contract with regard to internal order, so your elements can come out unsorted. If you dig into the implementation, you might out why they appear in the order you see in the output. – Tim Biegeleisen Jan 06 '16 at 03:57
  • 1
    If you know it isn't ordered, why do you care what order it's in? – user207421 Jan 06 '16 at 04:02
  • It looks ordered? It comes out {33,22,11,44} every time? – Jwan622 Jan 06 '16 at 04:03
  • 1
    But how does it matter if *It comes out {33,22,11,44} every time?* – Atri Jan 06 '16 at 04:06
  • 1
    @Jwan622 How exactly can `{33,22,11,44}` possibly be considered as 'ordered'? Consistent sequencing isn't the same thing as ordering. You should *expect* consistent sequencing for the same values inserted in the same order, unless time is part of their hashcode, which isn't mentioned anywhere. – user207421 Jan 06 '16 at 04:08
  • And in any case the sequence produced by calling `toString()`, as you are here doing here implicitly, isn't guaranteed to have anything to do with either the iteration order or any other internal ordering. It's just a sequence. You have no grounds for being surprised at anything it does. – user207421 Jan 06 '16 at 05:57
  • If you add 0 to 10 to a HashSet they will happen to appear in order, no matter which order you add them. – Peter Lawrey Jan 06 '16 at 07:22
  • Ah @EJP this makes sense ... consistency isn't ordered. Look I think even though this question is basic... I don't think I should be downvoted this much no? It seems to have generated good discussion and content which is a + for this site no? – Jwan622 Jan 06 '16 at 15:12
  • Thanks for the upvotes! I don't think this is too bad of a question....! – Jwan622 Jan 12 '16 at 00:56

4 Answers4

5

Quoting javadoc of HashSet:

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 doesn't say "random". It doesn't say it's not consistent. It basically just says that order is undefined and may change over time, meaning that if you add more values, the order of the current values may change.

Note that although you get consistent, but undefined, order of your specific values, another version of the Java Runtime Library may give a different, but still consistent, order.

The actual order of the objects depend on the hash values of those objects, the current number of hash buckets in the HashSet, and the algorithm used to map a hash value to a hash bucket. The algorithm may change between different versions of the Java Runtime Library, and the number of hash buckets may change as values are added and removed from the HashSet.

To see this in effect, try creating the HashSet with a different initial capacity, using the HashSet(int initialCapacity) constructor. Different capacities will likely order the values differently, but will be consistent, meaning that same values, same capacity and same Runtime version will always be same order.

Andreas
  • 154,647
  • 11
  • 152
  • 247
1

Internally HashSet uses a map with the key as the element you're inserting and the value is just a new Object as a dummy placeholder (Look at the source code, you will see it just uses a map).

This means the keys(elements you add in set) could be placed anywhere in the map depending on the hashing. If you continue to place the same values in the set as an experiment they would probably be hashed to exactly the same location which is why the order wouldn't change when iterating over the entries.

Only when you change the values would you get some different ordering due to where they end up being placed in the backing map.

reversebind
  • 1,216
  • 1
  • 14
  • 18
1

If you look at the implementation of HashMap it turns out that under the hood it is the HashMap, with values stored as keys in HashMap (and some dummy empty object as a value), so the order in HashSet is is implied by the ordering in HashMap. - You can read more about entry ordering in HashMap here: https://stackoverflow.com/a/2144822/1935341

Community
  • 1
  • 1
Mateusz Dryzek
  • 651
  • 4
  • 18
0

If you are wondering why the order is consistent as it said that set doesn’t maintain any order.

The thing is set doesn’t maintain insert order but maintain an order of itself.

HashSet Maintain a HashMap inside to store the entries. 

public HashSet() { 
    map = new HashMap<>();
}

When some item is inserted it is inserted to the Map. 

public boolean add(E e) {
    return map.put(e, PRESENT)==null;
}

Now as of HashMap. It is know that the index of the key is determined by the hash value of the key. This hash value is consistent for any object.

So similar Object will generate same hash every time. So the similar order is maintained .

Saif
  • 6,804
  • 8
  • 40
  • 61