The Java TM Tutorial

| Start of Tutorial > Start of Trail > Start of Lesson | Search

Trail: Collections
Lesson: Interfaces

## The Set Interface

> A `Set` is a `Collection` that cannot contain duplicate elements. `Set` models the mathematical set abstraction. The `Set` interface extends `Collection` and contains no methods other than those inherited from `Collection`. It adds the restriction that duplicate elements are prohibited. `Set` also adds a stronger contract on the behavior of the `equals` and `hashCode` operations, allowing `Set` objects with different implementation types to be compared meaningfully. Two `Set` objects are equal if they contain the same elements.

> The `Set` interface is shown below:

> >     public interface Set {
> >         // Basic Operations
> >         int size();
> >         boolean isEmpty();
> >         boolean contains(Object element);
> >         boolean add(Object element);    // Optional
> >         boolean remove(Object element); // Optional
> >         Iterator iterator();

> >         // Bulk Operations
> >         boolean containsAll(Collection c);
> >         boolean addAll(Collection c);    // Optional
> >         boolean removeAll(Collection c); // Optional
> >         boolean retainAll(Collection c); // Optional
> >         void clear();                    // Optional

> >         // Array Operations
> >         Object[] toArray();
> >         Object[] toArray(Object a[]);
> >     }

> The JDK contains two general-purpose `Set` implementations. `HashSet`, which stores its elements in a hash table, is the best-performing implementation. `TreeSet`, which stores its elements in a red-black tree, guarantees the order of iteration. For more information on implementations, see the Implementations lesson.

> Here's a simple but useful `Set` idiom. Suppose you have a `Collection`, `c`, and you want to create another `Collection` containing the same elements, but with all duplicates eliminated. The following one-liner does the trick:

> >     Collection noDups = new HashSet(c);

> It works by creating a `Set` (which, by definition, cannot contain duplicates) initially containing all the elements in `c`. It uses the "standard `Collection` constructor" described in the `Collection` interface lesson.

### Basic Operations

> The `size` operation returns the number of elements in the `Set` (its cardinality). The `isEmpty` method does exactly what you think it does. The `add` method adds the specified element to the `Set` if it's not already present, and returns a boolean indicating whether the element was added. Similarly, the `remove` method removes the specified element from the `Set` if it's present, and returns a boolean indicating whether the element was present. The `iterator` method returns an `Iterator` over the `Set`.

> Here's a little program that takes the words in its argument list and prints out any duplicate words, the number of distinct words, and a list of the words with duplicates eliminated:

> >     import java.util.*;

> >     public class FindDups {
> >         public static void main(String args[]) {
> >             Set s = new HashSet();
> >             for (int i=0; i<args.length; i++)
> >                 if (!s.add(args[i]))
> >                     System.out.println("Duplicate detected: "+args[i]);

> >             System.out.println(s.size()+" distinct words detected: "+s);
> >         }
> >     }

> Now let's run the program:

> >     % java FindDups i came i saw i left

> >     Duplicate detected: i
> >     Duplicate detected: i
> >     4 distinct words detected: [came, left, saw, i]

> Note that the example code always refers to the collection by its interface type (`Set`), rather than by its implementation type (`HashSet`). This is a strongly recommended programming practice, as it gives you the flexibility to change implementations merely by changing the constructor. If the variables used to store a collection, or the parameters used to pass it around, are declared to be of the collection's implementation type rather than its interface type, then all such variables and parameters must be changed to change the collection's implementation type. Furthermore, there's no guarantee that the resulting program will work; if the program uses any non-standard operations that are present in the original implementation type but not the new one, the program will fail. Referring to collections only by their interface keeps you honest, in the sense that it prevents you from using any non-standard operations.

> The implementation type of the `Set` in the example above is `HashSet`, which makes no guarantees as to the order of the elements in the `Set`. If you want the program to print the word list in alphabetical order, all you have to do is to change the set's implementation type from `HashSet` to `TreeSet`. Making this trivial one-line change causes the command line in the previous example to generate the following output:

> >     % java FindDups i came i saw i left

> >     Duplicate word detected: i
> >     Duplicate word detected: i
> >     4 distinct words detected: [came, i, left, saw]

### Bulk Operations

> The bulk operations are particularly well suited to `Sets`: they perform standard set-algebraic operations. Suppose `s1` and `s2` are `Sets`. Here's what the bulk operations do:
> - `s1.containsAll(s2)`: Returns `true` if `s2` is a subset of `s1`. (For example, set `s1` is a subset of `s2` if set `s2` contains all the elements in `s1`.)
> - `s1.addAll(s2)`: Transforms `s1` into the union of `s1` and `s2`. (The union of two sets is the set containing all the elements contained in either set.)
> - `s1.retainAll(s2)`: Transforms `s1` into the intersection of `s1` and `s2`. (The intersection of two sets is the set containing only the elements that are common in both sets.)
> - `s1.removeAll(s2)`: Transforms `s1` into the (asymmetric) set difference of `s1` and `s2`. (For example, the set difference of `s1` - `s2` is the set containing all the elements found in `s1` but not in `s2`.)
> To calculate the union, intersection, or set difference of two sets non-destructively (without modifying either set), the caller must copy one set before calling the appropriate bulk operation. The resulting idioms are shown below:

> >     Set union = new HashSet(s1);
> >     union.addAll(s2);

> >     Set intersection = new HashSet(s1);
> >     intersection.retainAll(s2);

> >     Set difference = new HashSet(s1);
> >     difference.removeAll(s2);

> The implementation type of the result `Set` in the above idioms is `HashSet`, which is, as mentioned above, the best all-around `Set` implementation in the JDK. However, any general-purpose `Set` implementation could be substituted.

> Let's revisit the `FindDups` example program above. Suppose you want to know which words in the argument list occur only once and which occur more than once, but you do not want any duplicates printed out repeatedly. This effect can be achieved by generating two sets, one containing every word in the argument list, and the other containing only the duplicates. The words that occur only once are the set difference of these two sets, which we know how to compute. Here's how the resulting program looks:

> >     import java.util.*;

> >     public class FindDups2 {
> >         public static void main(String args[]) {
> >             Set uniques = new HashSet();
> >             Set dups = new HashSet();

> >             for (int i=0; i<args.length; i++)
> >                 if (!uniques.add(args[i]))
> >                     dups.add(args[i]);

> >             uniques.removeAll(dups);  // Destructive set-difference

> >             System.out.println("Unique words:    " + uniques);
> >             System.out.println("Duplicate words: " + dups);
> >         }
> >     }

> Now let's run the revised program with the same same argument list we used before:

> >     % java FindDups2 i came i saw i left

> >     Unique words:    [came, left, saw]
> >     Duplicate words: [i]

> A less common set-algebraic operation is the symmetric set difference: the set of elements contained in either of two specified sets, but not contained in both of them. The following code calculates the symmetric set difference of two sets non-destructively:

> >     Set symmetricDiff = new HashSet(s1);
> >     symmetricDiff.addAll(s2);
> >     Set tmp = new HashSet(s1);
> >     tmp.retainAll(s2);
> >     symmetricDiff.removeAll(tmp);

### Array Operations

> The array operations don't do anything special for `Sets` beyond what they do for any other `Collection`. They are described in the `Collection` interface lesson.

| Start of Tutorial > Start of Trail | Search