HashSet vs. TreeSet vs. LinkedHashSet

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 in algorithm book). 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).

TreeSet Example

TreeSet<Integer> tree = new TreeSet<Integer>(); tree.add(12); tree.add(63); tree.add(34); tree.add(45);   Iterator<Integer> iterator = tree.iterator(); System.out.print("Tree set data: "); while (iterator.hasNext()) { System.out.print(iterator.next() + " "); }

Output is sorted as follows:

Tree set data: 12 34 45 63 

Now let's define a Dog class as follows:

class Dog { int size;   public Dog(int s) { size = s; }   public String toString() { return 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() + " "); } } }

Compile ok, but run-time error occurs:

Exception in thread "main" java.lang.ClassCastException: collection.Dog cannot be cast to java.lang.Comparable
 at java.util.TreeMap.put(Unknown Source)
 at java.util.TreeSet.add(Unknown Source)
 at collection.TestTreeSet.main(TestTreeSet.java:22)

Because TreeSet is sorted, the Dog object need to implement java.lang.Comparable's compareTo() method like the following:

class Dog implements Comparable<Dog>{ int size;   public Dog(int s) { size = s; }   public String toString() { return size + ""; }   @Override public int compareTo(Dog o) { return size - o.size; } }

References

https://www.programcreek.com/2013/03/hashset-vs-treeset-vs-linkedhashset/

The output is:

1 2 3