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.

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 Implementation

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<String> set = new HashSet<>();
set.add("apple");
set.add("banana");
set.add("orange");
System.out.println(set.contains("apple")); // true
System.out.println(set.contains("grape")); // false
set.remove("orange");
System.out.println(set.size()); // 2
set.clear();
System.out.println(set.isEmpty()); // true

TreeSet Implementation

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). The following code shows how to create a TreeSet and perform basic operations on it:

Set<Integer> set = new TreeSet<>();
set.add(5);
set.add(3);
set.add(8);
System.out.println(set.first()); // 3
System.out.println(set.last()); // 8
System.out.println(set.contains(5)); // true
set.remove(8);
System.out.println(set.size()); // 2

LinkedHashSet Implementation

LinkedHashSet is an implementation of the Set interface that maintains the insertion order of elements. It is implemented as a hash table with a linked list running through it, so it provides the efficiency of HashSet along with the ordered traversal of elements. The time complexity of basic operations (add, remove, contains) is O(1). The following code shows how to create a LinkedHashSet and perform basic operations on it:

Set<String> set = new LinkedHashSet<>();
set.add("apple");
set.add("banana");
set.add("orange");
System.out.println(set); // [apple, banana, orange]
set.remove("banana");
System.out.println(set); // [apple, orange]

Special-Purpose Set Implementations

EnumSet

EnumSet is a specialized implementation of Set that is designed to work with enum types. It is highly efficient and provides constant time performance for basic operations such as add, remove, contains, and size. EnumSet uses bit vectors to represent the elements and provides a compact and efficient representation for sets of enum values.

Here is an example of creating an EnumSet and adding elements to it:

enum Fruit {
    APPLE, BANANA, ORANGE
}

Set<Fruit> set = EnumSet.of(Fruit.APPLE, Fruit.BANANA);

ConcurrentSkipListSet

ConcurrentSkipListSet is a thread-safe implementation of Set that is optimized for concurrent access. It uses a skip list data structure to store the elements and provides log(n) time performance for basic operations such as add, remove, contains, and size. ConcurrentSkipListSet is well-suited for multi-threaded applications where multiple threads need to access the set concurrently.

Here is an example of creating a ConcurrentSkipListSet and adding elements to it:

Set<String> set = new ConcurrentSkipListSet<>();
set.add("apple");
set.add("banana");
set.add("orange");

CopyOnWriteArraySet

CopyOnWriteArraySet is a thread-safe implementation of the Set interface in Java, which means that it can be accessed and modified by multiple threads concurrently without any synchronization issues. This implementation is based on the Copy-on-write (COW) technique, which means that any modification operation on the Set creates a new copy of the underlying data structure, which can be modified without affecting the original set.

In other words, when an element is added, removed, or replaced in the set, a new copy of the entire set is created, and the modification is made to the new copy, leaving the original set unchanged. This ensures that any ongoing read operations on the original set are not affected by the modification, and they can continue to access the old data.

Conclusion

In conclusion, the Set interface in Java provides a convenient way to store a collection of unique elements. The three most commonly used implementations of the Set interface are HashSet, TreeSet, and LinkedHashSet. HashSet provides constant time performance for basic operations, TreeSet maintains elements in ascending order, and LinkedHashSet maintains the insertion order of elements.

Tags: Java

Set Implementation in Java