Why does the HashSet <T> class have values ​​already sorted when I use an iterator?

Question

I have the following code for my main method, and when I repeat through Set and print the values, the values ​​are already sorted. What reason?

 Set<Integer> set = new HashSet<Integer>(); set.add(2); set.add(7); set.add(3); set.add(9); set.add(6); for(int i : set) { System.out.println(i); } 

Output:

 2 3 6 7 9 

Answer 1

This is just a coincidence. A HashSet does not store or guarantee any order.

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

Answer 2

I am not sure if this coincidence is the correct answer. There is no chance. These are the results of using hash functions, small values ​​that you put in a HashSet, and a small number of elements that you put in Set.

• For Integer hashCode() is the value of int Integer.

• HashMap (and HashSet) does additional hashing of the value returned by hashCode , but this extra hash does not change the value for such small numbers that you added to the HashSet.

• Finally, the bucket into which each integer is entered is a modified hash code modulo the HashSet capacity. The initial HashSet / HashMap capacity is 16.

• Therefore, 2 is added to the bucket 2, 7 is added to the bucket 7, etc.

• When you iterate over HashSet elements, the buckets are visited in order, and since each bucket has at most one element, you get sorted numbers.

Here's how the bucket is calculated:

 int hash = hash(key.hashCode()); int i = indexFor(hash, table.length); static int hash(int h) { // for the small integers you put in the set, all the values being // xored with h are 0, so hash(h) returns h h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } static int indexFor(int h, int length) { return h & (length-1); // table.length is the initial capacity - 16, // so for h <= 15, indexFor(h,table.length)=h } 

Consequently, buckets 2,7,3,9,6 are 2,7,3,9,6 respectively.

The extended loop that you use to iterate over the HashSet visits the buckets in order, and for each bucket iterates over its records (which are stored in a linked list). Therefore, for your input, first visit 2, then 3, 6, 7 and 9.

If you add numbers above 15, both the hash method and the indexFor method (provided that you have not changed the default capacity for the HashSet) will prevent the sorting of numbers when repeating the HashSet iterator.

Answer 3

This is just an accident. I tried:

 final Set<Integer> set = new HashSet<Integer>(); set.add(2); set.add(17); set.add(32); set.add(92); set.add(63); 

and I got 17 32 2 92 63 . It was not in sorted order since the HashSet does not preserve the sorted order or the order in which they are added.