Difference between HashSet, TreeSet, and LinkedHashSet in Java
This post will discuss the difference between HashSet, TreeSet, and LinkedHashSet classes in Java.
A Set is a collection in Java that does not allow any duplicate entries. There are different types of sets that have different features and performance. HashSet, TreeSet and LinkedHashSet are the most commonly used implementations of the Set interface, which happens to be more or less similar in functionality. This post provides an overview of some of the major differences between these implementations.
1. Overview of HashSet
A HashSet is a class that implements the Set interfaces and uses a hash table as its underlying data structure to store elements. A hash table is a data structure that maps keys to values using a hash function. In a HashSet, each element is considered as a key that maps to itself as a value and the elements can be of any type. A HashSet offers many advantages over other types of sets:
HashSetallows fast access to elements by using the hash code of the elements.HashSetdoes not maintain any order of the elements in the set, unlikeTreeSetorLinkedHashSet.HashSetdoes not allow duplicate elements in the set, unlike aList.HashSetallows null elements in the set, unlike aTreeSet.
HashSet provides several methods to manipulate the set, such as add(), remove(), contains(), etc. These methods allow us to add, delete, or check elements in the set. Here is an example of how to create and use an HashSet in Java:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
import java.util.HashSet; import java.util.Set; class Main { public static void main(String[] args) { // Create a HashSet object Set<String> set = new HashSet<>(); // Add some elements to the set set.add("Aaron"); set.add("Bella"); set.add("Casey"); System.out.println(set); // [Bella, Aaron, Casey] // Try to add a duplicate element to the set set.add("Aaron"); System.out.println(set); // [Bella, Aaron, Casey] // Remove an element from the set set.remove("Bella"); System.out.println(set); // [Aaron, Casey] // Check if an element exists in the set System.out.println("Contains Aaron: " + set.contains("Aaron")); // true // Check if a null element exists in the set System.out.println("Contains null: " + set.contains(null)); // false } } |
2. Overview of TreeSet
A TreeSet is a class that implements the Set and NavigableSet interfaces, and uses a red-black tree as its underlying data structure to store elements. A red-black tree is a self-balancing binary search tree that maintains an ordered sequence of elements. The elements in a TreeSet are sorted by default in their natural ordering or by a provided Comparator. A TreeSet offers some advantages over other types of sets:
TreeSetallows fast access to elements as it uses a self-balancing tree structure for storing the elements.TreeSetmaintains the order of the elements in the set, unlike aHashSet.TreeSetdoes not allow duplicate elements in the set, unlike aList.TreeSetdoes not allow null elements in the set, unlike aHashSetorLinkedHashSet.
TreeSet provides several methods to manipulate the set, such as add(), remove(), contains(), etc. These methods allow us to add, delete, or check elements in the set. Moreover, TreeSet also provides additional methods to navigate the set in a sorted order, such as first(), last(), lower(), higher(), etc. These methods allow us to access the first or last element in the set, or find an element that is less than or greater than a given element. For example:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
import java.util.TreeSet; class Main { public static void main(String[] args) { // Create a TreeSet object TreeSet<String> set = new TreeSet<>(); // Add some elements to the set set.add("Aaron"); set.add("Bella"); set.add("Casey"); System.out.println(set); // [Aaron, Bella, Casey] // Try to add a duplicate element to the set set.add("Aaron"); System.out.println(set); // [Aaron, Bella, Casey] // Remove an element from the set set.remove("Bella"); System.out.println(set); // [Aaron, Casey] // Check if an element exists in the set System.out.println("Contains Aaron: " + set.contains("Aaron")); // true // Access the first element in the set System.out.println("First: " + set.first()); // Aaron // Access the last element in the set System.out.println("Last: " + set.last()); // Casey // Access an element that is less than C System.out.println("Lower than C: " + set.lower("C")); // Aaron // Access an element that is greater than C System.out.println("Higher than C: " + set.higher("C")); // Casey // Try to add a null element to the set set.add(null); // NullPointerException } } |
3. Overview of LinkedHashSet
A LinkedHashSet is another class that implements the Set interface and uses a hash table and a linked list as its underlying data structure to store elements. A hash table is a data structure that maps keys to values using a hash function. A linked list is a data structure that stores elements as nodes that are connected by pointers. In a LinkedHashSet, each element is considered as a key that maps to itself as a value, where elements can be of any type. A LinkedHashSet offers some advantages over other types of sets:
LinkedHashSetallows fast access to elements by using the hash code of the elements.LinkedHashSetmaintains the order of the elements in the set, unlike aHashSet.LinkedHashSetdoes not allow duplicate elements in the set, unlike aList.LinkedHashSetallows null elements in the set, unlike aTreeSet.
LinkedHashSet provides several methods to manipulate the set, such as add(), remove(), contains(), etc. However, unlike TreeSet, it does not provide any additional methods to navigate the set in a sorted order. For example:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
import java.util.LinkedHashSet; import java.util.Set; class Main { public static void main(String[] args) { // Create a LinkedHashSet object Set<String> set = new LinkedHashSet<>(); // Add some elements to the set set.add("Aaron"); set.add("Bella"); set.add("Casey"); System.out.println(set); // [Aaron, Bella, Casey] // Try to add a duplicate element to the set set.add("Aaron"); System.out.println(set); // [Aaron, Bella, Casey] // Remove an element from the set set.remove("Bella"); System.out.println(set); // [Aaron, Casey] // Check if an element exists in the set System.out.println("Contains Aaron: " + set.contains("Aaron")); // true // Add a null element to the set set.add(null); System.out.println(set); // [Aaron, Casey, null] } } |
4. Difference between HashSet, TreeSet, and LinkedHashSet
Here are some of the main differences between HashSet, TreeSet, and LinkedHashSet in Java:
1. Implementation Details
A HashSet implementation is backed by a hash table using a HashMap instance. A TreeSet implementation is based on a TreeMap implemented as red-black tree, and LinkedHashSet is implemented using a hash table and doubly linked list. Both HashSet and LinkedHashSet classes implements the Set interface, whereas TreeSet implements the NavigableSet interface.
HashSet, TreeSet, and LinkedHashSet provides utility methods to manipulate the set, such as add, remove, contains, etc. A TreeSet provides some more methods to manipulate and navigate the set, such as first, last, lower, higher, etc.
2. Iteration Order
The most important difference between the HashSet, TreeSet, and LinkedHashSet class lies in the order in which its iterator returns contents of the set.
HashSetmakes no guarantees on the iteration order of the set or even the order will remain constant over time.TreeSet, depending on the constructor used, is iterated according to the natural ordering of its elements or according to the specifiedComparator.LinkedHashSetruns a doubly linked list through all of its elements, which defines the predictable iteration order that is the same as the order in which elements were inserted into the set.
3. Performance
Both HashSet and LinkedHashSet allows fast access to elements by using the hash code of the elements. They offers O(1) time performance for the basic operations such as add, remove, contains and size, etc. This assumes that the hash function uniformly distributes elements in the bucket. However, due to the added expense of maintaining the doubly linked list, LinkedHashSet performance is slightly lower than that of HashSet. TreeSet is slowest among all which guarantees O(log(n)) time cost for these operations since it is implemented using a red-black tree.
Also, HashSet requires less memory than TreeSet and LinkedHashSet since it uses a hash table to store its elements. LinkedHashSet has the extra overhead of a doubly linked list, and since TreeSet is implemented as a red-black tree, which takes a considerable amount of memory.
4. Null values
Both HashSet and LinkedHashSet permit a null values in the set, whereas TreeSet does not permit null values in the set by default. A TreeSet can support null only if its Comparator supports comparison on null, which is not the case with its default order.
5. Which Implementation to use?
Here are some general recommendations on how to choose between HashSet, TreeSet, and LinkedHashSet in Java:
- If you need to store a collection of unique values in a performance critical application, we can use
HashSet. - If you need to store a collection of unique values but also maintain the order of the elements according to their natural ordering or by a
Comparator, we should useTreeSet. - If you need to store a collection of unique values that maintain the insertion order of the elements, we should use
LinkedHashSet. - If you need to store a collection of unique values that also support multithreading, we should use ConcurrentSkipListSet instead. This class will ensure that the set is synchronized and thread-safe and prevent any data inconsistency or concurrency issues.
That’s all about the differences between HashSet, TreeSet, and LinkedHashSet in Java.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)