Understanding HashSet, LinkedHashSet, and TreeSet in Java

HashSet, LinkedHashSet, and TreeSet in Java are commonly used classes that implement the Set interface from the Java Collections Framework. They are used for storing unique elements – in other words, they do not allow duplicates. However, they each have different characteristics and use cases. Let's look into each of these Set implementations and understand when to use which, complemented by examples.

HashSet

HashSet is the most common Set implementation. It stores elements in a hash table, which allows for fast execution times for basic operations, like add, remove, contains and size.

Key features of HashSet:

• It does not maintain any order of elements, meaning you cannot predict in which order elements will be returned.
• The time complexity for basic operations (add, remove, contains and size) is constant time O(1), assuming the hash function disperses elements properly among the buckets.
• It allows the insertion of a null element.

Example of using HashSet:

java
import java.util.HashSet;

public class Main {
    public static void main(String[] args) {
        HashSet<String> hSet = new HashSet<String>();

        hSet.add("Apple");
        hSet.add("Banana");
        hSet.add("Cherry");
        hSet.add("Apple"); // This will not be added as "Apple" is already present in the set

        System.out.println("HashSet: " + hSet); // Output order may vary
    }
}        

LinkedHashSet

LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. This linked list defines the iteration ordering, which is the order in which elements were inserted into the set (insertion-order).

Key features of LinkedHashSet:

• It maintains the insertion order of elements during iteration.
• The time complexity for basic operations is almost the same as HashSet, i.e., O(1).
• It also allows one null element.

Example of using LinkedHashSet:

java
import java.util.LinkedHashSet;

public class Main {
    public static void main(String[] args) {
        LinkedHashSet<String> lhSet = new LinkedHashSet<String>();

        lhSet.add("Apple");
        lhSet.add("Banana");
        lhSet.add("Cherry");

        System.out.println("LinkedHashSet: " + lhSet); // Output will maintain insertion order
    }
}        

TreeSet

TreeSet is a NavigableSet implementation that uses a Tree for storage. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used.

Key features of TreeSet:

• It maintains the elements in a sorted (ascending) order.
• The basic operations (add, remove and contains) offer guaranteed log(n) time cost as it uses a red-black tree in the background.
• It does not allow a null element as it compares the elements for sorting.

Example of using TreeSet:

java
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) {
        TreeSet<String> tSet = new TreeSet<String>();

        tSet.add("Apple");
        tSet.add("Banana");
        tSet.add("Cherry");

        System.out.println("TreeSet: " + tSet); // Output will be in sorted order
    }
}        

When to Use HashSet, LinkedHashSet, or TreeSet

The choice between HashSet, LinkedHashSet, and TreeSet should depend on your specific requirements:

Use HashSet when:

• You want a general-purpose Set implementation.
• You don't need any ordering of elements.
• You want to maximize performance and don't care about the order in which elements are stored or displayed.

Use LinkedHashSet when:

• You care about the iteration order. It maintains the insertion order during iteration.
• You want a compromise between the unordered HashSet and the sorted TreeSet while keeping almost the same performance (O(1)).

Use TreeSet when:

• You want to maintain a sorted set according to the natural ordering of its elements or custom sorting defined by a comparator.
• You are okay with slightly lower performance for adding or removing elements (O(log(n)) instead of O(1)).
• You need features provided by the NavigableSet interface, like retrieving elements greater or smaller than a certain value.

Always choose the right Set implementation based on your specific needs and performance requirements. Experiment and benchmark if you are unsure about the performance implications of your choice.