The Java Collections Framework is designed to support numerous collections in a hierarchical fashion. It is essentially made up of interfaces, implementations, and algorithms.
Collections are objects that group multiple elements and store, retrieve, and manipulate those elements. The Collection
interface is at the root of the collection hierarchy. Subinterfaces of Collection
include List, Queue
, and Set
. Table 15-1 shows these interfaces and whether they are ordered or allow duplicates. The Map
interface is also included in the table, as it is part of the framework.
Interface | Ordered | Dupes | Notes |
---|---|---|---|
|
Yes |
Yes |
Positional access; element insertion control |
|
Can be |
No (Keys) |
Unique keys; one value mapping max per key |
|
Yes |
Yes |
Holds elements; usually FIFO |
|
Can be |
No |
Uniqueness matters |
Table 15-2 lists commonly used collection type implementations, their interfaces, and whether or not they are ordered, sorted, and/or contain duplicates.
Implementations | Interface | Ordered | Sorted | Dupes | Notes |
---|---|---|---|---|---|
|
|
Index |
No |
Yes |
Fast resizable array |
|
|
Index |
No |
Yes |
Doubly linked list |
|
|
Index |
No |
Yes |
Legacy, synchronized |
|
|
No |
No |
No |
Key/value pairs |
|
|
No |
No |
No |
Legacy, synchronized |
|
|
Insertion, last access |
No |
No |
Linked list/hash table |
|
|
Balanced |
Yes |
No |
Red-black tree map |
|
|
Priority |
Yes |
Yes |
Heap implementation |
|
|
No |
No |
No |
Fast access set |
|
|
Insertion |
No |
No |
Linked list/hash set |
|
|
Sorted |
Yes |
No |
Red-black tree set |
The subinterfaces of the Collection
interface provide several valuable method signatures, as shown in Table 15-3.
Method | List params | Set params | Map params | Returns |
---|---|---|---|---|
|
index, element |
element |
n/a |
|
|
Object |
Object |
n/a |
|
|
n/a |
n/a |
key |
|
|
n/a |
n/a |
value |
|
|
index |
n/a |
key |
|
|
Object |
n/a |
n/a |
|
|
none |
none |
n/a |
|
|
n/a |
n/a |
none |
|
|
n/a |
n/a |
key, value |
|
|
index or Object |
Object |
key |
|
|
none |
none |
none |
|
Collection.stream()
returns a sequential Stream
with the context collection as its source. Collection.parallelStream()
returns a parallel Stream
with the context collection as its source.
The Collections
class, not to be confused with the Collection
interface, contains several valuable static methods (e.g., algorithms). These methods can be invoked on a variety of collection types. Table 15-4 shows commonly used Collection
class methods, their acceptable parameters, and return values.
Method | Parameters | Returns |
---|---|---|
|
Collection <? super T>, T… |
|
|
Collection, [Comparator] |
|
|
Collection, [Comparator] |
|
|
Collection, Collection |
|
|
Collection, Object |
|
|
Deque |
|
|
List |
|
|
List |
|
|
List destination, List source |
|
|
List, int distance |
|
|
List, int position, int position |
|
|
List, Object |
|
|
List, Object |
|
|
List, Object, [Comparator] |
|
|
List, Object oldValue, Object newValue |
|
|
Map |
|
See Chapter 16 for more information on typed parameters (e.g., <T>
).
Algorithms and data structures are optimized for different reasons—some for random element access or insertion/deletion, others for keeping things in order. Depending on your needs, you may have to switch algorithms and structures.
Common collection algorithms, their types, and average time efficiencies are shown in Table 15-5.
Algorithms | Concrete type | Time |
---|---|---|
|
|
0 (1) |
|
|
0 (n) |
|
|
0 (n) |
|
|
0 (1) |
|
|
0 (1) |
|
|
0 (1) |
|
|
0 (1) |
|
|
0 (n) |
|
|
0 (n) |
|
|
0 (1) |
|
|
0 (log n) |
|
|
0 (log n) |
|
|
0 (log n) |
The Big O notation is used to indicate time efficiencies, where n is the number of elements (see Table 15-6).
Notation | Description |
---|---|
0 (1) |
Time is constant, regardless of the number of elements. |
0 (n) |
Time is linear to the number of elements. |
0 (log n) |
Time is logarithmic to the number of elements. |
0 (n log n) |
Time is linearithmic to the number of elements. |
Several methods in the Collections
class assume that the objects in the collection are comparable. If there is no natural ordering, a helper class can implement the Comparator
functional interface to specify how the objects are to be ordered. The code example here orders surnames by their generated metaphone codes:
Take a look at the Metaphone Code Calculator written with Java for a better understanding of metaphone codes.
import
org.apache.commons.codec.language.Metaphone
;
public
class
MetaphoneCode
{
private
String
metaphoneCode
;
public
MetaphoneCode
(
String
surname
)
{
Metaphone
m
=
new
Metaphone
();
metaphoneCode
=
m
.
metaphone
(
surname
)
+
"("
+
surname
+
")"
;
}
public
String
getMetaphoneCode
()
{
return
metaphoneCode
;
}
public
void
setMetaphoneCode
(
String
metaphoneCode
)
{
this
.
metaphoneCode
=
metaphoneCode
;
}
public
String
toString
()
{
return
this
.
metaphoneCode
;
}
}
import
java.util.Comparator
;
public
class
SurnameSort
implements
Comparator
<
MetaphoneCode
>
{
@Override
public
int
compare
(
MetaphoneCode
mc1
,
MetaphoneCode
mc2
)
{
return
mc1
.
getMetaphoneCode
().
compareTo
(
mc2
.
getMetaphoneCode
());
}
}
import
java.util.ArrayList
;
import
java.util.Collections
;
public
class
SurnameApp
{
public
static
void
main
(
String
[]
args
)
{
MetaphoneCode
m1
=
new
MetaphoneCode
(
"Whitede"
);
MetaphoneCode
m2
=
new
MetaphoneCode
(
"Whitehead"
);
MetaphoneCode
m3
=
new
MetaphoneCode
(
"Whitted"
);
MetaphoneCode
m4
=
new
MetaphoneCode
(
"Whitshead"
);
MetaphoneCode
m5
=
new
MetaphoneCode
(
"White"
);
ArrayList
<
MetaphoneCode
>
mlist
=
new
ArrayList
<>();
mList
.
add
(
m1
);
mList
.
add
(
m2
);
mList
.
add
(
m3
);
mList
.
add
(
m4
);
mList
.
add
(
m5
);
System
.
out
.
println
(
"Unsorted: "
+
mList
);
SurnameSort
cSort
=
new
SurnameSort
();
Collections
.
sort
(
mList
,
cSort
);
System
.
out
.
println
(
"Sorted: "
+
mList
);
}
}
$
Unsorted:
[
WTT
(
Whitede
),
WTHT
(
Whitehead
),
WTT
(
Whitted
),
WTXT
(
Whitshead
),
WT
(
White
)]
$
Sorted:
[
WT
(
White
),
WTHT
(
Whitehead
),
WTT
(
Whitede
),
WTT
(
Whitted
),
WTXT
(
Whitshead
)]
The SurnameSort
class implemented the Comparator
interface that was used by the cSort
instance. Optionally, an anonymous inner class could have been created to avoid the work of creating the seperate SurnameSort
class:
// Replace: SurnameSort cSort = new SurnameSort();
Comparator
<
MetaphoneCode
>
cSort
=
new
Comparator
<
MetaphoneCode
>()
{
public
int
compare
(
MetaphoneCode
mc1
,
MetaphoneCode
mc2
)
{
return
mc1
.
getMetaphoneCode
().
compareTo
(
mc2
.
getMetaphoneCode
());
}
};
Since Comparator
is a functional interface, a lambda expression could have been used to make the code more readable:
Comparator
<
MetaphoneCode
>
cSort
=
(
MetaphoneCode
mc1
,
MetaphoneCode
mc2
)
->
mc1
.
getMetaphoneCode
().
compareTo
(
mc2
.
getMetaphoneCode
());
Class names do not need to be explicitly stated in the argument list, as the lambda expressions have knowledge of the target types. That is, notice (mc1, mc2)
versus (MetaphoneCode mc1, MetaphoneCode mc2)
:
// Example 1
Comparator
<
MetaphoneCode
>
cSort
=
(
mc1
,
mc2
)
->
mc1
.
getMetaphoneCode
().
compareTo
(
mc2
.
getMetaphoneCode
());
Collections
.
sort
(
mList
,
cSort
);
// Example 2
Collections
.
sort
(
mList
,
(
mc1
,
mc2
)
->
mc1
.
getMetaphoneCode
().
compareTo
(
mc2
.
getMetaphoneCode
()));
JDK 9 introduces new convenience factory methods that create compact unmodifiable collection (e.g., List, Set, Map) instances. Therefore, multiple lines of code can be refactored into one:
// Pre Java 9 immutable list instantiation
List
<
String
>
haplogroups
=
new
ArrayList
<>();
haplogroups
.
add
(
"I2"
);
haplogroups
.
add
(
"I2B"
);
haplogroups
.
add
(
"IJ"
);
haplogroups
=
Collections
.
unmodifiableList
(
haplogroups
);
// Refactored Java 9 immutable list instantiation
List
<
String
>
haplogroups
=
List
.
of
(
"I2"
,
"I2B"
,
"IJ"
);