The Java Set Interface, Implementations and Examples
The Set interface is a collection that cannot contain duplicate elements. It models the mathematical set abstraction and is used to represent sets like below
- Cards comprising a poker hand
- Courses making up the schedule of a student
- The processes running on a machine
The Set interface contains only methods inherited from Collection and adds the restriction to prohibit the duplicate elements.
“Set” interface Java SE 8
public interface Set<E> extends Collection<E> {
// Basic operations
int size();
boolean isEmpty();
boolean contains(Object element);
boolean add(E element); //optional operation
boolean remove(Object element); //optional operation
boolean equals(Object element);
int hashCode();
Iterator<E> iterator();
// Bulk operations
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c); //optional operation
boolean removeAll(Collection<?> c); //optional operation
boolean retainAll(Collection<?> c); //optional operation
void clear(); //optional operation
// Array Operations
Object[] toArray();
<T> T[] toArray(T[] a);
}
“add” Operation of Set Interface
Adds the specified element to the set if it is not already present and this is optional operation. If the set already contains the element, the call to this method leaves the set unchanged and returns false. In combination with the restriction on constructors, this ensures that sets never contain duplicate elements.
“equals” Operation of Set Interface
Set also adds a stronger contract on the behavior of the equals and hashCode operations, allowing Set instances to be compared meaningfully even if their implementation types differ. Two Set instances are equal if they contain the same elements.
Implementation of “Set” Interface
The implementations of Set interface are:
- HashSet – It stores its elements in a hash table and it is the best performing implementation and faster than TreeSet. But there is no guarantee on the order of iteration. It is the most commonly used implementation.
- TreeSet – It stores its elements in a red-black tree and orders its elements based on their values i.e., elements will be in ascending order, according to natural order. It is slower than HashSet.
- LinkedHashSet – It is implemented as a hash table with a linked list running through it. It maintains insertion-order i.e., the order in which the elements are inserted in to the set.
Limitations of Using HashSet
One thing that you should keep in mind about HashSet is that “iteration is linear in the sum of the number of entries and the number of buckets (the capacity)”.
Thus choosing an initial capacity that is too high, can waste both space and time. On the other hand choosing an initial capacity that is too low wastes time by copying data structure each time it’s forced to increase the capacity.
If you don’t specify the initial capacity, then the default value is 16. In the past, there were some advantages when you choose prime number as initial capacity. But now it’s no longer true, because internally the capacity is always rounded up to a power of 2.
The following line of code allocates a HashSet whose initial capacity is 64
Set<String> str = new HashSet<String>(64);
Example: Set Interface and HashSet
package com.sneppets.corejava.collections;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
/**
* Program to demonstrate Set Implementations
* @author sneppets.com
*
*/
public class SetInterfaceHashSetExample {
public static void main (String[] args)
{
String[] strArray = {"John", "Peter", "Samuel", "John"};
//Order is not guaranteed
System.out.println("HashSet...Order is not guaranteed");
Set<String> s = new HashSet<String>();
checkDuplicate(s,strArray);
System.out.println(s);
//Order according to values
System.out.println();
System.out.println("TreeSet...Order according to values");
s = new TreeSet<String>();
checkDuplicate(s,strArray);
System.out.println(s);
//Order according to insertion
System.out.println();
System.out.println("LinkedHashSet...Order according to insertion ");
s = new LinkedHashSet<String>();
checkDuplicate(s,strArray);
System.out.println(s);
}
private static void checkDuplicate(Set<String> s, String[] args) {
for (int i=0; i<args.length; i++)
{
if(!s.add(args[i]))
{
System.out.println("Duplicate detected :" + args[i]);
}
System.out.println(s.size()+ " distinct words are detected: " + s);
}
}
}
Output:
HashSet...Order is not guaranteed 1 distinct words are detected: [John] 2 distinct words are detected: [John, Peter] 3 distinct words are detected: [Samuel, John, Peter] Duplicate detected :John 3 distinct words are detected: [Samuel, John, Peter] [Samuel, John, Peter] TreeSet...Order according to values 1 distinct words are detected: [John] 2 distinct words are detected: [John, Peter] 3 distinct words are detected: [John, Peter, Samuel] Duplicate detected :John 3 distinct words are detected: [John, Peter, Samuel] [John, Peter, Samuel] LinkedHashSet...Order according to insertion 1 distinct words are detected: [John] 2 distinct words are detected: [John, Peter] 3 distinct words are detected: [John, Peter, Samuel] Duplicate detected :John 3 distinct words are detected: [John, Peter, Samuel] [John, Peter, Samuel]
Example: Set Interface and TreeSet
package com.sneppets.corejava.collections;
import java.util.Set;
import java.util.TreeSet;
/**
* Program to demonstrate TreeSet
* @author sneppets.com
*/
public class SetInterfaceTreeSetExample {
public static void main (String[] args)
{
Set<String> ts = new TreeSet<String>();
ts.add("one");
ts.add("two");
ts.add("three");
ts.add("four");
ts.add("three");
System.out.println("Members of TreeSet: " + ts);
}
}
Output:
Members of TreeSet: [four, one, three, two]
Example: Set Interface and LinkedHashSet
package com.sneppets.corejava.collections;
import java.util.LinkedHashSet;
import java.util.Set;
/**
* Program to demonstrate LinkedHashSet
* @author sneppets.com
*/
public class SetInterfaceLinkedHashSetExample {
public static void main(String[] args)
{
Set<Integer> lhs = new LinkedHashSet<Integer>();
lhs.add(2);
lhs.add(1);
lhs.add(3);
lhs.add(3);
System.out.println("Members from LinkedHashSet = " + lhs);
}
}
Output:
Members from LinkedHashSet = [2, 1, 3]
Special-Purpose Set Implementations
There are two special-purpose Set implementations
- EnumSet – It is a high-performance Set implementation for enum types.All of the members of an enum set must be of the same enum type.
- CopyOnWriteArraySet – It is a Set implementation backed up by a copy-on-write array. All mutative operations, such as add, set, and remove, are implemented by making a new copy of the array; no locking is ever required.