What's the difference between HashSet and Set?

java interface set
user496949 picture user496949 · Feb 28, 2011 · Viewed 83.3k times · Source

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?

Answer

Erik picture Erik · Feb 28, 2011

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

Related questions

Implements vs extends: When to use? What's the difference?

Please explain in an easy to understand language or a link to some article.

Read More
How should I have explained the difference between an Interface and an Abstract class?

In one of my interviews, I have been asked to explain the difference between an Interface and an Abstract class. Here's my response: Methods of a Java interface are implicitly abstract and cannot have implementations. A Java abstract class can …

Read More
Type List vs type ArrayList in Java

(1) List<?> myList = new ArrayList<?>(); (2) ArrayList<?> myList = new ArrayList<?>(); I understand that with (1), implementations of the List interface can be swapped. It seems that (1) is typically used in an application regardless of need (…

Read More