Why do we not get the ordered sequence in HashSet

Question

I am using the HashSet for adding the elements and retrieving them, I know that I will not retrieve the data in sequence in which I added them, but I want to know the exact reason why Is it happeing?

import java.util.HashSet;
import java.util.Iterator;

 public class HS {
     public static void main(String args[]) {
         HashSet h=new HashSet();
         h.add("Mayank");
         h.add("Mayank");

         h.add("Vashist");
         h.add("Dinesh");

         h.add("Vashist");

         Iterator itr=h.iterator();
         while(itr.hasNext()) {
             System.out.println(itr.next());
         }
     }
 }

Solution 1

This is just the contract for a Set in java, from the javadoc

Returns an iterator over the elements in this set. The elements are returned in no particular order (unless this set is an instance of some class that provides a guarantee). So an implementation of Set isn't required to maintain any order in the values.

In order to return values in order the Set needs to maintain the order. This has costs for speed and space.

A LinkedHashSet maintains insertion order.

Solution 2

HashSet does not preserve the element addition order. First it computes the object hash code that should stay constant but is difficult to predict, and then uses it to select a bucket that is a list of objects that have had the same bucket selected. As an Iterator just iterates over all buckets, the iteration order is largely unpredictable.

Use LinkedHashSet instead if you need to preserve the order. However LinkedHashSet maintains an additional linked list so needs more resources.

Solution 3

Because in HashSet there is a hash value calculated for each object and this hash value determines the array index of the particular object in the container. So the order of inserted elements are naturally not preserved. This allows for accessing desired elements with O(1) complexity but it costs a lot of memory.

http://en.wikipedia.org/wiki/Hash_table

Solution 4

A HashSet uses what is referred to as a hash table to store items.

A hash table is made up of several "slots" into which your items are put. Deciding what slot to put an item into is determined by that item's hash code which generally has no relationship to the natural ordering of the item.

A TreeSet, on the other hand, stores items based on their natural ordering which allows an in-order traversal of its contents. This order will be based on the natural ordering of the objects and not the order in which they were inserted. Another difference between a TreeSet and HashSet is that a HashSet provides O(1) lookup, insertion and removal where as a TreeSet provides O(log(n)) lookup, insertion and removal.

A LinkedHashSet maintains insertion order of items by constructing links between the elements as they are inserted.

View more solutions