Skip to main content

The Set interface

Introduction​

The Set interface in Java is a part of the Java Collection Framework and it extends the Collection interface. It is used to represent a collection of unique elements, meaning that it does not allow duplicate elements. The Set interface provides a set of methods for adding, removing, and searching for elements in the set.

One of the main characteristics of the Set interface is that it does not maintain the insertion order of elements, unlike the List interface. This means that the order of elements in a Set may change when elements are added or removed, and elements may be returned in a different order than they were added.

Here's an example of creating a Set of strings:

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

public class SetExample {
    public static void main(String[] args) {
        // creating a set of strings
        Set<String> fruits = new HashSet<>();

        // adding elements to the set
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // adding a duplicate element
        fruits.add("apple"); // Does not change the Set

        // printing the set
        System.out.println(fruits);
    }
}

In this example, we created a Set of strings and added three elements to it: "apple", "banana", and "orange". We also added a duplicate element "apple" to the set, but the set only contains one "apple" as the set does not allow duplicate elements.

The Set interface has many implementations such as HashSet, LinkedHashSet, and TreeSet, which have different characteristics and performance.

Implementations of the Set Interface​

The Set interface in Java has several implementations, each with its own characteristics and performance. The most commonly used implementations are:

HashSet​

The HashSet class is the most commonly used implementation of the Set interface. It uses a hash table for storage and provides constant time performance for the basic operations such as add(), remove(), contains(), and size(). A hash table is a data structure that uses a hash function to map keys to indices in an array, called a bucket. The main advantage of HashSet is that it provides fast performance for the basic operations, but it does not maintain the insertion order of elements. Here's an example of creating a HashSet of strings:

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

public class HashSetExample {
    public static void main(String[] args) {
        // creating a HashSet of strings
        Set<String> fruits = new HashSet<>();

        // adding elements to the set
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // printing the set
        System.out.println(fruits);
    }
}

LinkedHashSet​

The LinkedHashSet class is an implementation of the Set interface that extends HashSet. It maintains the insertion order of elements and uses a doubly-linked list to link the elements together. This means that elements are returned in the order they were inserted. The main advantage of LinkedHashSet is that it maintains the insertion order of elements, but it has a slightly higher memory overhead than HashSet.

Here's an example of creating a LinkedHashSet of strings:

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

public class LinkedHashSetExample {
    public static void main(String[] args) {
        // creating a LinkedHashSet of strings
        Set<String> fruits = new LinkedHashSet<>();

        // adding elements to the set
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // printing the set
        System.out.println(fruits); //[apple, banana, orange]
    }
}

TreeSet​

The TreeSet class is an implementation of the Set interface that provides fast performance for the basic operations and it maintains the natural ordering of elements, or elements can be ordered by a Comparator (if provided at set creation time). The TreeSet class implements the SortedSet interface, which provides a total ordering on its elements.

Here's an example of creating a TreeSet of strings:

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

public class TreeSetExample {
    public static void main(String[] args) {
        // creating a TreeSet of strings
        Set<String> fruits = new TreeSet<>();

        // adding elements to the set
        fruits.add("orange");
        fruits.add("banana");
        fruits.add("apple");

        // printing the set
        System.out.println(fruits); // [apple, banana, orange]
    }
}

When choosing which implementation of the Set interface to use, consider the following:

  • If you need fast performance for the basic operations and do not need to maintain the insertion order of elements, use HashSet.
  • If you need to maintain the insertion order of elements, use LinkedHashSet.
  • If you need to maintain the natural ordering of elements or order elements by a comparator and need range operations and navigation, use TreeSet.

Common Methods of the Set Interface​

The Set interface in Java provides a set of methods for adding, removing, and searching for elements in the set. The most commonly used methods are:

add(E e): This method is used to add an element to the set. If the set already contains the element, the method does not add the element and returns false. Here's an example of using the add() method:

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

public class AddMethodExample {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // adding a new element
        boolean added = fruits.add("mango");
        System.out.println("Mango added: " + added);

        // adding a duplicate element
        added = fruits.add("apple");
        System.out.println("Apple added: " + added); // false

        // printing the set
        System.out.println(fruits);
    }
}

The add() method returns true when an element is added successfully and returns false when the element is already in the set.

remove(Object o): This method is used to remove an element from the set. If the set does not contain the element, the method does not remove the element and returns false. Here's an example of using the remove() method:

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

public class RemoveMethodExample {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // removing an element
        boolean removed = fruits.remove("banana");
        System.out.println("Banana removed: " + removed);

        // removing a non-existing element
        removed = fruits.remove("mango");
        System.out.println("Mango removed: " + removed);

