What is a Set in Java and its implementations?

In Java, a Set is an interface that belongs to the Java Collections Framework. It extends the Collection interface and represents a collection that does not allow duplicate elements. As a mathematical set, it models the concept of a unique group of items.

What is a Set?

A Set is an unordered collection of unique objects. Unlike a List, it does not maintain any specific order of elements, and you cannot access elements by index. Attempting to add a duplicate element to a Set will simply be ignored, and the Set will remain unchanged. It allows at most one null element.

Key Characteristics of a Set

• No duplicate elements: Each element in a Set must be unique.
• No guaranteed order: Elements are not stored in any specific order (except for LinkedHashSet and TreeSet).
• Permits at most one null element.
• Not synchronized: Set implementations are generally not thread-safe by default (use Collections.synchronizedSet() for thread safety).
• Provides basic collection operations: add, remove, contains, size, isEmpty, clear, etc.

Common Set Implementations

HashSet

HashSet is the most common implementation of the Set interface. It stores elements by using a hash table for storage. This offers constant-time performance for the basic operations (add, remove, contains, size) assuming the hash function disperses the elements properly. HashSet does not guarantee any order of elements.

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

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

        System.out.println("Names in HashSet: " + names); // Order not guaranteed
        System.out.println("Contains Bob? " + names.contains("Bob"));
    }
}

LinkedHashSet

LinkedHashSet is an ordered version of HashSet. It maintains a doubly-linked list running through all of its entries. This means that elements are stored in the order in which they were inserted (insertion order). It offers performance almost identical to HashSet but with the added cost of maintaining the linked list.

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

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

        System.out.println("Names in LinkedHashSet: " + names); // Insertion order maintained
    }
}

TreeSet

TreeSet stores its elements in a sorted order. It implements the NavigableSet interface and is backed by a TreeMap. Elements are stored in ascending order according to their natural ordering, or by a Comparator provided at set creation time. Its performance for basic operations (add, remove, contains) is O(log n) because it's based on a balanced binary search tree (Red-Black tree). TreeSet does not permit null elements (unless a custom Comparator allows it, which is generally not recommended as it can lead to issues with natural ordering).

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

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

        System.out.println("Names in TreeSet: " + names); // Natural sorted order

        // TreeSet does not allow null (will throw NullPointerException)
        // names.add(null);
    }
}

Choosing the Right Set Implementation