HashSet vs LinkedHashSet vs TreeSet in Java

In this article, we will learn the differences between HashSet, LinkedHashSet, and TreeSet in Java with examples.

HashSet: Implements the Set interface using a hash table. It does not guarantee any specific order of elements. 

LinkedHashSet: Extends HashSet and uses a linked list to maintain the insertion order of elements.

TreeSet: Implements the NavigableSet interface and is based on a Red-Black tree structure. It ensures the elements are sorted according to their natural ordering or a custom comparator is provided during set creation.

HashSet vs LinkedHashSet vs TreeSet: Key Points Comparison 

Underlying Data Structure: 

HashSet: Uses a hash table for storing elements. 

LinkedHashSet: Uses both a hash table and a linked list. The hash table provides the primary structure, while the linked list maintains the order of elements. 

TreeSet: Uses a Red-Black tree (a type of balanced binary search tree). 

Ordering of Elements: 

HashSet: This does not guarantee any order. 

LinkedHashSet: Maintains the order of elements based on their insertion order. 

TreeSet: Elements are stored in their natural order or according to a custom comparator if provided during set creation. 

Performance:

HashSet: Offers constant time performance (O(1)) for basic operations (add, remove, contains) assuming the hash function disperses the elements properly. 

LinkedHashSet: Nearly identical to HashSet in performance but with slight overhead due to maintenance of the linked list. 

TreeSet: Offers log(n) time cost for basic operations (add, remove, contains) because of the tree structure. 

Null Handling: 

HashSet: Can contain one null element. 

LinkedHashSet: Can also contain one null element. 

TreeSet: Cannot contain null if using natural ordering, because it requires elements to be comparable. If using a custom comparator, it can only contain null if the comparator can handle it. 

Memory Overhead: 

HashSet: Moderate.

LinkedHashSet: Higher due to the added pointers for the linked list. 

TreeSet: Relatively high because of the tree structure. 

Use-cases: 

HashSet: When you just need a collection without duplicates and don't care about order.

LinkedHashSet: When you need a collection without duplicates and want to maintain the order of insertion. 

TreeSet: When you want a sorted set or need operations like "give me the highest/lowest element" or "give me elements in a range." 

Iteration: 

HashSet: Iteration order is unpredictable. 

LinkedHashSet: Iterates in the order of insertion or access. 

TreeSet: Iterates in the ascending order of elements. 

Thread Safety: 

All three sets are not thread-safe. External synchronization or concurrent set versions are required for multi-threaded scenarios.

Examples: 

Using HashSet:

Set<String> fruits = new HashSet<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
fruits.add("Apple"); // Duplicates are ignored

System.out.println(fruits);

Output:

[Cherry, Banana, Apple]

The order can be different since HashSet doesn't guarantee any order. 

Using LinkedHashSet:

Set<String> fruits = new LinkedHashSet<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");
fruits.add("Apple"); // Duplicates are ignored

System.out.println(fruits);

Output:

[Apple, Banana, Cherry]

The order of insertion is preserved in LinkedHashSet.

Using TreeSet:

Set<String> fruits = new TreeSet<>();
fruits.add("Apple");
fruits.add("Banana");
fruits.add("Cherry");

System.out.println(fruits);

Output:

[Apple, Banana, Cherry]

Elements are in sorted (natural) order in TreeSet.

HashSet vs LinkedHashSet vs TreeSet: Summary Table

Conclusion

Use HashSet when you need a collection that prohibits duplicates and doesn't require maintaining any specific order of elements. Most efficient in terms of performance. 

Use LinkedHashSet when you want to maintain the order of element insertion. Particularly useful in cache-like structures.

Use TreeSet when you want a sorted set. It's invaluable when you need operations like "give me the highest/lowest element" or "give me elements in a range."

Related Interview QA

• Difference Between List and Set in Java
• Difference Between Collection and Collections in Java
  
• Difference Between Array and ArrayList in Java
  
• Difference between ArrayList and LinkedList in Java
• Difference Between HashSet and LinkedHashSet in Java
• Difference Between HashSet and TreeSet in Java
• HashSet vs LinkedHashSet vs TreeSet in Java
• Difference Between HashMap and HashTable in Java
• Difference Between HashSet and HashMap in Java
• HashMap vs LinkedHashMap in Java
• Difference between HashMap, LinkedHashMap, and TreeMap in Java
• Collections vs Streams in Java