Set

In Java, the Collections Framework is a set of classes and interfaces that provide a unified and efficient way to work with collections of objects. Among these collections, the Set interface stands out as it represents a collection that does not allow duplicate elements. This document will provide an overview of the Set interface and some of its commonly used implementing classes.

Set Interface

The Set interface is a part of the Java Collections Framework and extends the Collection interface. It defines the characteristics of a collection that does not allow duplicate elements. Here are some of the key methods in the Set interface:

• add(E e): Adds the specified element to the set if it is not already present.

• remove(Object o): Removes the specified element from the set if it is present.

• contains(Object o): Returns true if the set contains the specified element.

• size(): Returns the number of elements in the set.

• isEmpty(): Returns true if the set contains no elements.

The Set interface is implemented by several classes in Java, each with its own characteristics. Here, we'll explore some commonly used set implementations.

HashSet

HashSet is a basic implementation of the Set interface. It uses a hash table to store elements, providing constant time performance for basic operations (add, remove, contains) on average.

• Unordered collection.

• No duplicate elements.

• Provides constant-time performance for basic operations.

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

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

        // Adding elements
        hashSet.add("Apple");
        hashSet.add("Banana");
        hashSet.add("Orange");

        // Printing elements
        System.out.println("HashSet: " + hashSet);

        // Removing an element
        hashSet.remove("Banana");

        // Checking if an element is present
        System.out.println("Contains 'Banana': " + hashSet.contains("Banana"));
    }
}

---

TreeSet

TreeSet is an implementation of the NavigableSet interface, which is sorted. It uses a Red-Black tree to store elements in sorted order. The elements must be comparable or a Comparator must be provided at set creation time.

• Implements the SortedSet interface.

• Logarithmic time complexity for basic operations.

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

public class TreeSetExample {
    public static void main(String[] args) {
        // Creating a TreeSet
        Set<String> treeSet = new TreeSet<>();

        // Adding elements
        treeSet.add("Zebra");
        treeSet.add("Lion");
        treeSet.add("Giraffe");

        // Printing elements (sorted order)
        System.out.println("TreeSet: " + treeSet);

        // Removing an element
        treeSet.remove("Lion");

        // Checking if an element is present
        System.out.println("Contains 'Lion': " + treeSet.contains("Lion"));
    }
}

---

LinkedHashSet

LinkedHashSet is an implementation of the Set interface that maintains the order of insertion. It uses a hash table for storage, combined with a doubly-linked list to maintain order.

• Maintains insertion order.

• Slightly slower than HashSet due to the maintenance of order.

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        // Creating a LinkedHashSet
        Set<String> linkedHashSet = new LinkedHashSet<>();

        // Adding elements
        linkedHashSet.add("Red");
        linkedHashSet.add("Green");
        linkedHashSet.add("Blue");

        // Printing elements (order of insertion)
        System.out.println("LinkedHashSet: " + linkedHashSet);

        // Removing an element
        linkedHashSet.remove("Green");

        // Checking if an element is present
        System.out.println("Contains 'Green': " + linkedHashSet.contains("Green"));
    }
}

---

Benchmark

• Use HashSet for general-purpose cases where order doesn't matter.

• Use TreeSet when you need a sorted set.

• Use LinkedHashSet when you need to maintain insertion order.

Set Benchmark

---

Comparison Table

Feature	HashSet	TreeSet	LinkedHashSet
Underlying Data Structure	Hash table	Red-Black Tree	Hash table + Linked list
Performance	O(1)	O(log n)	O(1)
Ordering	No ordering	Natural ordering or by a provided comparator	Maintains the insertion order
Null Elements	Allows a single null element	Does not allow null elements	Allows a single null element
Duplicates	Does not allow duplicate elements	Does not allow duplicate elements	Does not allow duplicate elements
Performance	Generally faster for add, remove, and lookup	Slower than HashSet for add and remove, but has log(n) time for add, remove, and lookup	Similar to HashSet, but with slightly slower add and remove operations
Interface	Implements Set interface	Implements SortedSet interface	Implements Set interface
Use Case	When no specific order is required and duplicates are not allowed	When elements need to be sorted and duplicates are not allowed	When maintaining the insertion order is required and duplicates are not allowed
Iteration	Unordered iteration	Ordered iteration based on the natural order or a custom comparator	Ordered iteration based on insertion order
Memory Overhead	Low	High	Moderate

---

Where to use?

• HashSet is suitable when order is not important, and you need constant-time performance for basic operations.

• TreeSet is preferable when elements need to be stored in a sorted order and log(n) time complexity is acceptable.

• LinkedHashSet is useful when you want to maintain the order of insertion and still have good performance for basic operations.

In summary, the Set interface in Java Collections Framework provides a powerful and flexible way to work with collections of unique elements. The choice of which set implementation to use depends on specific requirements such as ordering, sorting, and performance characteristics. The examples provided cover some of the most commonly used Set implementations in Java.