HashSet vs LinkedHashSet vs TreeSet

• Comparison 

Features	HashSet	LinkedHashSet	TreeSet
Internal Working	HashSet internally uses HashMap for storing objects	LinkedHashSet uses LinkedHashMap internally to store objects	TreeSet uses TreeMap internally to store objects
When To Use	If you don’t want to maintain insertion order but want store unique objects	If you want to maintain insertion order of elements then you can use LinkedHashSet	If you want to sort the elements according to some Comparator then use TreeSet
Order	HashSet does not maintain insertion order	LinkedHashSet maintains insertion order of objects	While TreeSet orders of the elements according to supplied Comparator. Default, It’s objects will be placed in their natural ascending order.
Complexity of Operations	HashSet gives O(1) complicity for insertion, removing and retrieving objects	LinkedHashSet gives insertion, removing and retrieving operations performance in order O(1).	While TreeSet gives performance of order O(log(n)) for insertion, removing and retrieving operations.
Performance	HashSet performance is better according to LinkedHashSet and TreeSet.	The performance of LinkedHashSet is slow to TreeSet. The performance LinkedHashSet is almost similar to HashSet but slower because, LinkedHashSet maintains LinkedList internally to maintain the insertion order of elements	TreeSet performance is better to LinkedHashSet excluding insertion and removal operations because, it has to sort the elements after each insertion and removal operations.
Compare	HashSet uses equals() and hashCode() methods to compare the objects	LinkedHashSet uses equals() and hashCode() methods to compare it’s objects	TreeSet uses compare() and compareTo() methods to compare the objects
Null Elements	HashSet allows only one null objects	LinkedHashSet allows only one null objects.	TreeSet not allow a any null objects. If you insert null objects into TreeSet, it throws NullPointerException
Syntax	HashSet obj = new HashSet();	LinkedHashSet obj = new LinkedHashSet();	TreeSet obj = new TreeSet();

	Add	Contains	Next	Data Structure
HashSet	O(1)	O(1)	O(h/n)	Hash Table
LinkedHashSet	O(1)	O(1)	O(1)	Hash Table + Linked List
TreeSet	O(log n)	O(log n)	O(log n)	Red-black tree

• Details

HashSet

1. Implements Set -> Collection

2. Duplicates not allowed (returns false, if duplicate is added, no compile time or runtime error)

3. Insertion order NOT preserved, null insertion allowed, heterogeneous objects allowed

4. To be used when frequent operation is search

5. Constructors (Common for all Hash implemented collections)

1. Default (with initialCapacity as 16 and fillRatio: 0.75 i.e. new HashSet will be created when existing one is filled 75%)

2. int initialCapacity = Creates with predefined size = initialCapacity and fillRatio = 0.75

3. int initialCapacity, float fillRatio = Creates with predefined initialCapacity & fillRatio

4. Collections C = convert any collection to HashSet

LinkedHashSet

1. Extends HashSet which Implements Set -> Collection

2. Based on Hashtable + LinkedList

3. LinkedHashSet is same HashSet except one difference that in LinkedHashSet insertion order is preserved 

4. Best choice to develop cache based applications

TreeSet

1. Duplicates are not allowed

2. Null allowed only in empty TreeSet as first element, for rest NullPointerException due to comparison i.e. null.equals()

3. Insertion order NOT preserved, but elements are inserted according to sorting order

4. Heterogeneous objects are not allowed (if tried, runtime exception ‘ClassCastException’)

5. Methods from SortedSet: 

1. first(): first element in the set

2. last(): last element in the set

3. headSet(ele): elements less than or equal to ‘ele’

4. tailSet(ele): greater than or equal to ‘ele’, 

5. subSet(ele1, ele2): >= ele1 and <= ele2

6. comparator(): returns null, if natural order is used

6. Constructors

1. Default (default natural sorting order)

2. Comparator C: Customized sorting order defined by comparator object

3. Collections C = convert any collection to TreeSet

4. SortedSet S = convert SortedSet collection to TreeSet

7. If TreeSet is defined for an object for which natural sorting is not available i.e. any objects other than numbers & strings, we MUST use Comparator constructor, else we will get ClassCastException