Set is an interface in Java that represents a collection of unique elements, meaning that no two elements in a set can be the same. Java provides several implementations of Set, each with its own unique features and trade-offs. In this blog post, we will explore the different implementations of Set in Java and their use cases.
This post was originally posted at https://agrawalsuneet.github.io/blogs/set-implementation-in-java/ and later reposted on Medium.
What is a Set?
A set is a collection of unique elements. This means that each element in a set is distinct from all other elements. Sets are often used in programming to represent a collection of data that does not contain duplicates. For example, a set of names would not contain two elements with the same name.
Set Interface in Java
The Set interface is part of the java.util package and is used to create a collection of unique elements. It extends the Collection interface and adds the following methods:
- add(E element): Adds the specified element to the set if it is not already present.
- remove(Object o): Removes the specified element from the set if it is present.
- contains(Object o): Returns true if the set contains the specified element.
- size(): Returns the number of elements in the set.
- isEmpty(): Returns true if the set contains no elements.
- clear(): Removes all the elements from the set.
- iterator(): Returns an iterator over the elements in the set.
General-Purpose Set Implementations
HashSet is the most commonly used implementation of the Set interface. It is based on a hash table and does not maintain any order of the elements. The time complexity of basic operations (add, remove, contains) is O(1). The following code shows how to create a HashSet and perform basic operations on it:
Set set = new HashSet<>();
System.out.println(set.contains("apple")); // true
System.out.println(set.contains("grape")); // false
System.out.println(set.size()); // 2
System.out.println(set.isEmpty()); // true
TreeSet is an implementation of the SortedSet interface that uses a red-black tree data structure. It maintains the elements in ascending order based on their natural ordering (or a Comparator provided at the time of creation). The time complexity of basic operations (add, remove, contains) is O(log n).