THE Java™ Programming Language, Fourth Edition

public SortedSet<E>headSet(E max)

Returns a view of the set that contains all the elements of this set whose

values are less than the value of max. This view is backed by the collection

as with subSet. The exceptions thrown by this method or the returned set

are the same as those of subSet.

public SortedSet<E>tailSet(E min)

Similar to headSet, but the returned set contains all the elements of this set

whose values are greater than or equal to the value of min.

The notion of being backed by a collection is important in many methods. The sets returned by the subsetting
methods are not snapshots of the matching contents. Rather, they are views onto the underlying collection that
filter out certain elements, returning an empty collection if all elements are filtered out. Because the subsets
are backed by the original collection, the views remain current no matter which set you usethe subset or the
original set. You can create snapshots by making copies of the view, as in

public SortedSet copyHead(SortedSet set, T max) {
SortedSet head = set.headSet(max);
return new TreeSet(head); // contents from head
}

This utilizes the copy constructor provided by most of the concrete collection implementations to create a new
collection whose initial members are the same as the collection passed to the constructor.

The java.util package gives you two general-purpose Set implementationsHashSet and
LinkedHashSetand one SortedSet implementation, TReeSet.

21.5.1. HashSet

HashSet is a Set implemented with a hashtable. Modifying the contents of a HashSet or testing
for containment are 0(1) constant-time operations[3]that is, they do not get larger as the size of the set
increases (assuming that the hashCode methods of the contents are well written to distribute the hash codes
widely across the full range of int values). HashSet has four constructors:

[3] The notation 0(f) is used in computer science to mean that the order of time for the

execution of an algorithm increases in the manner of f. In this notation, n is traditionally the

magnitude of the data under consideration. An algorithm that is 0(logn) takes longer as a

function of the log of nthe number of elementsmultiplied by some constant C. Generally

speaking, the constant is irrelevant when algorithms are compared because as n gets large, the

difference between an algorithm that is 0(logn) compared to one that is, say, 0(n^2 ) is governed

by n, not the constantwhen n is 1000, for example, logn is 6.9, whereas n^2 is 1,000,000. The

multiplying constant for the 0(logn) algorithm would have to be extremely large to make it

worse than the 0(n^2 ) algorithm. Of course, when two 0(logn) algorithms are compared, the

constant does matter, so in such a case it would be written. A similar argument means that for

algorithms whose overhead has multiple terms, such as 0(C^2 +n), the smaller term is not

relevant and so would be typically described as 0(n). An algorithm that is not sensitive to the

size of n is written as 0(1) or sometimes 0(C). You will see "big O" notation in this chapter

because it is an effective way of comparing different collection implementations.

publicHashSet(int initialCapacity, float loadFactor)