Trusted answers to developer questions
HashSet vs. TreeSet in Java
Educative Answers TeamHashSets and TreeSets are both sets, therefore, they do not allow duplicates. Also, neither of them is thread-safe, i.e., they require manual synchronization when multiple threads try to access them. However, since both of them are separate classes in Java, there are some differences among them:
Differences
- Null values can be added
- No fixed iteration order
- Heterogenous values are allowed
- Time complexity for insertion/deletion/retrieval:
O(1)
- Implements the Set interface
- Nulls aren’t allowed[1]
- Iteration over items is in natural order or a given Comparator is used[2]
- Only homogenous values are allowed[3]
- Time complexity for the same operations:
O(log n)
- Implements the NavigableMapinterface[4]
Explanation
- A
java.lang.NullPointerExceptionis thrown when trying to insert a null into a TreeSet. - By default, a TreeSet sorts values in natural and ascending order. However, strings are sorted in their alphabetical order (“10” comes before “2” because “1” comes before “2”). A custom
Comparator<T>can be passed to the constructor of the TreeSet. This is usually done to sort a user-defined type (e.g.,Student), or to change how an existing type (e.g.,String,Integer, etc.) is sorted. An example is shown below:
import java.util.TreeSet;
import java.util.Comparator;
public class TreeComparator {
public static void main(String[] args) {
TreeSet<Student> ts = new TreeSet<>(new MyComp());
ts.add(new Student("Tom", 45));
ts.add(new Student("Jerry", 50));
ts.add(new Student("Spike", 40));
ts.forEach(System.out::println);
}
}
// Declaring a custom Comparator:
class MyComp implements Comparator<Student>{
@Override
public int compare(Student o1, Student o2) {
// Sort by marks:
return o1.getMarks().compareTo(o2.getMarks());
}
}
class Student{
String name;
Integer marks;
Student(String n, int m){
name = n;
marks = m;
}
String getName() {
return name;
}
Integer getMarks() {
return marks;
}
// Overriding toString() to use println:
public String toString() {
return name + ": " + marks;
}
}- A Collection in Java (e.g., HashSet, TreeSet, ArrayList) can be declared without specifying its type in
<>. This provides the flexibility to add elements of different data types in a heterogeneous Collection:
Declaring a Collection in the following way will be considered as a warning; nevertheless, the program will compile and execute:
HashSet hs = new HashSet();
hs.add("a string");
hs.add(10);
On the other hand, a TreeSet is a homogeneous Collection. Consequently, the first element we add to it will be considered as its only allowed data-type; otherwise, java.lang.ClassCastException will be thrown upon execution.
TreeSet ts = new TreeSet();
ts.add(10); // Type fixed as Integer.
ts.add("a string"); // Throws exception.
- Hierarchy:
Class diagram showing a part of the hierarchy
RELATED TAGS
hash
tree
set
java
data structures
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES
View all Courses
Keep Exploring
Related Courses
