Difference Between HashSet LinkedHashSet and TreeSet
HashSet, LinkedHashSet and TreeSet are all implementations of the Set interface.In this post lets see Difference Between HashSet LinkedHashSet and TreeSet.
1. Implementation
All these 3 implement the Set interface.
HashSet is backed by a hash table (actually a HashMap instance).
LinkedHashSet uses Hash table and linked list. It maintains a doubly-linked list running through all of its entries, thus maintaining the order of insertion.
TreeSet is a NavigableSet implementation based on a TreeMap.
2. Ordering
HashSet does not guarantee any order in which the elements are stored.
LinkedHashSet maintains the order in which the elements are inserted.
TreeSet sorts the elements in its natural ordering and ascending. You can provide a comparator to sort the elements stored in the TreeMap
3. Null values as Entries
HashSet and LinkedHashSet both allow Null elements to be added.
Null is not allowed in a TreeSet unless you specify a comparator that can handle a Null.
4. Performance
HashSet are the fastest in terms of basic opertaions like add, remove or search elements.
LinkedHashSet can be a little slower as they maintain a linked list which causes some performance overhead. But we never saw a major performance difference between HashSet and LinkedHashSet.
TreeSet are the slowest in comparision with the other two, due to the sorting done.
Lets see an example of performance when we add a lot of elements to all these Sets.
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 | package com.kscodes.collections; import java.util.HashSet; import java.util.LinkedHashSet; import java.util.TreeSet; public class SetPerformanceTest { public static void main(String args[]) { int COUNTER = 100000; long startTime = System.currentTimeMillis(); HashSet<Integer> hashSet = new HashSet<>(); for (int i = 0; i < COUNTER; i++) { hashSet.add(i); } long endTime = System.currentTimeMillis(); System.out.println("Total Time for HashSet : " + (endTime - startTime)); startTime = System.currentTimeMillis(); LinkedHashSet<Integer> linkedHashSet = new LinkedHashSet<>(); for (int i = 0; i < COUNTER; i++) { linkedHashSet.add(i); } endTime = System.currentTimeMillis(); System.out.println("Total Time for LinkedHashSet : " + (endTime - startTime)); startTime = System.currentTimeMillis(); TreeSet<Integer> treeSet = new TreeSet<>(); for (int i = 0; i < COUNTER; i++) { treeSet.add(i); } endTime = System.currentTimeMillis(); System.out.println("Total Time for TreeSet : " + (endTime - startTime)); } } |
Output
1 2 3 | Total Time for HashSet : 18 Total Time for LinkedHashSet : 20 Total Time for TreeSet : 34 |
5. When to use
Since HashSet is the fastest, for any regular operations you should use HashSet. If you need to have a maintain the insertion order of elements use LinkedHashSet. If you want sorted set, then use TreeSet but at cost of performance.
