Iteration Order of Hashset

Iteration order of HashSet

Absolutely not.

The insertion order directly influences the iteration order whenever you have a bucket collision:

When two elements end up in the same bucket, the first one that was inserted will also be the first one returned during iteration, at least if the implementation of collision handling and iteration is straightforward (and the one in Sun's java.util.HashMap is)

java.util.HashSet int iteration order

Docs says

This class implements the Set interface, backed by a hash table (actually a HashMap instance). 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. This class permits the null element.

go for LinkedHashSet

Relying on the iteration order of an unmodified HashSet

According to the reference source of HashSet (link), the iteration order is predictable in the absence of set modifications.

public bool MoveNext() {
    if (version != set.m_version) {
        throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
    }

    while (index < set.m_lastIndex) {
        if (set.m_slots[index].hashCode >= 0) {
            current = set.m_slots[index].value;
            index++;
            return true;
        }
        index++;
    }
    index = set.m_lastIndex + 1;
    current = default(T);
    return false;
}

However unlikely, this could change in future versions of the .NET platforms, or in other implementations. To ensure that the order stays the same, make a list from the set on the first iteration, and use the list for your second iteration:

var myList = myHashSet.ToList();
foreach( var obj myObject in myList) ...
// Some instructions (may or may not modify myHashSet, it no longer matters)
foreach( var obj myObject in myList) ...

iterating through instance of HashSet class, expect random order but the results are always the same order

YES. It's due to "luck". It depends on the JRE implementation! I learned this the hard way many years ago when started implementing in Java, and the code was tested on different platforms.

If i recall, in windows a HashSet iteration was perfectly ordered, but in Mac OSX totally scrambled!

Bottom line: Always rely on the docs, and not on the apparent results!

Why HashSet order always same for my program?

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.

Ordering of elements in Java HashSet

The second one (just using HashSet) is only a coincidence. From the JavaDocs:

This class implements the Set interface, backed by a hash table (actually a HashMap instance). 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. This class permits the null element.

The third one (LinkedHashSet) is designed to be like that:

Hash table and linked list implementation of the Set interface, with predictable iteration order. This implementation differs from HashSet in that it maintains a doubly-linked list running through all of its entries. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order). Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)

Order of element in hashSet

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

Iteration Order of Hashset