The Set Interface

The Set interface extends the Collection interface. It represents an unordered collection of elements that does not allow duplicate elements. It is essentially a programmatic implementation of the mathematical set abstraction.

The most commonly used implementations of the Set interface are HashSet, LinkedHashSet, and TreeSet.

---

1. HashSet

The HashSet class is the default, go-to implementation of the Set interface. It stores its elements in a hash table (specifically, it is backed by a HashMap under the hood).

Key Characteristics

• No Duplicates: If you try to add a duplicate element, the add() method will simply return false and the set will not change.
• Unordered: It makes no guarantees about the iteration order of the set. The order may change over time as elements are added and removed.
• Fast Performance: It offers constant time performance $O(1)$ for basic operations (add, remove, contains), assuming the hash function disperses elements properly.
• Allows Null: It allows a single null element.

Example

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

public class LabSet1 {

  public static void main(String args[]) {
    Set<String> set = new HashSet<>();

    set.add("Apple");
    set.add("Banana");
    set.add("Orange");

    // Attempting to add a duplicate
    boolean isAdded = set.add("Apple");

    System.out.println("Was duplicate added? " + isAdded); // false

    // The order of output is unpredictable!
    for (String fruit : set) {
      System.out.println(fruit);
    }
  }
}

---

2. LinkedHashSet

The LinkedHashSet class extends HashSet. It maintains a doubly-linked list running through all of its entries.

Key Characteristics

• Predictable Iteration Order: Unlike HashSet, it maintains insertion order. When you iterate through a LinkedHashSet, elements will be returned in the exact order they were inserted.
• Slightly Slower: Because it has to maintain the linked list, it has slightly higher memory overhead and is marginally slower than HashSet for insertions and deletions.

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

public class LabSet2 {

  public static void main(String args[]) {
    Set<String> set = new LinkedHashSet<>();

    set.add("One");
    set.add("Two");
    set.add("Three");

    // Order is guaranteed to be: One, Two, Three
    System.out.println(set);
  }
}

---

3. TreeSet

The TreeSet class implements the SortedSet interface (which extends Set). It uses a Red-Black tree structure under the hood.

Key Characteristics

• Sorted Order: It stores elements in their natural ascending order (e.g., A-Z for Strings, 1-9 for Integers), or according to a custom Comparator provided at creation time.
• Slower Performance: Because it has to sort elements upon insertion, basic operations take $O(\log n)$ time.
• No Nulls: Unlike HashSet, TreeSet does not allow null elements (it will throw a NullPointerException if you try to add one).

Example

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

public class LabSet3 {

  public static void main(String args[]) {
    Set<Integer> numbers = new TreeSet<>();

    // Inserting in random order
    numbers.add(50);
    numbers.add(10);
    numbers.add(30);

    // The output will be automatically sorted: [10, 30, 50]
    System.out.println("Sorted Set: " + numbers);
  }
}

[!TIP] Summary: When to use what?

• Need maximum performance and don't care about order? Use HashSet.
• Need to maintain insertion order? Use LinkedHashSet.
• Need elements to be automatically sorted? Use TreeSet.