Understanding HashSet and TreeSet

What Is a Set in Java?

A Set is a collection that does not allow duplicate elements, making it an excellent choice when uniqueness is required. Unlike a List, a Set does not maintain the order of elements (unless specified otherwise). In Java, the Set interface is part of the java.util package and supports basic operations like add(), remove(), contains(), and size(). The two most commonly used implementations of this interface are HashSet and TreeSet, each offering unique properties that make them suited to different types of applications.

1. HashSet in Java

HashSet is arguably the most widely used implementation of the Set interface. It utilizes a hash table for storing elements, meaning the order of elements is not guaranteed. This unordered nature makes HashSet a great choice when the primary goal is fast element retrieval and manipulation, without concern for the order in which elements are stored.

Key Features of HashSet:

• Unordered: Elements are stored without any specific order.
• Allows null values: HashSet permits the storage of a single null element.
• Constant time complexity: The average time complexity for operations such as add(), remove(), and contains() is O(1), though it can degrade to O(n) in rare cases when hash collisions occur.
• No insertion order: The order in which elements are inserted is not preserved.

Example Code for HashSet:

import java.util.HashSet;

public class HashSetExample {
    public static void main(String[] args) {
        // Create a HashSet
        HashSet<String> set = new HashSet<>();

        // Add elements
        set.add("Apple");
        set.add("Banana");
        set.add("Cherry");
        set.add("Apple"); // Duplicate element (will not be added)

        // Print the HashSet (unordered)
        System.out.println("HashSet contains: " + set);

        // Check for existence of an element
        if (set.contains("Banana")) {
            System.out.println("Banana is in the set.");
        }

        // Remove an element
        set.remove("Cherry");

        // Print the updated HashSet
        System.out.println("HashSet after removal: " + set);
    }
}

Code Explanation:

• HashSet<String> set = new HashSet<>();: A HashSet of strings is created.
• set.add("Apple");: Elements are added to the set. Notice how even if the same element (“Apple”) is added again, it is ignored since duplicates aren’t allowed in a Set.
• set.contains("Banana");: This method checks if a particular element exists in the set.
• set.remove("Cherry");: An element (“Cherry”) is removed from the set.
• The final output demonstrates the unordered nature of HashSet.

2. TreeSet in Java

Unlike HashSet, a TreeSet stores elements in a sorted order. This sorting is either based on their natural ordering (e.g., for numbers, alphabetical for strings) or according to a custom comparator that you provide. TreeSet is implemented using a Red-Black Tree, which ensures that the elements are always kept in a balanced state for efficient querying.

Key Features of TreeSet:

• Sorted: Elements are always sorted in ascending order, or as defined by a comparator.
• No null values: TreeSet does not allow null elements due to the nature of its sorting mechanism.
• Logarithmic time complexity: Operations such as add(), remove(), and contains() have a time complexity of O(log n) because of the underlying tree structure.
• NavigableSet: TreeSet implements the NavigableSet interface, offering additional methods like lower(), higher(), and pollFirst() for navigation and manipulation of the set.

Example Code for TreeSet:

import java.util.TreeSet;

public class TreeSetExample {
    public static void main(String[] args) {
        // Create a TreeSet
        TreeSet<Integer> set = new TreeSet<>();

        // Add elements
        set.add(10);
        set.add(20);
        set.add(5);
        set.add(15);

        // Print the TreeSet (sorted order)
        System.out.println("TreeSet contains: " + set);

        // Check for existence of an element
        if (set.contains(15)) {
            System.out.println("15 is in the set.");
        }

        // Remove an element
        set.remove(5);

        // Print the updated TreeSet
        System.out.println("TreeSet after removal: " + set);

        // Navigating the TreeSet
        System.out.println("The first element: " + set.first());
        System.out.println("The last element: " + set.last());
    }
}

Code Explanation:

• TreeSet<Integer> set = new TreeSet<>();: A TreeSet of integers is created.
• set.add(10);: Elements are added, and they are automatically sorted in ascending order.
• set.contains(15);: Checks if the number “15” is present.
• set.remove(5);: Removes the element “5” from the set.
• set.first(); and set.last();: These methods return the smallest and largest elements in the set, respectively.

Key Differences Between HashSet and TreeSet

When to Use HashSet vs TreeSet?

• Use HashSet when:
• You don’t care about the order of elements.
• You require fast, constant-time operations for adding, removing, and checking elements.
• You’re dealing with large datasets where insertion order is irrelevant.
• Use TreeSet when:
• You need elements to be sorted, whether in natural order or by a custom comparator.
• You need additional operations like range queries or finding the smallest/largest element.
• You need to store elements in an ordered manner and need efficient range-based queries.