TreeSet, LinkedHashSet and HashSet all are implementation of Set interface and by virtue of that, they follows contract of Set interface i.e. they do not allow duplicate elements. Despite being from same type hierarchy, there are lot of difference between them; which is important to understand, so that you can choose most appropriate Set implementation based upon your requirement. By the way difference between TreeSet and HashSet or LinkedHashSet is also one of the popular Java Collection interview question, not as popular as Hashtable vs HashMap or ArrayList vs Vector but still appears in various Java interviews. In this article we will see difference between HashSet, TreeSet and LinkedHashSet on various points e.g. Ordering of elements, performance, allowing null etc and then we will see When to use TreeSet or LinkedHashSet or simply HashSet in Java.
Difference between TreeSet, LinkedHashSet and HashSet in Java
TreeSet, LinkedHashSet and HashSet in Java
are three Set implementation in collection framework and like many others they
are also used to store objects. Main feature of TreeSet is
sorting, LinkedHashSet is
insertion order and HashSet is just general purpose
collection for storing object. HashSet is implemented using HashMap in Java while TreeSet
is implemented using TreeMap. TreeSet is a SortedSet
implementation which allows it to keep elements in the sorted order defined by
either Comparable or Comparator interface.
Comparable is used for natural order sorting and Comparator for custom order sorting of
objects, which can be provided while creating instance of TreeSet. Anyway before seeing
difference between TreeSet, LinkedHashSet and HashSet, let's see
some similarities between them:
2) Thread safety : HashSet, TreeSet and LinkedHashSet are not thread-safe, if you use them
in multi-threading environment where at least one Thread modifies Set you need to externally synchronize them.
3) Fail-Fast Iterator : Iterator returned by TreeSet, LinkedHashSet and HashSet are fail-fast Iterator. i.e. If Iterator is modified after its creation by any way other than Iterators remove() method, it will throw ConcurrentModificationException with best of effort. read more about fail-fast vs fail-safe Iterator here
null : Both HashSet and LinkedHashSet allows null but TreeSet doesn't allow null but TreeSet doesn't allow null and throw java.lang.NullPointerException when you will insert null into TreeSet. Since TreeSet uses compareTo() method of respective elements to compare them which throws NullPointerException while comparing with null, here is an example:
Comparison : HashSet and LinkedHashSet uses equals() method in Java for comparison but TreeSet uses compareTo() method for maintaining ordering. That's why compareTo() should be consistent to equals in Java. failing to do so break general contact of Set interface i.e. it can permit duplicates.
TreeSet vs HashSet vs LinkedHashSet - Example
Let’s compare all these Set implementation on some points by writing Java program. In this example we are demonstrating difference in ordering, time taking while inserting 1M records among TreeSet, HashSet and LinkedHashSet in Java. This will help to solidify some points which discussed in earlier section and help to decide when to use HashSet, LinkedHashSet or TreeSet in Java.
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
/**
* Java program to demonstrate difference between TreeSet, HashSet and LinkedHashSet
* @author
*/
public class SetComparision {
public static void main(String args[]){
HashSet<String> fruitsStore = new HashSet<String>();
LinkedHashSet<String> fruitMarket = new LinkedHashSet<String>();
TreeSet<String> fruitBuzz = new TreeSet<String>();
for(String fruit: Arrays.asList("mango", "apple", "banana")){
fruitsStore.add(fruit);
fruitMarket.add(fruit);
fruitBuzz.add(fruit);
}
System.out.println("Ordering in HashSet :" + fruitsStore);
System.err.println("Order of element in LinkedHashSet :" + fruitMarket);
System.out.println("Order of objects in TreeSet :" + fruitBuzz);
Set<Integer> numbers = new HashSet<Integer>();
long startTime = System.nanoTime();
for(int i =0; i<10000000; i++){
numbers.add(i);
}
long endTime = System.nanoTime();
System.out.println("Total time to insert 10M elements in HashSet in sec : "
// LinkedHashSet performance Test – inserting 10M objects
startTime = System.nanoTime();
for(int i =0; i<10000000; i++){
numbers.add(i);
}
endTime = System.nanoTime();
System.out.println("Total time to insert 10M elements in LinkedHashSet in sec : "
numbers = new TreeSet<Integer>();
startTime = System.nanoTime();
for(int i =0; i<10000000; i++){
numbers.add(i);
}
endTime = System.nanoTime();
System.out.println("Total time to insert 10M elements in TreeSet in sec : "
}
}
Output
Ordering in HashSet :[banana, apple, mango]
Order of element in LinkedHashSet :[mango, apple, banana]
Order of objects in TreeSet :[apple, banana, mango]
Total time to insert 10M elements in HashSet in sec : 3564570637
Total time to insert 10M elements in LinkedHashSet in sec : 3511277551
Total time to insert 10M elements in TreeSet in sec : 10968043705
Since all three implements Set interface they can be used for common Set operations like not allowing duplicates but since HashSet, TreeSet and LinkedHashSet has there special feature which makes them appropriate in certain scenario. Because of sorting order provided by TreeSet, use TreeSet when you need a collection where elements are sorted without duplicates. HashSet are rather general purpose Set implementation, Use it as default Set implementation if you need a fast, duplicate free collection. LinkedHashSet is extension of HashSet and its more suitable where you need to maintain insertion order of elements, similar to List without compromising performance for costly TreeSet. Another use of LinkedHashSet is for creating copies of existing Set, Since LinkedHashSet preservers insertion order, it returns Set which contains same elements in same order like exact copy. In short, although all three are Set interface implementation they offer distinctive feature, HashSet is a general purpose Set while LinkedHashSet provides insertion order guarantee and TreeSet is a SortedSet which stores elements in sorted order specified by Comparator or Comparable in Java.
Here is code example of LinkedHashSet which demonstrate How LinkedHashSet can be used to copy objects from one Set to another without losing order. You will get exact replica of source Set, in terms of contents and order. Here static method copy(Set source) is written using Generics, This kind of parameterized method provides type-safety and help to avoid ClassCastException at runtime.
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
/**
* Java program to copy object from one HashSet to another using LinkedHashSet.
* LinkedHashSet preserves order of element while copying elements.
*
* @author Javin
*/
public class SetUtils{
public static void main(String args[]) {
HashSet<String> source = new HashSet<String>(Arrays.asList("Set, List, Map"));
System.out.println("source : " + source);
Set<String> copy = SetUtils.copy(source);
System.out.println("copy of HashSet using LinkedHashSet: " + copy);
}
/*
* Static utility method to copy Set in Java
*/
public static <T> Set<T> copy(Set<T> source){
return new LinkedHashSet<T>(source);
}
}
Output:
source : [Set, List, Map]
copy of HashSet using LinkedHashSet: [Set, List, Map]
How to sort ArrayList in descending order in Java
4 ways to loop Map in Java with examples
How to convert List to Array in Java
How to create read only or unmodifiable Collection in Java
How to convert Collection to coma separated String in Java
10 example of Hashtable in Java - tutorial
No comments:
Post a Comment