HashSet vs. TreeSet in Java

HashSets 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:

HashSet vs. TreeSet

HashSet

TreeSet

Null values can be added

Nulls aren’t allowed

No fixed iteration order

Iteration over items is in natural order or a given Comparator is used

Heterogenous values are allowed

Only homogenous values are allowed

Time complexity for insertion/deletion/retrieval: O(1)

Time complexity for the same operations: O(log n)

Implements the Set interface

Implements the NavigableSet interface

Explanation

  1. A java.lang.NullPointerException is thrown when trying to insert a null into a TreeSet.
  2. 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;
}
}
  1. 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.
  1. Hierarchy:
Class diagram showing a part of the hierarchy
Class diagram showing a part of the hierarchy

Free Resources

Copyright ©2024 Educative, Inc. All rights reserved