The set interface present in the java.util package and extends the Collection interface is an unordered collection of objects in which duplicate values cannot be stored. It is an interface which implements the mathematical set. This interface contains the methods inherited from the Collection interface and adds a feature which restricts the insertion of the duplicate elements. There are two interfaces which extend the set implementation namely SortedSet and NavigableSet.
The Set interface is the sub-interface of Collection Interface. It is mainly implemented by 3 general-purpose classes namely:
TreeSet - Mainly implements Red-Black Tree which is a self-balancing binary tree. Objects are stored in sorted order.
HashSet - Implements Hashing for quick search, insertion and delete operations. The objects that we insert into the HashSet does not guarantee to be inserted in the same order.
LinkedHashSet - Derived class of HashSet. Facilitates access of elements in insertion order.
Abstract Classes like the provides a skeletal implementation of the Collection interface.
Interface like SortedSet provides operations related to subset such as finding all the items greater or smaller than a given key or finding a subset in a given range
Interface like NavigableSet provides navigable operations like floor, ceil, higher, lower etc.
Declaration: The Set interface is declared as:
public interface Set extends Collection
Since Set is an interface, objects cannot be created of the typeset. We always need a class which extends this list in order to create an object. And also, after the introduction of Generics in Java 1.5, it is possible to restrict the type of object that can be stored in the Set. This type-safe set can be defined as:
// Obj is the type of the object to be stored in Set
Set set = new HashSet ();
Example 1:
// Java program to demonstrate a Set
import java.util.*;
public class GfG{
public static void main(String[] args)
{
// Set demonstration using HashSet
Set<Integer> s = new HashSet<Integer>();
// Adding elements to the Set
s.add(10);
s.add(20);
s.add(30);
// Duplicate element is skipped
s.add(20);
System.out.println(s);
}
}
Output:
[20, 10, 30]
Note:
The order of the items is not defined in a HashSet.
The order of the items are maintained in a TreeSet in a sorted order. To do this it either uses a Comparable interface implemented by the class or a Comparator interface.
When to prefer TreeSet over HashSet
TreeSet uses a Red-Black tree algorithm underneath to sort out the elements. When one needs to perform read/write operations frequently, then TreeSet is a good choice.
Sorted unique elements are required instead of unique elements. The sorted list given by TreeSet is always in ascending order.
To implement operations like ceil(), floor(), higher(), lower(), we need to use a TreeSet.
TreeSet can also implement a doubly ended queue and doubly ended priority queue for inserting or extracting max-min elements simultaneously. The TreeSet can perform all these operations in O(log n) time.
TreeSet has greater locality than HashSet. If two entries are nearby in the order, then TreeSet places them near each other in data structure and hence in memory, while HashSet spreads the entries all over memory regardless of the keys they are associated to.
LinkedHashSet is another data structure that is between these two. It provides time complexities like HashSet and maintains the order of insertion (Note that this is not sorted order, but the order in which elements are inserted).
Interesting quick Operations:
Let 2 sets be,
Set s1 = new HashSet();
Set s2 = new HashSet();
For Union of these two Sets: s1.addAll(s2) : This is used to append all of the elements from the mentioned collection(s2) to the existing set(s1). The elements are added randomly without following any specific order.
For Intersection of these two Sets: s1.retainAll(s2) : This is used to retain from this set(s1) all of its elements that are contained in the specified collection(s2).
For the Difference between these two sets: s1.removeAll(s2) : This is used to remove from this set(s1) all of its elements that are contained in the specified collection(s2).
Removing Duplicates from a Specific Collection using HashSet:
Set s = new HashSet();
For eg, to get an array(arr) with unique elements, the Collection c can be replaced by Arrays.asList(arr). If this is implemented using a TreeSet then we can also get the elements in sorted order.
Here's an edited version of your article:
The Set interface, present in the java.util package and extending the Collection interface, is an unordered collection of objects in which duplicate values cannot be stored. It is an interface that implements the mathematical set. This interface contains methods inherited from the Collection interface and adds a feature that restricts the insertion of duplicate elements. There are two interfaces that extend the set implementation, namely SortedSet and NavigableSet.
The Set interface is mainly implemented by three general-purpose classes, namely:
TreeSet: mainly implements Red-Black Tree, which is a self-balancing binary tree. Objects are stored in sorted order.
HashSet: implements Hashing for quick search, insertion, and deletion operations. The objects that we insert into the HashSet do not guarantee to be inserted in the same order.
LinkedHashSet: derived class of HashSet, facilitating access of elements in insertion order.
Abstract classes like the provides a skeletal implementation of the Collection interface, while interfaces like SortedSet provide operations related to subsets, such as finding all the items greater or smaller than a given key or finding a subset in a given range. The NavigableSet interface provides navigable operations like floor, ceil, higher, lower, etc.
Declaration: The Set interface is declared as:
public interface Set<E> extends Collection<E>
Since Set is an interface, objects cannot be created of the type set. We always need a class that extends this list to create an object. Also, after the introduction of Generics in Java 1.5, it is possible to restrict the type of object that can be stored in the Set. This type-safe set can be defined as:
// Obj is the type of the object to be stored in Set
Set<Obj> set = new HashSet<>();
Example:
// Java program to demonstrate a Set
import java.util.*;
public class GfG{
public static void main(String[] args)
{
// Set demonstration using HashSet
Set<Integer> s = new HashSet<Integer>();
// Adding elements to the Set
s.add(10);
s.add(20);
s.add(30);
// Duplicate element is skipped
s.add(20);
System.out.println(s);
}
}
Output:
[20, 10, 30]
Note:
The order of the items is not defined in a HashSet. The order of the items is maintained in a TreeSet in sorted order. To do this, it either uses a Comparable interface implemented by the class or a Comparator interface.
When to prefer TreeSet over HashSet:
- When read/write operations are frequent, TreeSet is a good choice.
- When sorted unique elements are required instead of unique elements, TreeSet is preferred.
- When operations like ceil(), floor(), higher(), lower() need to be implemented, TreeSet is a better option.
- TreeSet can also implement a doubly-ended queue and doubly-ended priority queue for inserting or extracting max-min elements simultaneously. TreeSet can perform all these operations in O(log n) time.
TreeSet has greater locality than HashSet. If two entries are nearby in the order, then TreeSet places them near each other in data structure and hence in memory, while HashSet spreads the entries all over memory regardless of the keys they are associated with.
LinkedHashSet is another data structure that is between these two. It provides time complexities like HashSet and maintains the order of insertion (Note that this is not sorted order, but the order in which elements are inserted).
Interesting quick Operations:
Let two sets be:
Set s1 = new HashSet<>();
Set s2 = new HashSet<>();
For the union of these two Sets: s1.addAll(s2). This appends all the elements from the mentioned collection(s2) to the existing set(s1). For the Union of these two Sets: s1.addAll(s2)
This method is used to add all the elements from the specified collection (s2) to the existing set (s1). It returns a boolean value indicating whether the set was modified as a result of the operation.
Example:
Set<Integer> s1 = new HashSet<>();
Set<Integer> s2 = new HashSet<>();
s1.add(1);
s1.add(2);
s2.add(2);
s2.add(3);
s1.addAll(s2);
System.out.println(s1);
Output:
[1, 2, 3]
2). For the Intersection of these two Sets: s1.retainAll(s2)
This method is used to retain only the elements that are present in both sets (s1 and s2). The resulting set will contain only those elements which are common in both sets. It returns a boolean value indicating whether the set was modified as a result of the operation.
Example:
Set<Integer> s1 = new HashSet<>();
Set<Integer> s2 = new HashSet<>();
s1.add(1);
s1.add(2);
s2.add(2);
s2.add(3);
s1.retainAll(s2);
System.out.println(s1);
Output:
[2]
3). For the Difference between these two sets: s1.removeAll(s2)
This method is used to remove all the elements from the first set (s1) that are present in the second set (s2). It returns a boolean value indicating whether the set was modified as a result of the operation.
Example:
Set<Integer> s1 = new HashSet<>();
Set<Integer> s2 = new HashSet<>();
s1.add(1);
s1.add(2);
s2.add(2);
s2.add(3);
s1.removeAll(s2);
System.out.println(s1);
Output:
[1]
Removing Duplicates from a Specific Collection using HashSet:
The HashSet class can also be used to remove duplicates from a specific collection. To remove duplicates, we need to add all the elements of the collection to the HashSet. Since the HashSet doesn't allow duplicate elements, all the duplicates will automatically be removed. We can then convert the HashSet back to the collection using the constructor of the specific collection.
Example:
List<Integer> listWithDuplicates = new ArrayList<>(Arrays.asList(1, 2, 3, 1, 2, 3, 4));
Set<Integer> setWithoutDuplicates = new HashSet<>(listWithDuplicates);
List<Integer> listWithoutDuplicates = new ArrayList<>(setWithoutDuplicates);
System.out.println(listWithoutDuplicates);
Output:
[1, 2, 3, 4]
In the above example, we first created a list with duplicate elements. We then created a HashSet from the list which automatically removed all the duplicates. Finally, we converted the HashSet back to a list using the constructor of ArrayList.
