Java Reference
In-Depth Information
Table 8-1. Set implementations
Class
Internal
representation
Since
Element
order
Member
restric-
tions
Basic
opera-
tions
Iteration
perfor-
mance
Notes
Hashtable
1.2
None
None
O(1)
O(capacity)
Best general-
purpose
implementation.
Hash
Set
Linked
hashtable
1.2
Insertion
order
None
O(1)
O(n)
Preserves
insertion order.
Linked
Hash
Set
Bit ields 5.0
Enum
declaration
Enum
values
O(1)
O(n)
Holds non-
null
enum values
only.
Enum
Set
Red-black tree
1.2
Sorted
ascending
Comparable
O(log(n))
O(n)
Tree
Set
Comparable
elements or
Com
parator
.
Array
5.0
Insertion
order
None
O(n)
O(n)
Threadsafe
without
synchronized
methods.
CopyOn
Wri
teAr
raySet
The
TreeSet
implementation uses a red-black tree data structure to maintain a set
that is iterated in ascending order according to the natural ordering of
Comparable
objects or according to an ordering specified by a
Comparator
object.
TreeSet
actually implements the
SortedSet
interface, which is a subinterface of
Set
.
The
SortedSet
interface offers several interesting methods that take advantage of its
sorted nature. The following code illustrates:
public
static
void
testSortedSet
(
String
[]
args
)
{
// Create a SortedSet
SortedSet
<
String
>
s
=
new
TreeSet
<>(
Arrays
.
asList
(
args
));
// Iterate set: elements are automatically sorted
for
(
String
word
:
s
)
{
System
.
out
.
println
(
word
);
}
s
a
// Special elements
String
first
=
s
.
first
();
// First element
String
last
=
s
.
last
();
// Last element
// all elements but first
