-2

I found a (for me) inexplicable behavior with an implemented HashSet in Java. I implemented the HashSet like this and filled it with the values of a list.

HashSet<Integer> set = new HashSet<Integer>(list);

I first used a list containing numbers reaching fom 0 to 9 to fill the HashSet:

Example: {1,0,5,9,6,7,3,1,3,6,1,5,1,3,4,9,9,7}
Output: [0, 1, 3, 4, 5, 6, 7, 9]

Since HashSets normally give back values in an ascending sorted order until now everything worked fine. But as soon as I started using a list containing bigger vaues it starts giving back the values in a weird way:

Example: {67,1,122,19,456,42,144,42,3,34,5,5,42}
Output: [1, 34, 67, 3, 5, 456, 42, 144, 19, 122]

I read something about that this depends on the internal hashing algorithm here: Java HashSet shows list in weird order, always starting with 3 but that is even more confusing since I used the exact same HashSet just with different values.

Could please somebody explain me why this is happening?

Lukas Schröder
  • 344
  • 1
  • 2
  • 16
  • 4
    Why are you worrying about the order? The JavaDoc says the following: __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.__ – Logan Nov 12 '18 at 18:59
  • 4
    Never ever ever rely on the iteration order of a `HashSet`! – Jacob G. Nov 12 '18 at 18:59
  • @Logan because I used this a few times to order Integer Arrays and it worked for the smaller values so I was a bit confused about why it stopped working for larger values. And no its not a duplicate of the other question. – Lukas Schröder Nov 12 '18 at 19:05
  • @Logan yes, this one answers it. I just did not find this question. – Lukas Schröder Nov 12 '18 at 19:14

3 Answers3

6

HashSet explicitly does not provide a predictable ordering.

It simply so happens that in the first case, the hash codes (which for Integer is just the integer value) are all smaller than the number of buckets, which means that if all of the values are lower than the default number of buckets (16), they'll coincidentally be in order.

chrylis -cautiouslyoptimistic-
  • 75,269
  • 21
  • 115
  • 152
4

Since HashSets normally give back values in an ascending sorted order

The short answer, integers 0 to 15, a HashSet happens to be in natural order. However, this could change in future as this is not a documented feature and is not something you should rely on.

The long answer:

This only happens due to the way the keys are hashed. Integer.hashCode() is implemented as

public int hashCode() {
    return Integer.hashCode(value);
}

which calls

public static int hashCode(int value) {
    return value;
}

so the values 0 to 15 for example have a hash of just 0 to 15.

HashSet, in turn, takes the hash and agitates it so that high bits kept significant.

// from HashMap
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

However, as you can see, that in OpenJDK Java 11, the values 0 to 65535 are unaltered.

Finally, the lower bits are kept to determine where in the HashSet's array they are stored.

// from HashMap.putVal
i = (n - 1) & hash

Where n is the capacity which is always a power of two. As the default capacity is 16, the values 0 to 15 are unaltered.

This index i is used to determine where in the underlying array, the entry should be stored.

When you iterate over a HashSet or HashMap it simply starts at the first index of the array, iterating over then in index order which also happens to be the natural order of the keys.

Peter Lawrey
  • 525,659
  • 79
  • 751
  • 1,130
3

HashSet is an unordered Collection. It does not maintain the order in which the elements are inserted. So it won't give values in an ascending sorted order always

Sandeepa
  • 3,457
  • 5
  • 25
  • 41