Java Collections - HashSet vs. TreeSet vs. LinkedHashSet

1 minute read

Tables

Set Interface ⤴

Set interface extends Collection interface. In a set, no duplicates are allowed. Every element in a set must be unique. You can simply add elements to a set, and duplicates will be removed automatically.

collection-hierarchy

HashSet vs. TreeSet vs. LinkedHashSet ⤴

  • HashSet is Implemented using a hash table. Elements are not ordered. The add, remove, and contains methods have constant time complexity O(1).
  • TreeSet is implemented using a tree structure(red-black tree). The elements in a set are sorted, but the add, remove, and contains methods has time complexity of O(log(n)). It offers several methods to deal with the ordered set like first(), last(), headSet(), tailSet(), etc.
  • LinkedHashSet is between HashSet and TreeSet. It is implemented as a hash table with a linked list running through it, so it provides the order of insertion. The time complexity of basic methods is O(1).

Example ⤴

TreeSet Example ⤴

class Dog implements Comparable<Dog>{
	int size;
 
	public Dog(int s) {
		size = s;
	}
 
	public String toString() {
		return size + "";
	}
 
	@Override  // must have, if not, run-time error occurs: java.lang.ClassCastException
	public int compareTo(Dog o) {
	        return size - o.size;
	}
}

Let’s add some dogs to TreeSet like the following:

import java.util.Iterator;
import java.util.TreeSet;
 
public class TestTreeSet {
	public static void main(String[] args) {
		TreeSet<Dog> dset = new TreeSet<Dog>();
		dset.add(new Dog(2));
		dset.add(new Dog(1));
		dset.add(new Dog(3));
 
		Iterator<Dog> iterator = dset.iterator();
 
		while (iterator.hasNext()) {
			System.out.print(iterator.next() + " ");
		}
	}
}

The output is:

1 2 3

HashSet Example ⤴

HashSet<Dog> dset = new HashSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
	System.out.print(iterator.next() + " ");
}

Output:

5 3 2 1 4

Note: the order is not certain.

LinkedHashSet Example ⤴

LinkedHashSet<Dog> dset = new LinkedHashSet<Dog>();
dset.add(new Dog(2));
dset.add(new Dog(1));
dset.add(new Dog(3));
dset.add(new Dog(5));
dset.add(new Dog(4));
Iterator<Dog> iterator = dset.iterator();
while (iterator.hasNext()) {
	System.out.print(iterator.next() + " ");
}

The order of the output is certain and it is the insertion order:

2 1 3 5 4

References ⤴

Leave a Comment