There are many programming problems that can be solved using slight variations of the same piece of code or the same data structure. As a somewhat contrived example, suppose we are given an array of strings and want to return either the string at a particular index or a default value if the index is out
of range. This can be implemented as follows:
public static String getOrDefault(
String[] array, int index, String dflt){
return index >= 0 && index < array.length
? array[index] : dflt;
}
Except for the two occurrences of the type String, nothing about this algorithm is specific to strings.
Generics are the language feature provided by Java that makes it possible to write code that works with a wide range of types. In contrast to interfaces, which ostensibly serve a similar purpose, generics do not require the types to be part of a
certain type hierarchy. Here is getOrDefault() rewritten using generics:
public static <T> T getOrDefault(
T[] array, int index, T dflt) {
return index >= 0 && index < array.length
? array[index] : dflt;
}
The main difference is the declaration of a generic type before the method definition and the replacement of String with T. This new, generic version of getOrDefault() now works with arrays
of any type.
Really any type? Unfortunately, not quite: Generics in Java only work with types that are derived from Object, but not with primitive types such as int, float, or
char. For example, if you try to call getOrDefault() with an array of ints
getOrDefault(new int[]{1, 2, 3}, -1, 999);
the compiler will complain that the function cannot be applied to the given types. We can sometimes work around this limitation by using wrapper types such as Integer, Float, or Character, as in the following example:
getOrDefault(new Integer[]{1, 2, 3}, -1, 999);
If this isn’t feasible or too inefficient, it can be necessary to supplement generic methods that operate on types derived from Object with one or more specialized methods that handle primitive types. This
technique is widely used in Java’s standard library, for example to provide specialized algorithms in the Arrays class.
Collections
Methods aren’t the only thing that can be generalized using generics. In fact, most Java programmers first encounter generics when they try to use one of the many collection classes provided by the standard library.
A collection is a data type that manages multiple objects and provides methods for accessing and changing them. Java’s standard library comes with a wide selection of generic collection classes that are parametrized by the types they hold. Perhaps the most widely used example
is ArrayList, which is a resizable array of the given type T. Another example is HashMap, which takes two type arguments and provides a mapping from values of type T to values of
type U. The following example uses these types to create an array of Integers and a mapping from Strings to Integers:
var firstPrimes = new ArrayList<Integer>();
firstPrimes.add(2);
firstPrimes.add(3);
firstPrimes.add(5);
firstPrimes.add(7);
var releaseYear = new HashMap<String, Integer>();
releaseYear.put("Star Trek: The Motion Picture", 1979);
releaseYear.put("Star Trek II: The Wrath of Khan", 1982);
// ...
The Java compiler uses the type arguments to ensure that only compatible values are stored in the respective container. For example, when trying to add a String to firstPrimes, Java complains about “incompatible types” because only integers are
permitted. There are many collections beside ArrayList and HashMap; the most important ones are listed in Table B.2.
Table B.2
Commonly used collection classes
.
Class
Interfaces
Description
ArrayList
List
variable-length array
LinkedList
List, Deque
doubly-linked list
ArrayDeque
Deque
double-ended queue
HashSet
Set
set based on hash tables
TreeSet
NavigableSet
ordered set based on trees
PriorityQueue
Queue
priority queue
HashMap
Map
a key-value map based on hash tables
TreeMap
NavigableMap
a key-value map based on trees
Underlying all these collection classes is a hierarchy of generic interfaces such as Iterable, Collection, List, Map, and Set that define the capabilities offered by different kinds of data structures. All collection classes provided by the standard library implement at least one of these interfaces, but some implement more. For instance, LinkedList implements both List and Deque because it can be used as a linear list and as a double-ended queue.
These interfaces are also commonly used in place of concrete collection classes when declaring variables and method signatures. If we wanted to write a method that converts a sequence of strings to upper-case, we could declare it as
static ArrayList<String> makeUppercase(ArrayList<String> strings) {
var result = new ArrayList<String>();
for (String s : strings)
result.add(s.toUpperCase());
return result;
}
But by changing the type of strings to Iterable and the return type to List, we obtain a function that is more flexible and easier to modify:
static List<String> makeUppercase(Iterable<String> strings) {
// as above
}
This function definition is more flexible because it accepts many different collection types and not just ArrayLists. Its implementation is also easier to modify because we can change the type of collection allocated inside the method without having to adjust the
return type. Using interfaces instead of concrete classes as return and argument types is sometimes referred to as “programming to interfaces, not implementations.”
Iterators and Iterables
Java defines two related interfaces for iterating over data structures: Iterator and Iterable. The Iterator interface is used to iterate over the elements of any data
structure that contains elements of a certain type E. It is defined as follows:
interface Iterator<E> {
boolean hasNext();
E next();
void remove();
}
The three methods are defined to work as follows:
•next() returns the next element and advances the iterator.
•hasNext() determines whether there are any elements remaining, that is, whether the next call to next() succeeds.
•remove() removes the previous element returned by next() from the data structure. The remove() method is optional and can be omitted.
The Iterable interface consists of a single method that creates a new iterator:
public interface Iterable<E> {
Iterator<E> iterator();
// ...
}
Usually, Iterable is implemented by classes that contain multiple other objects, and the Iterator returned by the iterator() method can then be used to access these objects sequentially.
Iterables can be used with for statements of the form
for (E value : collection) {
// ...
}
where collection is some object that implements Iterable. This loop is equivalent to the following code:
Iterator<E> it = collection.iterator();
while (it.hasNext()) {
E value = it.next();
// ...
}
The iterator() method is first used to create a new Iterator, which is then used to access every element of collection.
All collection classes in Java’s standard library, including ArrayList, HashSet, and HashMap, implement the Iterable interface.
The Iterator returned by each of these classes then handles the practical details of iterating over the elements of the particular data structure.