Java Reference
In-Depth Information
public <T> SortedSet<T> copyHead(SortedSet<T> set, T max) {
SortedSet<T> head = set.headSet(max);
return new TreeSet<T>(head); // contents from head
}
This utilizes the copy constructor provided by most of the concrete col-
lection implementations to create a new collection whose initial mem-
bers are the same as the collection passed to the constructor.
The
java.util
package gives you two general-purpose
Set
implement-
ations
HashSet
and
LinkedHashSet
and
one
SortedSet
implementation,
TReeSet
.
21.5.1.
HashSet
HashSet<E>
is a
Set<E>
implemented with a hashtable. Modifying the con-
tents of a
HashSet
or testing for containment are
0
(1) constant-time op-
(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
(log
n
) takes longer as a function of the log of
n
the num-
ber 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
(lo
gn
)
compared to one that is, say,
0
(
n
2
) is governed by
n,
not the constantwhen
n
is 1000, for example,
lo
gn
is 6.9, whereas
n
2
is 1,000,000. The multiplying constant for the
0
(lo
gn
) algorithm would have to
be extremely large to make it worse than the
0
(n
2
) algorithm. Of course, when two
0
(lo
gn
) 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.
public
HashSet(int initialCapacity, float loadFactor)
