# Java: Sets

Sets are collections that allow only one object with a given value in them. The java.util.Set interface is a subinterface of Collection. There are two very useful concrete classes that implements sets:

- `java.util.HashSet` is implemented with a hash table. Access time is O(1). Entries are unsorted.
- `java.util.TreeSet` is implemented as a balanced binary tree. Access time is O(log N). Entries are sorted.

## Set interface has all Collection interface methods

Sets implement all Collection methods.

## HashSet class constructors

HashSet is implmented with an underlying HashMap. In addition to implemented the Set interface methods, HashSet has the following constructors.

Result | Constructor | Description
--- | --- | ---
`hset =` | `new HashSet()` | Creates a new HashSet with default initial capacity 16 and load factor 0.75.
`hset =` | `new HashSet(initialCapacity)` | Creates a new HashSet with the specified initial int capacity.
`hset =` | `new HashSet(initialCapacity, loadFactor)` | Creates a new HashSet with the specified capacity which will not exceed a specified (float) load factor.
`hset =` | `new HashSet(coll)` | Creates a new HashSet with elements from the Collection coll

## SortedSet interface methods

The SortedSet interface is used by TreeSet and adds additional methods to reflect that a TreeSet is sorted.

    SortedSet sset;

Result | Method | Description
--- | --- | ---
`comp =` | `sset.comparator()` | Returns Comparator used to compare elements. null if natural ordering used (eg, String).
`obj =` | `sset.firstKey()` | First element (in sorted order).
`obj =` | `sset.lastKey()` | Last element (in sorted order).
`sset =` | `sset.headMap(obj)` | Returns SortedSet of all elements less than obj.
`sset =` | `sset.tailMap(obj)` | Returns SortedSet of all elements greater than or equal to obj.
`sset =` | `sset.subMap(from, to)` | Returns SortedSet of all elements greater than or equal to from and less than to.

## TreeSet class constructors

TreeSet implements the Set and SortedSet interface methods. TreeSet is implemented with an underlying TreeMap (balanced binary tree). If the element type has a natural order (eg, String) elements will be ordered by that, but often you will supply a Comparator object that tells how two elements compare. It has the following constructors.

Result | Constructor | Description
--- | --- | ---
`tset =` | `new TreeSet()` | Creates new TreeSet. Elements sorted by natural order.
`tset =` | `new TreeSet(comp)` | Creates new TreeSet using Comparator comp to sort elements.
`tset =` | `new TreeSet(coll)` | Creates new TreeSet from Collection coll using natural ordering.
`tset =` | `new TreeSet(sset)` | Creates new TreeSet from SortedSet smp using element ordering from sset.