HashSet vs. TreeSet in Java
Educative Answers TeamGrokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
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
- 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>{@Overridepublic 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:
RELATED TAGS
Grokking Modern System Design Interview for Engineers & Managers
Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.
