generics : Java Glossary

Introduction

All the Java Collection classes, e.g. HashMap, ArrayList, TreeList can contain only generic Objects. The problem with this is you must keep track manually what sorts of object are really in each Collection. The compiler won’t warn you if you add a Cat to a Collection of Dogs.

Without genericity, in Java, you must, at run time, cast objects on the way into a Collection to make sure they are the right type and cast them back again on the way out before you can use their methods. It is totally up to you as application programmer to enforce your rules about what sort of objects you want in each Collection. You can’t simply declare that a Collection will contain only Dog objects and have attempts put anything else in flagged at compile time.

Java version 1.5 or later has generics implemented with high overhead, requiring implicit casts both on the way into the collection and on the way out. The compiler automatically casts all objects going into your collection to Dog and will automatically cast them back to Dog on the way out. Inside the collection, they are treated as generic Objects.

In theory, neither of these two time consuming casts are necessary. However, removing them would create a vulnerability in the JVM (Java Virtual Machine) that could be exploited maliciously. The saving grace of the design in that Sun did not need to change the JVM or class file structure to implement it.

You can try out the Java version 1.5 or later compiler with generics.

Learning Strategy

• Get yourself a nice tall hot/cold drink with caffeine and/or guarana. You will need maximal alertness for making sense of generics.
• Don’t expect to understand everything in one reading. You must alternately read, practice, read, practice. More and more of what you read will gradually make sense as you try to push generics further in your examples. Happily, you can do 90% of what you need with just basic skills.
• Read the introductory and simple tutorials and explanations first. If you feel over your head, try reading something else and come back to that one later.
• Try writing some simple code, say adding a few Strings to a generified ArrayList for practice. Use the ComparatorCutter to write you a generified Comparator.
• Examine your code with a disassembler or decompiler to see what the generified code looks like at run time. Nearly all of what happens in generics happens at compile time.
• Consider buying some textbooks. The authors of those books tend to be more patient with the novice than those of the official documentation who are primarily language lawyers concerned with completeness and corner cases.
• Generics are not nearly as powerful as they first look from their complexity. Don’t be surprised if there is no way at all to do what would seem to be obvious operations. They are severely hobbled because they are purely a compile time feature.
  1. Type erasure: All information about generics is washed away by the compiler so at runtime, it is as if no generics were used. They are as invisible at runtime as preprocessor macros.
  2. All generics can really do is add some extra cross-checks on how you use combinations of classes, taking into consideration only information that can be gleaned from types known at compile time. This is still powerful feature. It ensures casts can’t fail and prevents many common coding bugs.

Why The New Syntax?

Further, types passed to a static method define the types of the parameters in the call, something quite different from passing a class as a parameter, which could only have an effect once the call had been made, e.g.

The Ugly

• The syntax for generics is butt ugly. Here is a class that has two replaceable types D and C. D must implement both Comparable and Serializable. & is used where you would expect to use comma. extends is used where you would expect to use implements. < > is used where you would expect to use ( ). I can hardly believe Sun chose such disgusting inconsistent syntax. But that’s what we are stuck with.
• To avoid creating new keywords, generics recycles extends, super and & with meanings quite unrelated to the original meanings.
• Generics are fundamentally incompatible with arrays. You cannot allocate a generically typed array 

  // You MAY NOT write code like this:
  
  HashMap<String,Integer>[] hs = new HashMap<String,Integer>[1000];

  This is nuts since all the Collection classes fundamentally depend on internally typed arrays. Astoundingly, you can’t write code that involves arrays and generics without generating (or suppressing) unchecked conversion warnings. Even Oracle’s Collection code generates warnings! The design of generics is so jerry-rigged, so inept that generics can’t even handle the very specific purpose they were designed for, namely Collection type safety!!! The excuse Sun gives is this goofiness is necessary because of type erasure — that all generic type information is checked then discarded at compile time. The excuse they give for type erasure was they wanted to make code with generics usable by older Java object code that knew nothing of genericity. You can’t actually do this, so the benefit was never realised.
