Difference between HashSet and TreeSet in Java

Hey everyone, welcome back to the blog! In today’s blog post, we’ll discuss two important implementations of the Set interface in Java—HashSet and TreeSet. Both are used to store unique elements, but they have different behaviors when it comes to ordering, performance, and how they store data. Let’s dive into the differences and look at some examples!”

Difference between HashSet and TreeSet in Java

1. Difference 1: HashSet uses a hash table, TreeSet uses a red-black tree

“First, let’s talk about how these sets store their elements. HashSet uses a hash table to store elements, which allows for very fast operations like adding, removing, and checking for elements. On the other hand, TreeSet uses a red-black tree, a self-balancing binary search tree, to store its elements in sorted order.”

Example:

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class SetComparison {
    public static void main(String[] args) {
        // HashSet example
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Banana");
        hashSet.add("Apple");
        hashSet.add("Cherry");
        System.out.println("HashSet Output: " + hashSet);

        // TreeSet example
        Set<String> treeSet = new TreeSet<>();
        treeSet.add("Banana");
        treeSet.add("Apple");
        treeSet.add("Cherry");
        System.out.println("TreeSet Output: " + treeSet);
    }
}

Output:

HashSet Output: [Banana, Apple, Cherry] or [Apple, Cherry, Banana] (order is unpredictable)
TreeSet Output: [Apple, Banana, Cherry] (sorted order)

2. Difference 2: HashSet does not maintain any order, TreeSet maintains elements in sorted order

“Next, let’s look at how the elements are ordered. HashSet does not guarantee any specific order of elements, so when you iterate through a HashSet, the order may seem random. In contrast, TreeSet maintains the elements in sorted order, either in their natural order (if the elements implement Comparable) or according to a custom comparator.”

Example:

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class SetOrderComparison {
    public static void main(String[] args) {
        // HashSet example
        Set<Integer> hashSet = new HashSet<>();
        hashSet.add(50);
        hashSet.add(10);
        hashSet.add(30);
        System.out.println("HashSet Output: " + hashSet); // Unordered

        // TreeSet example
        Set<Integer> treeSet = new TreeSet<>();
        treeSet.add(50);
        treeSet.add(10);
        treeSet.add(30);
        System.out.println("TreeSet Output: " + treeSet); // Sorted order
    }
}

Output:

HashSet Output: [50, 10, 30] or any other random order
TreeSet Output: [10, 30, 50] (sorted order)

3. Difference 3: HashSet allows null elements, TreeSet does not allow null elements

“HashSet allows one null element to be added to the set, as it can store any type of object, including null. However, TreeSet does not allow null values because it needs to compare elements to maintain the sorted order. Since null cannot be compared with other objects, adding null will throw a NullPointerException.”

Example:

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class SetNullComparison {
    public static void main(String[] args) {
        // HashSet example - allows null
        Set<String> hashSet = new HashSet<>();
        hashSet.add(null);
        hashSet.add("Banana");
        System.out.println("HashSet with null: " + hashSet);

        // TreeSet example - does not allow null
        Set<String> treeSet = new TreeSet<>();
        try {
            treeSet.add(null); // This will throw a NullPointerException
        } catch (NullPointerException e) {
            System.out.println("TreeSet does not allow null values");
        }
    }
}

Output:

HashSet with null: [null, Banana]
TreeSet does not allow null values

4. Difference 4: HashSet is faster for basic operations, TreeSet is slower due to sorting

“In terms of performance, HashSet is faster for basic operations like adding, removing, and checking for elements. All of these operations typically take constant time, O(1), because it uses a hash table. TreeSet, on the other hand, is slower because it has to maintain the sorted order, which means operations like adding and removing take O(log n) time.”

Example:

import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class SetPerformanceComparison {
    public static void main(String[] args) {
        // HashSet example
        Set<Integer> hashSet = new HashSet<>();
        long startTime = System.nanoTime();
        hashSet.add(100);
        hashSet.add(200);
        hashSet.add(300);
        System.out.println("HashSet contains 200: " + hashSet.contains(200));
        long endTime = System.nanoTime();
        System.out.println("HashSet operation time: " + (endTime - startTime) + " ns");

        // TreeSet example
        Set<Integer> treeSet = new TreeSet<>();
        startTime = System.nanoTime();
        treeSet.add(100);
        treeSet.add(200);
        treeSet.add(300);
        System.out.println("TreeSet contains 200: " + treeSet.contains(200));
        endTime = System.nanoTime();
        System.out.println("TreeSet operation time: " + (endTime - startTime) + " ns");
    }
}

Output:

HashSet contains 200: true
HashSet operation time: [Shorter time in nanoseconds]

TreeSet contains 200: true
TreeSet operation time: [Longer time in nanoseconds due to sorting]

Conclusion

That wraps up our comparison of HashSet and TreeSet! To summarize, HashSet is faster and ideal when you don’t need ordering, while TreeSet maintains elements in sorted order and is useful when you need sorted data. Try running these examples in your IDE and see how they perform.

Summary Table: HashSet vs TreeSet