[java] HashSet vs LinkedHashSet

What is the difference between them? I know that

A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. Use this class instead of HashSet when you care about the iteration order. When you iterate through a HashSet the order is unpredictable, while a LinkedHashSet lets you iterate through the elements in the order in which they were inserted.

But in sourcecode of LinkedHashSet there are only calling constructors of HashSet. So where is double-linked List and insertion order?

This question is related to java hashset linkedhashset

The answer is


LinkedHashSet's constructors invoke the following base class constructor:

HashSet(int initialCapacity, float loadFactor, boolean dummy) {
  map = new LinkedHashMap<E, Object>(initialCapacity, loadFactor);
}

As you can see, the internal map is a LinkedHashMap. If you look inside LinkedHashMap, you'll discover the following field:

private transient Entry<K, V> header;

This is the linked list in question.


HashSet is unordered and unsorted Set.
LinkedHashSet is the ordered version of HashSet.

The only difference between HashSet and LinkedHashSet is that:
LinkedHashSet maintains the insertion order.

When we iterate through a HashSet, the order is unpredictable while it is predictable in case of LinkedHashSet.

The reason for how LinkedHashSet maintains insertion order is that:
The underlying used data structure is Doubly-Linked-List.


If you take a look at the constructors called from the LinkedHashSet class you will see that internally it's a LinkedHashMap that is used for backing purpose.


All Methods and constructors are same but only one difference is LinkedHashset will maintain insertion order but it will not allow duplicates.

Hashset will not maintain any insertion order. It is combination of List and Set simple :)


You should look at the source of the HashSet constructor it calls... it's a special constructor that makes the backing Map a LinkedHashMap instead of just a HashMap.


HashSet:

The underlined data structure is Hashtable. Duplicate objects are not allowed.insertion order is not preserved and it is based on hash code of objects. Null insertion is possible(only once). It implements Serializable, Clonable but not RandomAccess interface. HashSet is best choose if frequent operation is search operation.

In HashSet duplicates are not allowed.if users are trying to insert duplicates when we won't get any compile or runtime exceptions. add method returns simply false.

Constructors:

HashSet h=new HashSet(); creates an empty HashSet object with default initial capacity 16 and default fill ratio(Load factor) is 0.75 .

HashSet h=new HashSet(int initialCapacity); creates an empty HashSet object with specified initialCapacity and default fill ration is 0.75.

HashSet h=new HashSet(int initialCapacity, float fillRatio);

HashSet h=new HashSet(Collection c); creates an equivalent HashSet object for the given collection. This constructor meant for inter conversion between collection object.

LinkedHashSet:

It is a child class of HashSet. it is exactly same as HashSet including(Constructors and Methods) except the following differences.

Differences HashSet:

  1. The underlined data structure is Hashtable.
  2. Insertion order is not preserved.
  3. introduced 1.2 version.

LinkedHashSet:

  1. The underlined data structure is a combination of LinkedList and Hashtable.
  2. Insertion order is preserved.
  3. Indroduced in 1.4 version.

I suggest you to use LinkedHashSet most of the time, because it has better performance overall):

  1. Predictable iteration order LinkedHashSet (Oracle)
  2. LinkedHashSet is more expensive for insertions than HashSet;
  3. In general slightly better performance than HashMap, because the most of the time we use Set structures for iterating.

Performance tests:

------------- TreeSet -------------
 size       add  contains   iterate
   10       746       173        89
  100       501       264        68
 1000       714       410        69
10000      1975       552        69
------------- HashSet -------------
 size       add  contains   iterate
   10       308        91        94
  100       178        75        73
 1000       216       110        72
10000       711       215       100
---------- LinkedHashSet ----------
 size       add  contains   iterate
   10       350        65        83
  100       270        74        55
 1000       303       111        54
10000      1615       256        58

You can see source test page here: The Final Performance Testing Example


HashSet: Unordered actually. if u passing the parameter means

Set<Integer> set=new HashSet<Integer>();
for(int i=0;i<set.length;i++)
{
  SOP(set)`enter code here`
}

Out Put: May be 2,1,3 not predictable. next time another order.

LinkedHashSet() which produce FIFO Order.


HashSet don't maintain the order of insertion item
LinkedHashSet maintain the order of insertion item

Example

Set<String> set = ...;// using new HashSet<>() OR new LinkedHashSet<>()
set.add("2");
set.add("1");
set.add("ab");
for(String value : set){
   System.out.println(value);
}  

HashSet output

1
ab
2

LinkedHashSet output

2
1
ab