• To understand why type erasure forced this monstrous kludge, read up on ArrayStoreException. Even without generics, Java cannot tell purely at compile time when inserting a given Object into an array is legal. Since the type erasure means there is no generic information around at run time, Java cannot enforce generic type safety when Objects are stored in arrays.

  Type erasure implies many peculiar restrictions:

  • For a type parameter T, you can’t write a class literal T.class.
  • You can’t use instanceof to test if an object is of type T.
  • You can’t create an array of T.
  • You can’t write class literals for generic types like List <String>. class
  • You can’t test if an object is an instanceof List < String>
  • You can’t create an array of List<String>.
  I think the real reason they did it was political. They did not want to force the licenced vendors to make major changes to their JVMs. To kludge around the problem, look at how Sun implemented ArrayList.
• Again because of type erasure, Java cannot enforce generic type information in casts at run time. Happily casts are rarely required when working with generics.

How To Use Generics

You

javac.exe -source 1.5 -target 1.5 *.java

to turn on generics. Otherwise they will be treated as syntax errors.

To create an ArrayList that can only hold Dog Objects. If you attempt to put anything else in there, (except subclasses like Dalmatians), you will find out at compile time. This is a great improvement on the old days when you sometimes found out about your errors when you partly exercised the code at run time.

// this is NOT legal
java.util.Vector<Dog> dogs = new java.util.Vector<Dalmatian>();

Comparator/Comparable

Iterator

Generics and Static Methods

Generics and Static Factories

// naive and unsuccessful attempt to create a new object of generic type T
T thing = new T();

// What that code compiles to at run time:
Object thing = new Object();

Static Inference

// How the sort method is defined in Collections.sort
// Quite a bit more complex that using it, eh?
public static
  <T extends Comparable<? super T>>
  void sort( List<T> list )

You would expect to invoke it then with:

// Short form of sort invocation
// relying on compiler static type inference
Collections.sort( listOfDogs );

So when is Java smart enough to figure out the types on its own via inferring? It sometimes feels as if it depends on the phases of the moon. Inferring has even the cleverest programmers scratching their heads. Nobody can figure out for certain why sometimes the compiler can infer the generic types and sometimes it cannot. So what can you do?

If you have Eclipse, you can rapidly experiment, removing the explicit types one by one and putting them back if Eclipse complains. If you don’t have Eclipse, you can do the same thing more slowly with a compile cycle.

The problem with removing type tags is if you remove one too many tags, you are flying without a net. You have effectively turned off type checking. It is difficult to tell the difference between allowing inference to check types and turning off type checking altogether. This is a serious flaw in the design of Java generics.

Generic type tags are useful documentation to let others know what your code is up to. That is an argument for leaving them in.

If you burn the generic types into your code in 100 places, it will be hard to modify later if you change that type. Ideally you should specify the type of a variable in only one place — where it is declared. That is an argument for removing the type tags wherever you can.

Generics and Serialized Objects

Code like this will cause problems:

// generates type mismatch error
ArrayList<Thing> things = ois.readObject();

You can try to fix it with a cast like this:

// generates cast warning
ArrayList<Thing>things = (ArrayList<Thing>)ois.readObject();

but that generates a warning message. The problem is type erasure. The generic type is not stored with the serialized object. Java could check that the Object read back was an ArrayList, but not that it was an ArrayList< Thing>. Since it can’t guarantee, it gives the warning. The problem is the lame type erasure way generics were implemented. Had the type information been included, Java could check and the cast would be valid. So what do you do? You can just live with the warning, suppress it with an annotation like this:

// suppress unchecked warning
@SuppressWarnings( "unchecked" )
void restore()
   {
   // Java cannot check that the object is actually an ArrayList<Thing>.
   // It will just trust that it is.
   ArrayList<Thing> things = (ArrayList<Thing>) ois.readObject();
   ...
   }

or you can copy the fields one by one like this:

If your ArrayList is already allocated and final, you can do it this way:

// copy with a temporary array, generates no warning
final ArrayList<Thing> things = new ArrayList<Thing>( INITIAL_SIZE );
...
final ArrayList<Object> temp = (ArrayList<Object>)ois.readObject();
things.clear();
for ( Object item : temp )
   {
   things.add( (Thing)item );
   }

It is much simpler to read and write serialized arrays than ArrayLists. They don’t have this problem since you are not relying on generics for your type information. For arrays, the Java type system embeds the actual type in the ObjectStream. The problem is you may not be able to switch your ObjectStream ArrayLists to simple arrays when your clients have many files in the old serialized ArrayList format. Arrays are also slightly more compact.

Syntactic Soup: <?> vs <Dog> vs <? extends Dog> vs <E extends Dog> vs <? super T>

