HashSet, TreeSet and LinkedHashSet

The java.util.Set interface denotes a Collection that does not allow duplicate elements.

The three mostly used implementations of Map in Java are HashMap, TreeMap, and LinkedHashMap :—

HashMap is implemented as a hash table, and there is no ordering of elements.
TreeMap is implemented based on red-black tree structure, and it is ordered collection of elements.
LinkedHashMap preserves the insertion order of elements.

Set Methods

Some of the useful Set methods are as follows −

int size(): to get the number of elements in the Set.
boolean isEmpty(): to check if Set is empty or not.
boolean contains(Object o): Returns true if this Set contains the specified element.
Iterator iterator(): Returns an iterator over the elements in this set. The elements are returned in no particular order.
Object[ ] toArray(): Returns an array containing all of the elements in this set. If this set makes any guarantees as to what order its elements are returned by its iterator, this method must return the elements in the same order.
boolean add(E e): Adds the specified element to this set if it is not already present (optional operation).
boolean remove(Object o): Removes the specified element from this set if it is present (optional operation).
boolean removeAll(Collection c): Removes from this set all of its elements that are contained in the specified collection (optional operation).
boolean retainAll(Collection c): Retains only the elements in this set that are contained in the specified collection (optional operation).
void clear(): Removes all the elements from the set.
Iterator iterator(): Returns an iterator over the elements in this set.

Example

The following program illustrates different methods supported by the Set class −

SetsDemo.java

import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.TreeSet;

public class SetsDemo {

    public static void main(String[] args) {
        // Create HashSet object
        HashSet<Integer> hSet = new HashSet<Integer>();
        
        // Create TreeSet object
        TreeSet<Integer> tSet = new TreeSet<>();
        
        // Create LinkedHashSet object
        LinkedHashSet<Integer> lhSet = new LinkedHashSet<>();

        // Add three objects in HashSet, TreeSet and LinkedHashSet
        for (Integer val : Arrays.asList(50, 30, 10, 40, 20)) {
            hSet.add(val);
            tSet.add(val);
            lhSet.add(val);
        }
        
        System.out.println("HashSet: " + hSet);
                   
        //Removing element on the basis of specified condition  
        hSet.removeIf(val->(val==30));
        System.out.println("After invoking removeIf() method: "+ hSet);  
        
        //Removing all the elements available in the HashSet  
        hSet.clear();  
        System.out.println("After invoking clear() method: " + hSet);
        
        //Adding new elements
        hSet.add(60);
        hSet.add(70);
        System.out.println("After new additions: " + hSet);
        
        //Removing all the new elements from HashSet  
        hSet.removeAll(hSet);  
        System.out.println("After invoking removeAll() method: " + hSet);  
        
        System.out.println("\nTreeSet: " + tSet);
        System.out.println("First element of the TreeSet is: " + tSet.first());
        System.out.println("Last element of the TreeSet is: " + tSet.last());
        
        // Using higher()
        System.out.println("Using higher: " + tSet.higher(30));
        // Using lower()
        System.out.println("Using lower: " + tSet.lower(20));
        // Using headSet() with specified boolean value
        System.out.println("Using headSet with boolean value: " + tSet.headSet(40, true));
        // Using tailSet() with specified boolean value
        System.out.println("Using tailSet with boolean value: " + tSet.tailSet(30, false));
        // Using pollFirst()
        System.out.println("Removed First Element: " + tSet.pollFirst());
        // Using pollLast()
        System.out.println("Removed Last Element: " + tSet.pollLast());
        System.out.println("New TreeSet: " + tSet);
        
        
        System.out.println("\nLinkedHashSet: " + lhSet);
        // Calling the iterator() method
        Iterator<Integer> iterate = lhSet.iterator();
        System.out.print("LinkedHashSet using Iterator: ");
        // Accessing elements
        while(iterate.hasNext()) {
            System.out.print(iterate.next() + " ");
        }
        System.out.println();
        
        LinkedHashSet<Integer> result; // for storing result
        LinkedHashSet<Integer> numbers1 = new LinkedHashSet<>(Arrays.asList(10, 20, 30, 40));
        LinkedHashSet<Integer> numbers2 = new LinkedHashSet<>(Arrays.asList(40, 50, 60));
        System.out.println("Numbers1: " + numbers1);
        System.out.println("Numbers2: " + numbers2);
        
        // Union of two sets numbers1 and numbers2
        result = numbers1;
        result.addAll(numbers2);
        System.out.println("Union is: " + result);
        // Intersection of two sets numbers1 and numbers2
        result = new LinkedHashSet<>(Arrays.asList(10, 20, 30, 40)); // result is now numbers1
        result.retainAll(numbers2);
        System.out.println("Intersection is: " + result);
        // Difference between two sets numbers1 and numbers2
        result = new LinkedHashSet<>(Arrays.asList(10, 20, 30, 40)); // result is now numbers1
        result.removeAll(numbers2);
        System.out.println("Difference is: " + result);
    }
}

Output:

HashSet: [50, 20, 40, 10, 30]
After invoking removeIf() method: [50, 20, 40, 10]
After invoking clear() method: []
After new additions: [70, 60]
After invoking removeAll() method: []

TreeSet: [10, 20, 30, 40, 50]
First element of the TreeSet is: 10
Last element of the TreeSet is: 50
Using higher: 40
Using lower: 10
Using headSet with boolean value: [10, 20, 30, 40]
Using tailSet with boolean value: [40, 50]
Removed First Element: 10
Removed Last Element: 50
New TreeSet: [20, 30, 40]

LinkedHashSet: [50, 30, 10, 40, 20]
LinkedHashSet using Iterator: 50 30 10 40 20 
Numbers1: [10, 20, 30, 40]
Numbers2: [40, 50, 60]
Union is: [10, 20, 30, 40, 50, 60]
Intersection is: [40]
Difference is: [10, 20, 30]

Comparison among HashSet, LinkedHashSet and TreeSet

HashSet, TreeSet and LinkedHashSet are all implementations of the Set interface. The following discussion provides comparative study among them :—

1. Implementation

All these 3 implement the Set interface.
HashSet is backed by a hash table (actually a HashMap instance).
LinkedHashSet uses Hash table and linked list. It maintains a doubly-linked list running through all of its entries, thus maintaining the order of insertion.
TreeSet is a NavigableSet implementation based on a TreeMap.

2. Ordering

HashSet does not guarantee any order in which the elements are stored.
LinkedHashSet maintains the order in which the elements are inserted.
TreeSet sorts the elements in its natural ordering and ascending. You can provide a comparator to sort the elements stored in the TreeMap

3. Null values as Entries

HashSet and LinkedHashSet both allow Null elements to be added.
Null is not allowed in a TreeSet unless you specify a comparator that can handle a Null.

4. Performance

HashSet are the fastest in terms of basic operations like add, remove or search elements.
LinkedHashSet can be a little slower as they maintain a linked list which causes some performance overhead. But we never saw a major performance difference between HashSet and LinkedHashSet.
TreeSet are the slowest in comparision with the other two, due to the sorting done.

When to use HashSet, TreeSet and LinkedHashSet:

HashSet: If we don’t want to maintain insertion order but want to store unique objects.

TreeSet: If we want to sort the elements according to some Comparator then use TreeSet.

LinkedHashSet: If we want to maintain insertion order of elements then we can use LinkedHashSet.