What’s the difference between HashSet and Set?

Set represents a generic “set of values”. A TreeSet is a set where the elements are sorted (and thus ordered), a HashSet is a set where the elements are not sorted or ordered.

HashSet is typically a lot faster than a TreeSet.

TreeSet is typically implemented as a red-black tree (See http://en.wikipedia.org/wiki/Red-black_tree – I’ve not validated the actual implementation of sun/oracle’s TreeSet), whereas a HashSet uses Object.hashCode() to create an index in an array. Access time for a red-black tree is O(log(n)) whereas access time for a HashSet ranges from constant-time to the worst case (every item has the same hashCode) where you can have a linear search time O(n).

Leave a Comment