ArrayList<Dog> is a collection permitted to contain Dogs or any subclass of Dog. An ArrayList< Dog> that incidentally contained only Dalmatians is a quite different beast from an ArrayList< Dalmatian> which can’t contain anything but Dalmatians (or their subclasses).

Collection<Object> is a heterogenous Collection, while Collection<?> is a homogenous Collection of elements of the same unknown type, e.g. Dog and its subclasses.

Consider the wildcard form of a type specification:

• Collection<Dog> potentially contains both Dog and Dalmatian objects. Collection<Dog> matches both types of specifier.
• Collection<Dalmatian>, on the other paw, may not contain any Dog objects, other than Dalmatians. Collection< Dalmatian> matches the wildcard [Collection <? extends T >] but not the simple form [ Collection < T >].

The wildcard form restricts our ability to put raw Dog objects into the Collection, but on the other hand it lets us deal with Collection< Dalmatian>, where we could not otherwise.

You will need to read Oracle’s tutorial many times. It is as subtle as a Buddhist sutra. It makes me wonder if generics were a big mistake, introducing something so very difficult to solve a simple problem. Angelika Langer’s Generics FAQ is somewhat more accessible. Just keep reading and experimenting and more and more of what you read will make sense little by little. Unfortunately, I find the understanding does not stick and you have to keep going back to the well to have it continue to make sense.

Here is a complex example. If you understand this, you will be well on your way to understanding the fine points:

public static
<D extends Dog & Comparable<? super D>>
D selectSuitableDog( Collection<? extends D> );

This static method above is designed to be used with class D that has the following properties:

• It must either be a Dog or a subclass of Dog
• D must implement Comparable on two Dog objects, or on two superclass of Dog objects such as Object. A Comparable for two Dalmatians will not do.

You must pass a Collection to the method where the Collection contains Dog objects (where the Dog objects may be subclasses of Dog), or a more limited Collection of some subclass of Dog objects, e.g. a Collection< Dalmatian> of pure Dalmatian objects. Note that a Collection< Dog> where all elements happen to be Dalmatian is quite a different animal from a Collection< Dalmatian>where all elements are coerced to be Dalmatians (or subsets of Dalmatian).

Compared with the gobbledegook to define the method, your call to the method is very simple:

Lower and Upper Bounds

It helps to understand generics by thinking in terms of containers — most generified types are containers/Collections in some form or other.

Generified

public class Container<T> {}

Upper Bounds

Sometimes, though, we don’t want to let people include any old object. To do this, we declare an

public class Container<T extends Number> {}

If you think of a class hierarchy with the basic root classes at the top and the subclasses dangling down from it, then the upper bound is the name of the root uppermost class of a branch that is valid for T.

Now only Numeric types can be stored in the container. Also, since we know that any given value of T has to be a subclass of Number, we can safely reference objects in the container as Numbers instead of Objects.

Lower Bounds

Again, if you think of a class hierarchy with the basic root classes at the top and the subclasses dangling down from it, then the lower bound is the name of the lowermost class in a chain of superclasses that is valid for T. The bound includes the class mentioned, not just its super classes.

static <T> void sort( List<T> list, Comparator<? super T> c )

The above example says that for example, you could sort a List< Dalmatian> with either a Comparator< >Dalamatian> or a Comparator< Dog>.

