Sets

A Set is a Collection that contains unique elements (i.e., no duplicate elements). The collections framework contains several Set implementations, including HashSet and TreeSet. HashSet stores its elements in a hash table, and TReeSet stores its elements in a tree. The concept of hash tables is presented in Section 19.10. Figure 19.18 uses a HashSet to remove duplicate strings from a List. Recall that both List and Collection are generic types, so line 18 creates a List that contains String objects, and line 24 passes a Collection of Strings to method printNonDuplicates.

Figure 19.18. HashSet used to remove duplicate values from array of strings.

(This item is displayed on page 940 in the print version)

 1 // Fig. 19.18: SetTest.java
 2 // Using a HashSet to remove duplicates.
 3 import java.util.List;
 4 import java.util.Arrays;
 5 import java.util.HashSet;
 6 import java.util.Set;
 7 import java.util.Collection;
 8
 9 public class SetTest
10 {
11 private static final String colors[] = { "red", "white", "blue",
12 "green", "gray", "orange", "tan", "white", "cyan",
13 "peach", "gray", "orange" };
14
15 // create and output ArrayList
16 public SetTest()
17 {
18 List< String > list = Arrays.asList( colors );
19 System.out.printf( "ArrayList: %s
", list );
20 printNonDuplicates( list );
21 } // end SetTest constructor
22
23 // create set from array to eliminate duplicates
24 private void printNonDuplicates( Collection< String > collection )
25 {
26 // create a HashSet 
27 Set< String > set = new HashSet< String >( collection );
28
29 System.out.println( "
Nonduplicates are: " );
30
31 for ( String s : set )
32 System.out.printf( "%s ", s );
33
34 System.out.println();
35 } // end method printNonDuplicates
36
37 public static void main( String args[] )
38 {
39 new SetTest();
40 } // end main
41 } // end class SetTest

 

ArrayList: [red, white, blue, green, gray, orange, tan, white, cyan, peach,
gray, orange]

Nonduplicates are:
red cyan white tan gray green orange blue peach

 

Method printNonDuplicates (lines 2435), which is called from the constructor, takes a Collection argument. Line 27 constructs a HashSet from the Collection argument. Note that both Set and HashSet are generic types. By definition, Sets do not contain any duplicates, so when the HashSet is constructed, it removes any duplicates in the Collection. Lines 3132 output elements in the Set.

Sorted Sets

The collections framework also includes interface SortedSet (which extends Set) for sets that maintain their elements in sorted ordereither the elements' natural order (e.g., numbers are in ascending order) or an order specified by a Comparator. Class treeSet implements SortedSet. The program in Fig. 19.19 places strings into a treeSet. The strings are sorted as they are added to the treeSet. This example also demonstrates range-view methods, which enable a program to view a portion of a collection.

Figure 19.19. Using SortedSets and treeSets.

(This item is displayed on pages 941 - 942 in the print version)

 1 // Fig. 19.19: SortedSetTest.java
 2 // Using TreeSet and SortedSet.
 3 import java.util.Arrays;
 4 import java.util.SortedSet;
 5 import java.util.TreeSet;
 6
 7 public class SortedSetTest
 8 {
 9 private static final String names[] = { "yellow", "green",
10 "black", "tan", "grey", "white", "orange", "red", "green" };
11
12 // create a sorted set with TreeSet, then manipulate it
13 public SortedSetTest()
14 {
15 // create TreeSet 
16 SortedSet< String > tree = 
17  new TreeSet< String >( Arrays.asList( names ) );
18
19 System.out.println( "sorted set: " );
20 printSet( tree ); // output contents of tree
21
22 // get headSet based on "orange"
23 System.out.print( "
headSet ("orange"): " );
24 printSet( tree.headSet( "orange" ) );
25
26 // get tailSet based upon "orange"
27 System.out.print( "tailSet ("orange"): " );
28 printSet( tree.tailSet( "orange" ) );
29
30 // get first and last elements
31 System.out.printf( "first: %s
", tree.first() );
32 System.out.printf( "last : %s
", tree.last() );
33 } // end SortedSetTest constructor
34
35 // output set
36 private void printSet( SortedSet< String > set )
37 {
38 for ( String s : set )
39 System.out.printf( "%s ", s );
40
41 System.out.println();
42 } // end method printSet
43
44 public static void main( String args[] )
45 {
46 new SortedSetTest();
47 } // end main
48 } // end class SortedSetTest

 

sorted set:
black green grey orange red tan white yellow

headSet ("orange"): black green grey
tailSet ("orange"): orange red tan white yellow
first: black
last : yellow

 

Lines 1617 of the constructor create a TReeSet of String that contains the elements of array names and assigns the SortedSet to the reference tree. Both SortedSet and TReeSet are generic types. Line 20 outputs the initial set of strings using method printSet (lines 3642), which we discuss momentarily. Line 24 calls treeSet method headSet to get a subset of the TReeSet in which every element is less than "orange". The view returned from headSet is then output with printSet. If any changes are made to the subset, they will also be made to the original treeSet because the subset returned by headSet is a view of the TReeSet.

Line 28 calls treeSet method tailSet to get a subset in which each element is greater than or equal to "orange". The view returned by tailSet is then output. Any changes made through the tailSet view are made to the original treeSet. Lines 3132 call SortedSet methods first and last to get the smallest and largest elements of the set, respectively.

Method printSet (lines 3642) accepts a SortedSet as an argument and prints it. Lines 3839 print each element of the SortedSet using the enhanced for statement.