Maurice Naftalin Maurice - Java Generics and Collections

[] acquire add addAll addAllAbsent addFirst addIfAbsent addLast addObserver allOf append asLifoQueue asList [] binarySearch blocking [] ceiling ceilingEntry checkedCollection checkedList checkedMap checkedSet checkedSortedMap checkedSortedSet class clear clone close comparator comparator compare compareTo compiler flag complementOf concurrent contains containsAll containsKey containsValue copy copyOf covariant []delay timedequeueing descendingIterator descendingKeySet descendingMap descendingSet disjoint drainTo [] element emptyList emptyMap emptySet endenqueuing entrySet equals []FIFO, see First In First Out fill final first firstEntry firstKey floor floorEntry frequency front []genericreflection get getClass getComponentType getDelay getFirst getLast getListeners []hashtable hasNext hasPrevious headMap headSet higher higherEntry [] indexOf indexOfSubList insertionintervals isEmpty iterator []Java [] keySet [] last lastEntry lastIndexOf lastIndexOfSubList lastKey legacy listIterator locking lower lowerEntry lteration [] max min [] name navigableKeySet nCopies newInstance newSetFromMap next nextIndex noneOf nonreifiable notifyObservers [] of offer offerFirst offerLast ordinal []parameterized peek peekFirst peekLast poll pollFirst pollFirstEntry pollLast pollLastEntry pop previous previousIndex pull push put putAll putIfAbsent [] [] range read recursive remainingCapacity remove removeAll removeEldestEntry removeFirst removeFirstOccurrence removeLast removeLastOccurrence replace replaceAll retainAll reverse reverseOrder rotate runtime []segment locking Semaphore set setChanged setValue shuffle singleton singletonList singletonMap size sort sorted lists subList subMap subSet subString swap synchronizedCollection synchronizedList synchronizedMap synchronizedSet synchronizedSortedMap synchronizedSortedSet [] [] tailMap tailSet take toArray toGenericString toString tryAcquire type violations [] unlock unmodifiableCollection unmodifiableList unmodifiableMap unmodifiableSet unmodifiableSortedMap unmodifiableSortedSet update [] valueOf values values values valuesvariable [] []

About the Authors

Maurice Naftalin is Technical Director at Morningside Light Ltd., a software consultancy in the United Kingdom. He has most recently served as an architect and mentor at NSB Retail Systems plc, and as the leader of the client development team of a major U.K. government social service system. He has taught Java since 1998 at both basic and advanced levels for Learning Tree and Sun Educational Services.

Philip Wadler is professor of theoretical computer science at the University of Edinburgh, Scotland, where his research focuses on functional and logic programming. He co-authored the Generic Java standard that became the basis for generics in Sun's Java 5.0, and he also contributed to the XQuery language standard base. He received his Ph.D. in computer science from Carnegie-Mellon University and co-wrote Introduction to Functional Programming (Prentice-Hall).

An interface or class may be declared to take one or more type parameters, which are written in angle brackets and should be supplied when you declare a variable belonging to the interface or class or when you create a new instance of a class.

We saw one example in the previous section. Here is another:

List words = new ArrayList();words.add("Hello ");words.add("world!");String s = words.get(0)+words.get(1);assert s.equals("Hello world!");

In the Collections Framework, class ArrayList implements interface List . This trivial code fragment declares the variable words to contain a list of strings, creates an instance of an ArrayList , adds two strings to the list, and gets them out again.

In Java before generics, the same code would be written as follows:

List words = new ArrayList();words.add("Hello ");words.add("world!");String s = ( (String) words.get(0))+( (String) words.get(1))assert s.equals("Hello world!");

Without generics, the type parameters are omitted, but you must explicitly cast whenever an element is extracted from the list.

In fact, the bytecode compiled from the two sources above will be identical. We say that generics are implemented by erasure because the types List , List , and List> are all represented at run-time by the same type, List . We also use erasure to describe the process that converts the first program to the second. The term erasure is a slight misnomer, since the process erases type parameters but adds casts.

Generics implicitly perform the same cast that is explicitly performed without generics. If such casts could fail, it might be hard to debug code written with generics. This is why it is reassuring that generics come with the following guarantee:

Cast-iron guarantee : the implicit casts added by the compilation of generics never fail.

There is also some fine print on this guaranteee: it applies only when no unchecked warnings have been issued by the compiler. Later, we will discuss at some length what causes unchecked warnings to be issued and how to minimize their effect.

Implementing generics by erasure has a number of important effects. It keeps things simple, in that generics do not add anything fundamentally new. It keeps things small, in that there is exactly one implementation of List , not one version for each type. And it eases evolution, since the same library can be accessed in both nongeneric and generic forms.

This last point is worth some elaboration. It means that you don't get nasty problems due to maintaining two versions of the libraries: a nongeneric legacy version that works with Java 1.4 or earlier, and a generic version that works with Java 5 and 6. At the bytecode level, code that doesn't use generics looks just like code that does. There is no need to switch to generics all at onceyou can evolve your code by updating just one package, class, or method at a time to start using generics. We even explain how you may declare generic types for legacy code. (Of course, the cast-iron guarantee mentioned above holds only if you add generic types that match the legacy code.)

Another consequence of implementing generics by erasure is that array types differ in key ways from parameterized types. Executing

new String[size]

allocates an array, and stores in that array an indication that its components are of type String . In contrast, executing:

new ArrayList()

allocates a list, but does not store in the list any indication of the type of its elements. In the jargon, we say that Java reifies array component types but does not reify list element types (or other generic types). Later, we will see how this design eases evolution (see ).

Generics Versus Templates Generics in Java resemble templates in C++. There are just two important things to bear in mind about the relationship between Java generics and C++ templates: syntax and semantics. The syntax is deliberately similar and the semantics are deliberately different.

Syntactically, angle brackets were chosen because they are familiar to C++ users, and because square brackets would be hard to parse. However, there is one difference in syntax. In C++, nested parameters require extra spaces, so you see things like this:

List< List >