One of the concrete classes that implements Collection is java.util.HashSet. We briefly visited HashSet at the beginning of this section on Collections, and now it is time to expand on it a little. This class is just a plain old “Data Structures 101” hash table.
You provide each object that will be stored as data in the hash table, and the library class does the work of maintaining the table and putting the elements in the right places. You start by instantiating an empty HashSet, then anything you add is placed in the table. If an object is already in the table, it won't be added again.
The class HashSet implements Set which implements Collection. The exact parent-child relationship of interfaces is shown in Figure 16-2.
The interface java.util.Set does not add any methods at all to the elementary data access methods specified in java.util.Collection. It is written as a separate interface to help document and represent the design of the Collections Framework. It shows the symmetry between classes that are Sets, and classes that are Lists. As a reminder, the Collection interface, and thus the Set interface, looks like this.
public interface java.util.Set<E> extends Collection<E> {
// basic operations
public int size();
public boolean isEmpty();
public boolean contains(Object element);
public boolean add(E element);
public boolean remove(Object element);
public Iterator iterator();
// bulk operations on an entire collection
public boolean addAll(Collection c);
public boolean removeAll(Collection c);
public boolean retainAll(Collection c);
public boolean containsAll(Collection c);
public void clear();
// put the collection into an array
public Object[] toArray();
public T[] toArray(T a[]);
// a reminder that you may need to override these
public boolean equals(Object o);
public int hashCode();
}
A Set is a collection that has no duplicate elements. The interface represents the mathematical concept of a set, as applied in set theory. It is easy to calculate the intersection of two collections, or take the set difference between this set and another. An example of a set is the set of all colors that a system can display on its monitor. Here is how we would calculate the intersection of two collections:
import java.util.*;
import java.awt.Color;
import static java.awt.Color.*;
public class d2 {
public static void main(String[] args) {
// populate first collection
Collection <Color> hs1 = new HashSet<Color>();
hs1.add( red );
hs1.add( green );
hs1.add( blue );
hs1.add( magenta );
// populate second collection
Collection<Color> hs2 = new HashSet<Color>();
hs2.add( red );
hs2.add( green );
hs2.add( yellow );
// intersect is the things that are in hs1 AND in hs2
Collection <Color> intersect = hs1;
boolean ok = intersect.retainAll(hs2);
System.out.println("intersect: " + intersect);
}
}
Running this code results in this output:
intersect: [java.awt.Color[r=0,g=255,b=0],
java.awt.Color[r=255,g=0,b=0]]
Java has a type Color in the GUI library. Colors are stored as bytes containing the level of RGB (red/green/blue) shading for a monitor. If you inspect the output, you'll confirm that indeed the intersection of the two collections is green, red. We should note that these methods (addAll(), retainAll(), and removeAll()) are promised by the Collection interface, so you can use them on any Collection data structure including linked lists, not just on sets! The Collection framework is very powerful, and will save you many hours of programming once you master it.
You would use a HashSet when you have a collection that is not going to have duplicates and you want fast retrieval.
The fourth and final concrete Collection class that we'll mention is the TreeSet class. This class is a set (i.e., collection of arbitrary elements), and it has the additional feature that the elements are kept in a way that makes it easy to fetch them in ascending order of elements.
TreeSet automatically sorts an element into its correct place in the collection whenever you add it! The sort order will either be the natural order for the class, as expressed by Comparable, or the order defined by a Comparator that you pass to the constructor. When you get an Iterator for a TreeSet, it is guaranteed to deliver the elements in this order.
A TreeSet collection is implemented by (“has a”) a TreeMap behind the scenes. TreeMap in turn uses a red/black tree as its data structure. If you haven't met red/black trees yet, they are a variety of binary tree that is always kept balanced.
TreeSet works just like HashSet, but it takes a little extra work to keep everything in sorted order. Therefore, you will choose TreeSet when the ordering of the elements is important to you, and HashSet otherwise. There's no sense in incurring a performance penalty if you don't need to.
TreeSet has a few additional methods of its own, relating to the fact that it keeps elements in order. The extra features it offers, over and above Collection, are:
public class TreeSet<E> extends AbstractSet<E>
implements SortedSet<E>, Cloneable, java.io.Serializable {
public TreeSet(); // constructors
public TreeSet(Comparator);
public TreeSet(Collection);
public TreeSet(SortedSet<E> s);
public SortedSet subSet(E from, E to);
public SortedSet headSet(E lessThan);
public SortedSet tailSet(E gte);
public Comparator comparator();
public E first();
public E last();
public Object clone();
}
The methods first() and last() obviously return you the lowest and highest element currently in the collection. The method headSet() returns a view of this Collection, containing only elements that are strictly less than the argument object. The method tailSet() returns a view of elements that are greater than or equal to the argument object. The method subSet() returns a view into the collection that holds only objects starting at the from object inclusive, and going up to but not including the to object.
The four constructors of TreeSet shown will instantiate, respectively, an empty TreeSet, an empty tree set that will use this comparator, a TreeSet containing the elements in this collection, and a TreeSet containing the elements in this SortedSet. SortedSet is an interface that is only implemented by one class in the JDK: TreeSet. It is there so you can use it if you extend the framework with your own classes and designs.