HashSet vs TreeSet in Java

By Atul Rai | Last Updated: May 9, 2023 Previous       Next

HashSet vs TreeSet in Java- A Comparison of Set Implementations: The Set interface provides an unordered collection of unique elements in Java. Two commonly used implementations of the Set interface are HashSet and TreeSet. While both classes serve the same purpose of storing unique elements, they differ in their underlying data structures, performance characteristics, and ordering capabilities.

In this article, we will explore the differences between HashSet and TreeSet in Java with examples to help you understand when to use each implementation.

HashSet

HashSet is implemented using a hash table, which offers constant-time performance for basic operations like adding, removing, and checking for element existence (O(1) time complexity on average). The elements in a HashSet are not ordered and may appear in any random order when iterated over.

Let’s consider an example:

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        HashSet<String> names = new HashSet<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("Alice"); // Duplicate element, will be ignored

        System.out.println(names); // Output: [Bob, Alice, Charlie]
    }
}

In the above example, we create a HashSet called names to store a collection of names. As HashSet does not maintain any specific order, the output of the program may vary. Note that the duplicate element “Alice” is ignored, as HashSet guarantees uniqueness.

Post you may like: Check HashSet contains element case insensitive in Java

TreeSet

TreeSet is implemented using a self-balancing binary search tree called a Red-Black tree. This data structure provides a sorted order for the elements in the set. The time complexity for basic operations like adding, removing, and checking for element existence is O(log n), where n is the number of elements in the TreeSet.

Let’s see an example:

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        TreeSet<String> names = new TreeSet<>();
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        names.add("Alice"); // Duplicate element, will be ignored

        System.out.println(names); // Output: [Alice, Bob, Charlie]
    }
}

In this example, we create a TreeSet called names to store a collection of names. As TreeSet maintains elements in sorted order, the output is [Alice, Bob, Charlie]. The duplicate element “Alice” is ignored, as TreeSet also guarantees uniqueness.

When to use HashSet or TreeSet?

• Use HashSet when you need a collection of unique elements and order does not matter. HashSet provides faster performance for basic operations and is generally more efficient for large data sets.
• Use TreeSet when you need a collection of unique elements sorted in a specific order. TreeSet is suitable for scenarios where you require the elements to be maintained in a sorted manner.

It’s important to note that TreeSet has slightly slower performance than HashSet due to the overhead of maintaining the sorted order. Additionally, TreeSet requires elements to implement the Comparable interface or provide a custom Comparator for ordering.

In conclusion, both HashSet and TreeSet offer unique elements, but differ in terms of performance and ordering capabilities. Choose the appropriate implementation based on your specific requirements. Consider HashSet for fast and unordered operations, while TreeSet is ideal when you need sorted elements.

References

1. Set – Java Doc
2. HashSet – Java Doc
3. TreeSet – Java Doc
4. Java 8 – How to sort Set with stream.sorted()