        // printing the set
        System.out.println(fruits);
    }
}

The remove() method returns true when an element is removed successfully and returns false when the element is not in the set.

clear(): This method is used to remove all elements from the set. Here's an example of using the clear() method:

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

public class ClearMethodExample {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // printing the set before clearing
        System.out.println("Before clearing: " + fruits);

        // clearing the set
        fruits.clear();

        // printing the set after clearing
        System.out.println("After clearing: " + fruits); // Empty set
    }
}

contains(Object o): This method is used to check if the set contains a specific element. It returns true if the element is in the set and false otherwise.

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

public class ContainsMethodExample {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // checking if the set contains an element
        boolean contains = fruits.contains("banana");
        System.out.println("Contains banana: " + contains);

        contains = fruits.contains("mango");
        System.out.println("Contains mango: " + contains);
    }
}

size(): This method is used to get the number of elements in the set. It returns an integer representing the number of elements in the set.

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

public class SizeMethodExample {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // getting the size of the set
        int size = fruits.size();
        System.out.println("Size of the set: " + size);
    }
}

In addition to the above-mentioned methods, the Set interface also provides an iterator() method, which returns an iterator over the elements in the set. The Iterator interface provides methods for iterating over a collection, such as hasNext() and next() methods. Here's an example of using the iterator() method:

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

public class IteratorExample {
    public static void main(String[] args) {
        Set<String> fruits = new HashSet<>();
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // getting an iterator over the set
        Iterator<String> iterator = fruits.iterator();

        // iterating over the set
        while (iterator.hasNext()) {
            String fruit = iterator.next();
            System.out.println(fruit);
        }
    }
}

You can use the hasNext() method to check if there are more elements to iterate over, and the next() method to get the next element in the set.

Set Interface and Generics​

The Set interface in Java can be used with generics to create a set of a specific type of object. Generics provide a way to specify the type of elements in a collection. By using generics, we can ensure that a collection contains elements of a specific type, and avoid runtime type casting errors.

Here's an example of creating a Set of strings using generics:

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

public class SetWithGenericsExample {
    public static void main(String[] args) {
        // creating a Set of strings using generics
        Set<String> fruits = new HashSet<>();

        // adding elements to the set
        fruits.add("apple");
        fruits.add("banana");
        fruits.add("orange");

        // printing the set
        System.out.println(fruits);
    }
}

We can now be sure that the set only contains strings and not any other types of objects.

It's also possible to create a Set of custom objects using generics. Here's an example of creating a Set of Employee objects:

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

class Employee {
    private String name;
    private int age;

    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // getters and setters ...

}

public class SetWithCustomObjectsExample {
    public static void main(String[] args) {
        // creating a Set of Employee objects using generics
        Set<Employee> employees = new HashSet<>();

        // adding elements to the set
        employees.add(new Employee("John", 25));
        employees.add(new Employee("Jane", 30));
        employees.add(new Employee("Mike", 35));

        // printing the set
        System.out.println(employees);

    }
}

In addition to creating a Set of custom objects, it's also possible to create a Set of custom objects that implements a specific interface or extends a specific class using generics. Here's an example of creating a Set of Employee objects that implement the Comparable interface:

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

class Employee implements Comparable<Employee> {
    private String name;
    private int age;