To use generics, you merely have to replace the appropriate type parameter with your class. So a Container for Integers is declared as Container< Integer> (again primitive types are not valid here; this is due to implementation necessities.

Happily Java version 1.5 or later autoboxes primitive types in method calls allowing you to simulate containers of primitives.

Subclassing

Wildcard Types

Conversely, since we don’t know what type a Container< ?> holds, we can’t store stuff inside the container.

Otherwise we might accidentally store an Object in the Container of a type that does not belong.

However, since we know that all Containers must store Objects, we can treat whatever is in the Container as an Object. In effect, the wildcard turns the Container into a read-only object: you can’t write into Container< ?>, but you can read from it. This is internally enforced by the special subtyping rules of generic objects; the exact mechanisms require some mathematical theory that I will not delve in here.

Similarly to how we limited the storage type of a container with the extends Number relationship, we can limit the type of a wildcard. A type Container<? extends Number>' indicates that the object stores something that is at least of type Number. Once again, that means that instead of viewing it as containing something that is at least an Object, we can see it as containing something that is at least a Number.

Keep in mind the difference between a <Number> container that just incidentally contains only Integer objects and an <Integer> container that is restricted by generic type constraints to only Integer objects.

Recursive Types

public class Foo<T extends Foo<T>> {}

You will see recursive types used in the definition of the Enum class that underlies enums.

However, be careful not to think of the generic parameter declaration as any kind of operation.

public class Foo<T extends Foo<T>> {}

You generally subclass or implement such

public class Bar extends Foo<Bar> {}

The primary purpose of a recursive type is to allow the creation of generic interfaces whose methods require the use of the implementing class as parameters.

The other main use of lower bounds is in recursive types. Specifying

<T extends A<T>>

<T extends A<? super T>>

Generifying Methods

public static <T> T move( Container<T> from, Container<? super T> to);

Mixing Generics and Arrays

This material comes compliments of Lew, a frequent contributor to comp.lang.java.programmer. The comments in green are mine.

Generics and arrays do not mix well. That’s because arrays remember their underlying type at runtime, but generics just become plain Objects at runtime through the process of type erasure†.

The compiler will not let you create an array of generic types, unless the generic parameter comprises entirely unadorned wildcard (?) characters. So

// legal
Foo<?> [] bunchaFoos = new Foo<?> [NUMFOOS];

is legal, but

// illegal
 Foo<Bar> [] bunchaFoos = new Foo<Bar> [NUMFOOS];

is not. Other things like casting and reflection get really difficult, too.

For almost everything you want to do mixing arrays and generics you can use ArrayList instead of an array. The syntax is a little more verbose, and the code is somewhat slower, but the type safety and expressiveness compensate.

† In technical terms, an array is a reifiable type — in that it can be made real in the JVM. Consequently its base type must also be reifiable. A generic type, except for the pure wildcard ? generics, is not reifiable because of erasure. So the compiler won’t let you make an array of a generic type.

If you look at Oracle’s code for ArrayList and other generic-supporting classes, you might be surprised to find code that generates unchecked warnings (generics violated). There is no legitimate way to allocate arrays of generics. So what we do is sweep this unclean code under the rug and let ArrayList do the dirty deed for us. At least our code is clean.

The popular wisdom is you can’t have an array of HashMaps. Actually, you can, it is just it is not kosher generics.

// HashMap kludge. This will compile.
HashMap<Long,String> hashMaps = new HashMap[ 1000 ];

// you may not write
HashMap<Long,String> hashMaps = new HashMap<>[ 1000 ];

// or
HashMap<Long,String> hashMaps = new HashMap<Long,String>[ 1000 ];

Mark Vedder made a stab at explaining why: In Java, arrays are covariant but generics are not. Array covariance has been present since Java version 1.0. When generics were added in Java version 1.5, they were made invariant since generics were implemented to ensure type safety at compile time. Given that arrays are covariant, that is possible that not all slots of the array will contain identical types as long as the type put into the slot inherits from the type the array represents. For example, putting a String and a Date in an Object[] array, or a String and a StringBuilder in a CharSequence[] array. If the type put into the array is not in the type hierarchy of the array, for example putting a Date into a String[] array, an ArrayStoreException is thrown.

This is a Runtime exception. So the issue is not caught until Runtime. With generics, it would be caught at compile time.

What are you supposed to do instead of using an array of HashMaps?

Use a List<Set<YourType>> backed by an ArrayList of HashMaps.

I think he meant Map not Set.

I have read these explanations many times and I still don’t get it. It is not so much how it works, but why syntax whose meaning seems clear to humans does not work. Why is it broken? Was it really impossible to do properly? I suspect some of these strange properties of generics came from going for a simple implementation (avoiding any run time implementation), rather than a logical one. Or it may have happened because generics were tacked on later to Java’s arrays. Arrays are not considered Collections, even though they share many characteristics.

Under the Hood

Converting Sets

Let us say you had a Set of Dalmatians each of which implemented the Dog interface and your method wanted a Set of Dogs, not a Set of Dalmatians. What do you do?

Tips

• My usual tactic to solve difficult generics problems is to scan the code in src.zip for Oracle’s source code similar to what I am trying to do, then puzzle why the Sun code works, then copy the technique. Sometimes you discover there is no solution that does not generate a warning message.
• You almost never want to return a type with a wildcard, e.g. Set<? extends Dog>. Just give the user a single type, Set<Dog>. It will do what you wanted much better than the wildcard version.

Books

Book referral for Learning Java, fourth edition

	recommend book⇒Learning Java, fourth edition
	by	Patrick Niemeyer and Jonathan Knudson	978-1-4493-1924-3	paperback
	publisher	O’Reilly	978-1-4493-7249-1	eBook
	published	2013-06-25	B00DDZPC9I	kindle
Covers Java 1.7 though nearly all of it is about older features, including enums and generics. Covers serialisation vs code generation. Particularly good at explaining the use of the Java 1.2 Collection classes. Teaches with example code, my favourite technique. It has a tiger on the cover because Oracle’s code name for Java 1.5 was Tiger. Contains a very good chapter on generics. The book is not for people new to programming. This is the book Mark Space recommends, especially to learn OO programming.
Online bookstores carrying Learning Java, fourth edition abe books anz abe books.ca abe books.de amazon.ca amazon.de Chapters Indigo amazon.es Chapters Indigo eBooks iberlibro.com abe books.com abe books.fr amazon.com amazon.fr Barnes & Noble abe books.it Nook at Barnes & Noble amazon.it Kobo junglee.com Google play abe books.co.uk O’Reilly Safari amazon.co.uk Powells other stores
Greyed out stores probably do not have the item in stock. Try looking for it with a bookfinder.

Book referral for Effective Java: second edition

	recommend book⇒Effective Java: second edition
	by	Joshua J. Bloch	978-0-321-35668-0	paperback
	birth	1961-08-28 age:56	978-0-13-715002-1	WebBook
	publisher	Prentice Hall	B000WJOUPA	kindle
	published	2008-05-28
No design patterns, just generic advice on good Java programming style. This is considered the best explanation of generics, even though it has just one chapter on generics. People claim it all came clear after reading his explanation. It is also consider the best explanation of serialization. Not to be confused with his earlier Effective Java Programming Language Guide. book website
Online bookstores carrying Effective Java: second edition abe books anz abe books.ca abe books.de amazon.ca amazon.de Chapters Indigo amazon.es Chapters Indigo eBooks iberlibro.com abe books.com abe books.fr amazon.com amazon.fr Barnes & Noble abe books.it Nook at Barnes & Noble amazon.it Kobo junglee.com Google play abe books.co.uk O’Reilly Safari amazon.co.uk Powells other stores
Greyed out stores probably do not have the item in stock. Try looking for it with a bookfinder.

Book referral for Java Generics and Collections

	recommend book⇒Java Generics and Collections
	by	Maurice Naftalin & Philip Wadler	978-0-596-52775-4	paperback
	publisher	O’Reilly	978-0-596-55150-6	eBook
	published	2006-10-18	B0026OR2HM	kindle
Covers both generics and Collections. Covers Java 1.5+ features such as autoboxing, for:each as well. Recommended by Mike Schilling.
Online bookstores carrying Java Generics and Collections abe books anz abe books.ca abe books.de amazon.ca amazon.de Chapters Indigo amazon.es Chapters Indigo eBooks iberlibro.com abe books.com abe books.fr amazon.com amazon.fr Barnes & Noble abe books.it Nook at Barnes & Noble amazon.it Kobo junglee.com Google play abe books.co.uk O’Reilly Safari amazon.co.uk Powells other stores
Greyed out stores probably do not have the item in stock. Try looking for it with a bookfinder.

Book referral for Just Java 2, sixth edition

	recommend book⇒Just Java 2, sixth edition
	by	Peter van der Linden	978-0-13-148211-1	paperback
	publisher	Prentice Hall	978-0-13-700990-9	eBook
	published	2004-07-01	978-0-13-493982-7	audio
			B001MDC0FW	kindle
Covers Java 5 aka 1.5. Peter has a sense of humour and breaks the drudgery of reading with a funny story at the end of each chapter. He explains through simple examples. This is a book you can sit down and read and not fall asleep. I helped edit and proofread the chapters on enums and genericity. This is good introduction that won’t overwhelm you.
Online bookstores carrying Just Java 2, sixth edition abe books anz abe books.ca abe books.de amazon.ca amazon.de Chapters Indigo amazon.es Chapters Indigo eBooks iberlibro.com abe books.com abe books.fr amazon.com amazon.fr Barnes & Noble abe books.it Nook at Barnes & Noble amazon.it Kobo junglee.com Google play abe books.co.uk O’Reilly Safari amazon.co.uk Powells other stores
Greyed out stores probably do not have the item in stock. Try looking for it with a bookfinder.

Learning More