Java Reference
In-Depth Information
In mathematics, a set rejects duplicates. If an object is already in the set, an attempt to
add it again is ignored. That's useful in many programming situations as well. For
example, if we keep a set of available printers, each printer should occur at most once
in the set. Thus, we will interpret the
add
and
remove
operations of sets just as we
do in mathematics: Adding an element has no effect if the element is already in the
set, and attempting to remove an element that isn't in the set is silently ignored.
Sets don't have duplicates. Adding a duplicate of an element that is already present
is silently ignored.
Of course, we could use a linked list to implement a set. But adding, removing, and
containment testing would be relatively slow, because they all have to do a linear
search through the list. (Adding requires a search through the list to make sure that we
don't add a duplicate.) As you will see later in this chapter, there are data structures
that can handle these operations much more quickly.
In fact, there are two different data structures for this purpose, called hash tables and
trees. The standard Java library provides set implementations based on both data
structures, called
HashSet
and
TreeSet
. Both of these data structures implement
the
Set
interface (see
Figure 2
).
The
HashSet
and
TreeSet
classes both implement the
Set
interface.
Figure 2
Set Classes and Interfaces in the Standard Library
701