    public Employee(String name, int age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    @Override
    public String toString() {
        return "Employee{name='" + name + "', age=" + age + "}";
    }

    @Override
    public int compareTo(Employee other) {
        return this.name.compareTo(other.name);
    }
}

public class SetWithCustomObjectsAndComparableExample {
    public static void main(String[] args) {
        // creating a Set of Employee objects that implement Comparable using generics
        Set<Employee> employees = new TreeSet<>();

        // adding elements to the set
        employees.add(new Employee("John", 25));
        employees.add(new Employee("Jane", 30));
        employees.add(new Employee("Mike", 35));

        // printing the set
        System.out.println(employees);
    }
}

In this example, we implemented the Comparable interface in the Employee class and overridden the compareTo method that compares the name of the employees. We then created a Set of Employee objects that implement the Comparable interface using generics and added three Employee objects to the set. The set is now sorted by the name of the employees.

Set Interface and Autoboxing​

The Set interface in Java can be used with autoboxing to store primitive data types. Autoboxing is the automatic conversion of a primitive data type to its corresponding wrapper class. For example, autoboxing converts an int to an Integer, a boolean to a Boolean, and so on.

Here's an example of creating a Set of integers using autoboxing:

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

public class SetWithAutoboxingAndForLoopExample {
    public static void main(String[] args) {
        // creating a Set of integers using autoboxing
        Set<Integer> numbers = new HashSet<>();

        // adding elements to the set using a for loop
        for (int i = 1; i <= 5; i++) {
            numbers.add(i);
        }
        // printing the set
        System.out.println(numbers);
    }
}

In this example, we created a Set of integers using autoboxing and added elements to the set using a for loop. The int values are automatically converted to Integer objects by autoboxing inside the for loop.

note

When using autoboxing with a Set, you can't use the == operator to compare elements in the set because == compares the references, not the values. Instead, you should use the .equals() method to compare the values of the elements in the set.

CopyOnWriteArraySet​

CopyOnWriteArraySet is a thread-safe variant of the Set interface in Java. It is a concurrent collection class that uses a copy-on-write strategy, which means that all modifications to the set are made on a copy of the underlying array. This ensures that multiple threads can read the set simultaneously without the need for locks, while still allowing for safe and efficient modification. The CopyOnWriteArraySet is backed by a CopyOnWriteArrayList which provides a thread-safe way to manipulate the set. This makes CopyOnWriteArraySet well-suited for situations where many threads will be reading the set, but relatively few will be modifying it. However, because the array is copied on every modification, this class is less efficient than a standard HashSet when modifications are frequent.

note

Remember, it's CopyOnWriteArraySet, not CopyOnWriteSet!

Performance Considerations​

Time Complexity​

The add method has a time complexity of O(1) on average for HashSet and LinkedHashSet, and O(log n) for TreeSet. The remove method has a time complexity of O(1) on average for HashSet and LinkedHashSet, and O(log n) for TreeSet. The contains method has a time complexity of O(1) on average for HashSet and LinkedHashSet, and O(log n) for TreeSet.

Memory Usage​

HashSet and LinkedHashSet use internal HashMap implementation. LinkedHashSet also maintains a LinkedList of it's elements so require extra space to maintain adjacent element references

Additional Functionality of the Set Interface: Set Operations​

The Set interface in Java provides additional functionality for performing set operations such as union, intersection, and difference. Set operations are used to manipulate and compare sets of elements. In this section, we'll discuss how to perform these operations using the Set interface.

Union​

The union of two sets is a set that contains all the elements from both sets. In Java, the union can be performed using the addAll method of the Set interface. Here's an example of performing the union of two sets:

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

public class SetUnionExample {
    public static void main(String[] args) {
        Set<Integer> set1 = new HashSet<>();
        set1.add(1);
        set1.add(2);
        set1.add(3);
        set1.add(4);
        System.out.println("Set 1: " + set1);

        Set<Integer> set2 = new HashSet<>();
        set2.add(3);
        set2.add(4);
        set2.add(5);
        set2.add(6);
        System.out.println("Set 2: " + set2);

        set1.addAll(set2);
        System.out.println("Union: " + set1);
    }
}

The union of the two sets contains all the elements from both sets: {1, 2, 3, 4, 5, 6}.

Intersection​

The intersection of two sets is a set that contains only the elements that are common to both sets. In Java, the intersection can be performed using the retainAll method of the Set interface. Here's an example of performing the intersection of two sets:

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

public class SetIntersectionExample {
    public static void main(String[] args) {
        Set<Integer> set1 = new HashSet<>();
        set1.add(1);
        set1.add(2);
        set1.add(3);
        set1.add(4);
        System.out.println("Set 1: " + set1);

        Set<Integer> set2 = new HashSet<>();
        set2.add(3);
        set2.add(4);
        set2.add(5);
        set2.add(6);
        System.out.println("Set 2: " + set2);

        set1.retainAll(set2);
        System.out.println("Intersection: " + set1);
    }
}

The intersection of the two sets contains only the elements that are common to both sets: {3, 4}.

Difference​

The difference of two sets is a set that contains the elements that are present in the first set but not in the second set. In Java, the difference can be performed using the removeAll method of the Set interface. Here's an example of performing the difference of two sets:

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

public class SetDifferenceExample {
    public static void main(String[] args) {
        Set<Integer> set1 = new HashSet<>();
        set1.add(1);
        set1.add(2);
        set1.add(3);
        set1.add(4);
        System.out.println("Set 1: " + set1);

        Set<Integer> set2 = new HashSet<>();
        set2.add(3);
        set2.add(4);
        set2.add(5);
        set2.add(6);
        System.out.println("Set 2: " + set2);

        set1.removeAll(set2);
        System.out.println("Difference: " + set1);
    }
}

The difference of the two sets contains the elements that are present in the first set but not in the second set: {1, 2}.

::note These set operations will modify the original set and store the result in it. If you want to perform set operations without modifying the original set, you'll need to create a copy of the original set and perform the operations on the copy. :::