Search code examples
javainterfaceset

What's the difference between HashSet and Set?

Saw the code snippet like 

Set<Record> instances = new HashSet<Record>();

I am wondering if Hashset is a special kind of set. Any difference between them?

Solution

  • A 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.

    A HashSet is typically a lot faster than a TreeSet.

    A 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).