The collections api - Data Structures and Problem Solving Using Java - page 264

1 public static void main( String [] args )
2 {
3 Set<String> s = new TreeSet<String>( Collections.reverseOrder( ) );
4 s.add( "joe" );
5 s.add( "bob" );
6 s.add( "hal" );
7 printCollection( s ); // Figure 6.11
8

}

figure 6.31
An illustration of the TreeSet , using reverse order

In Section 5.6, we examined the static searching problem and saw that if
the items are presented to us in sorted order, then we can support the find
operation in logarithmic worst-case time. This is static searching because,
once we are presented with the items, we cannot add or remove items. The
SortedSet allows us to add and remove items.
We are hoping that the worst-case cost of the contains , add , and remove
operations is because that would match the bound obtained for the
static binary search. Unfortunately, for the simplest implementation of the
TreeSet , this is not the case. The average case is logarithmic, but the worst
case is and occurs quite frequently. However, by applying some algo-
rithmic tricks, we can obtain a more complex structure that does indeed have
cost per operation. The Collections API TreeSet is guaranteed to
have this performance, and in Chapter 19, we discuss how to obtain it using
the binary search tree and its variants, and provide an implementation of the
TreeSet , with an iterator.

O (log N )

O ( N )

O (log N )

We mention in closing that although we can find the smallest and largest
item in a SortedSet in time, finding the K th smallest item, where K
is a parameter, is not supported in the Collections API. However, it is possible
to perform this operation in time, while preserving the running
time of the other operations, if we do more work.

We can also use a
binary search tree
to access the K th
smallest item in
logarithmic time.

O (log N )

O (log N )

6.7.2 the HashSet class

In addition to the TreeSet , the Collections API provides a HashSet class that
implements the Set interface. The HashSet differs from the TreeSet in that it can-
not be used to enumerate items in sorted order, nor can it be used to obtain the
smallest or largest item. Indeed, the items in the HashSet do not have to be com-
parable in any way. This means that the HashSet is less powerful than the
TreeSet . If being able to enumerate the items in a Set in sorted order is not
important, then it is often preferable to use the HashSet because not having to
maintain sorted order allows the HashSet to obtain faster performance. To do so,
elements placed in the HashSet must provide hints to the HashSet algorithms.

The HashSet imple-
ments the Set
interface. It does
not require a
comparator.