Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

hash
tree
set
java
data structures

HashSet vs. TreeSet in Java

Educative Answers Team

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:

Differences

HashSet

  • 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


TreeSet

  • 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

  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:
svg viewer
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