Hashset vs Treeset

HashSet is much faster than TreeSet (constant-time versus log-time for most operations like add, remove and contains) but offers no ordering guarantees like TreeSet.

HashSet

• the class offers constant time performance for the basic operations (add, remove, contains and size).
• it does not guarantee that the order of elements will remain constant over time
• iteration performance depends on the initial capacity and the load factor of the HashSet.
  • It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.

TreeSet

• guarantees log(n) time cost for the basic operations (add, remove and contains)
• guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via its constructor) (implements SortedSet)
• doesn't offer any tuning parameters for iteration performance
• offers a few handy methods to deal with the ordered set like first(), last(), headSet(), and tailSet() etc

Important points:

• Both guarantee duplicate-free collection of elements
• It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal.
• None of these implementations are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
• LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however,it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.

So a choice of usage depends entirely on your needs but I feel that even if you need an ordered collection then you should still prefer HashSet to create the Set and then convert it into TreeSet.

• e.g. SortedSet<String> s = new TreeSet<String>(hashSet);

The TreeSet is one of two sorted collections (the other being TreeMap). It uses a Red-Black tree structure (but you knew that), and guarantees that the elements will be in ascending order, according to natural order. Optionally, you can construct a TreeSet with a constructor that lets you give the collection your own rules for what the order should be (rather than relying on the ordering defined by the elements' class) by using a Comparable or Comparator

and A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. Use this class instead of HashSet when you care about the iteration order. When you iterate through a HashSet the order is unpredictable, while a LinkedHashSet lets you iterate through the elements in the order in which they were inserted

Even after 11 years, nobody thought of mentioning a very important difference.

Do you think that if HashSet equals TreeSet then the opposite is true as well? Take a look at this code:

TreeSet<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
HashSet<String> hashSet = new HashSet<>();
treeSet.add("a");
hashSet.add("A");
System.out.println(hashSet.equals(treeSet));
System.out.println(treeSet.equals(hashSet));

Try to guess the output and then hover below snippet for seeing what the real output is. Ready? Here you go:

false
true

That's right, they don't hold equivalence relation for a comparator that is inconsistent with equals. The reason for this is that a TreeSet uses a comparator to determine the equivalence while HashSet uses equals. Internally they use HashMap and TreeMap so you should expect this behavior with the mentioned Maps as well.

Originally answered