user496949 - 9 months ago 27

Java Question

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

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

.