Last Modified 2019.2.1

Generic

Generic was introduced in Java 5 for more rigorous type checking and generic algorithm implementations at compile time. The following example defines a box where all types of references can be stored.

package net.java_school.examples;

public class Box<T> {
	private T t;

	public void set(T t) {
		this.t = t;
	}

	public T get() {
		return t;
	}
}

T is called a type parameter. T can be used anywhere in the class body. You must specify the type of T when creating the Box object.

Box<Integer> intBox = new Box<Integer>();//In <Integer>, Integer is called a type argument.

Because of Java 7 type inference, the above sentence can be reduced as follows.

Box<Integer> intBox = new Box<>();

Type Parameter Naming Conventions

  • E - Element (used extensively by the Java Collections Framework)
  • K - Key
  • N - Number
  • T - Type
  • V - Value
  • S,U,V etc. - 2nd, 3rd, 4th types

A raw type is the name of a generic class or interface without any type arguments.

Box<Integer> intBox = new Box<Integer>();
Box rawBox = new Box();//Box is the raw type of the generic type Box<T>

A non-generic class or interface type is not a raw type. Raw types show up in legacy code because lots of API classes (such as the Collections classes) were not generic prior to Java 5. When using raw types, you essentially get pre-generics behavior - a Box gives you Objects. For backward compatibility, assigning a parameterized type to its raw type is allowed:

Box<Integer> intBox = new Box<Integer>();
Box rawBox = intBox;//OK

Box rawBox = new Box();
Box<Integer> intBox = rawBox;//warning: unchecked conversions

But if you assign a raw type to a parameterized type, you get a warning:

Box<St;ring> strBox = new Box<>();
Box rawBox = strBox;
rawBox.set(8);//warning: unchecked invocation to set(T)

The warning shows that raw types bypass generic type checks, deferring the catch of unsafe code to runtime. Therefore, you should avoid using raw types.

Generic methods are methods that introduce their own type parameters. This is similar to declaring a generic type, but the type parameter's scope is limited to the method where it is declared. Static and non-static generic methods are allowed, as well as generic class constructors. The syntax for a generic method includes a list of type parameters, inside angle brackets, which appears before the method's return type.

package net.java_school.examples;

public interface Pair<K,V> {
	public K getKey();
	public V getValue();
}
package net.java_school.examples;

public class IdPasswdPair<K,V> implements Pair<K,V> {
	private K key;
	private V value;

	public IdPasswdPair(K key, V value) {
		this.key = key;
		this.value = value;
	}

	@Override
	public K getKey() {
		return key;
	}

	@Override
	public V getValue() {
		return value;
	}

}
package net.java_school.examples;

public class Util {

	//Generic Method
	public static <K,V> boolean compare(Pair<K,V> p1, Pair<K,V> p2) {
		return p1.getKey().equals(p2.getKey()) && p1.getValue().equals(p2.getValue());
	}

	public static void main(String[] args) {
		if (args.length == 2) {
			Pair<String, String> inputData = new IdPasswdPair<>(args[0], args[1]);
			Pair<String, String> storedData = new IdPasswdPair<>("xman31", "1987qwertY");
			boolean isSame = Util.compare(inputData, storedData);
			if (isSame) {
				System.out.println("Login succeeded.");
			} else {
				System.out.println("Login failed. Please check your ID and password.");
			}
		} else {
			System.out.println("How to run: java net.java_school.examples.Util 'ID' 'Password'");
		}
	}

}

The complete syntax for invoking the compare method would be:

boolean isSame = Util.<String, String>compare(inputData, storedData);

The type has been explicitly provided, as shown in bold. Generally, this can be left out and the compiler will infer the type that is needed:

boolean isSame = Util.compare(inputData, storedData);

This feature, known as type inference, allows you to invoke a generic method as an ordinary method, without specifying a type between angle brackets.

Bounded Type Parameters

A method that operates on numbers might only want to accept instances of Number or its subclasses. This is what bounded type parameters are for. To declare a bounded type parameter, list the type parameter's name, followed by the extends keyword, followed by its upper bound.

package net.java_school.examples;

public class Box<T extends Number> {
	private T t;

	public void set(T t) {
		this.t = t;
	}

	public T get() {
		return t;
	}
}

In the Box class declaration, <T extends Number> is called a type parameter section. Constraints can be interfaces like <T extends java.io.Serializable>. If the constraint is an interface, use the extends keyword. You can place one or more constraints in the Type Parameters section. A type parameter list can consist of one or more interfaces, or one class and one or more interfaces. If you have a mix of one class and an interface, you must first make the class appear in the type parameter list.

<T extends Aclass & Binterface & Cinterface>

Generic Methods and Bounded Type Parameters

package net.java_school.examples;

public class GenericMethodsWithBoundedTypeParametersTest {

	public static <T extends Number & Comparable<T>> int countGreaterThan(T[] array, T elem) {
		int count = 0;
		for (T e : array) {
			if (e.compareTo(elem) > 0) {
				++count;
			}
		}
		return count;
	}

	public static void main(String[] args) {
		Integer[] arr = {1,2,3,4,5,6,7,8,9,10};
		int count = countGreaterThan(arr,7);//The number of elements in the array arr whose values are greater than 7
		System.out.println(count);
	}

}
3

The Comparable<T> interface defines only one method.

package java.util;

public interface Comparable<T> {
	public int compareTo(T o);
}

The compareTo method of the Comparable<T> interface has a promised implementation. Assuming it runs like a.compareTo(b), the compareTo method should return a value like this:

if a == b, 0.
if a > b, 1.
if a < b, -1.

The Integer class inherits the Number class, and it also implements Comparable<Integer> Interface. Double, Long, Float, Short, and Byte inherit the Number class, and also implement the Comparable interface.

Generics, Inheritance, and Subtypes

Now consider the following method:

public void boxTest(Box<Number> n) { /* ... */ }

Are you allowed to pass in Box<Integer> or Box<Double>, as you might expect? The answer is "no", because Box<Integer> and Box<Double> are not subtypes of Box<Number>. This is a common misunderstanding when it comes to programming with generics, but it is an important concept to learn. Given two concrete types A and B (for example, Number and Integer), MyClass<A> has no relationship to MyClass<B>, regardless of whether or not A and B are related. The common parent of MyClass<A> and MyClass<B> is Object.
Generics Subtype Relationship

Using the Collections classes as an example, ArrayList<E> implements List<E>, and List<E> extends Collection<E>. So ArrayList<String> is a subtype of List<String>, which is a subtype of Collection<String>. So long as you do not vary the type argument, the subtyping relationship is preserved between the types.

Type Inference

Type inference is a Java compiler's ability to look at each method invocation and corresponding declaration to determine the type argument (or arguments) that make the invocation applicable. The inference algorithm determines the types of the arguments and, if available, the type that the result is being assigned, or returned. Finally, the inference algorithm tries to find the most specific type that works with all of the arguments. To illustrate this last point, in the following example, inference determines that the second argument being passed to the pick method is of type Serializable:

static <T> pick(T a1, T a2) { return a2; }
Serializable s = pick("d", new ArrayList<String>());

Type inference enables you to invoke a generic method as you would an ordinary method, without specifying a type between angle brackets.

public static <U> void addBox(U u, List<Box<U>> boxes) {...}
BoxDemo.addBox(Integer.valueOf(10), listOfIntegerBoxes);

The generic method addBox defines one type parameter named U. Generally, a Java compiler can infer the type parameters of a generic method call. Consequently, in most cases, you do not have to specify them. For example, to invoke the generic method addBox, you can specify the type parameter with a type witness as follows:

BoxDemo.<Integer>addBox(Integer.valueOf(10), listOfIntegerBoxes);

You can replace the type arguments required to invoke the constructor of a generic class with an empty set of type parameters (<>) as long as the compiler can infer the type arguments from the context. This pair of angle brackets is informally called the diamond. For example, consider the following variable declaration:

Map<String, List<String>> myMap = new HashMap<String, List<String>>();

You can substitute the parameterized type of the constructor with an empty set of type parameters (<>):

Map<String, List<String>> myMap = new HashMap<>();

Note that constructors can be generic (in other words, declare their own formal type parameters) in both generic and non-generic classes. Consider the following example:

class MyClass<X> {
	<T> MyClass(T t) {
		//...
	}
}

Consider the following instantiation of the class MyClass:

MyClass<Integer> myObject = new MyClass<>("");

In this example, the compiler infers the type Integer for the formal type parameter, X, of the generic class MyClass<X>. It infers the type String for the formal type parameter, T, of the constructor of this generic class.

MyClass<Integer> myObject = new MyClass<Integer>("");

The Java compiler takes advantage of target typing to infer the type parameters of a generic method invocation. The target type of an expression is the data type that the Java compiler expects depending on where the expression appears.

Target Types
Integer i = Integer.parseInt("10");
This statement is expecting an instance of Integer; this data type is the target type.

Consider the method Collections.emptyList, which is declared as follows:

static <T> List<T> emptyList();

Consider the following assignment statement:

List<String> listOne = Collections.emptyList();

This statement is expecting an instance of List<String>; this data type is the target type. Because the method emptyList returns a value of type List<T>, the compiler infers that the type argument T must be the value String. This works in both Java SE 7 and 8. Alternatively, you could use a type witness and specify the value of T as follows:

List<String> listOne = Collections.<String>emptyList();

However, this is not necessary in this context. It was necessary in other contexts, though. Consider the following method:

void processStringList(List<String> stringList) {
	//process
}

Suppose you want to invoke the method processStringList with an empty list. In Java SE 7, the following statement does not compile:

processStringList(Collections.emptyList());

The Java SE 7 compiler generates an error message similar to the following:
List<Object> cannot be converted to List<String>
The compiler requires a value for the type argument T so it starts with the value Object. Consequently, the invocation of Collections.emptyList returns a value of type List<Object>, which is incompatible with the method processStringList. Thus, in Java 7, you must specify the value of the type argument as follows:

processStringList(Collections.<String>emptyList());

This is no longer necessary in Java 8. The notion of what is a target type has been expanded to include method arguments, such as the argument to the method processStringList. In this case, processStringList requires an argument of type List<String>. The method Collections.emptyList returns a value of List<T>, so using the target type of List<String>, the compiler infers that the type argument T has a value of String. Thus, in Java SE 8, the following statement compiles:

processStringList(Collections.emptyList());

Wildcards

In generic code, the question mark (?), called the wildcard, represents an unknown type. The wildcard is never used as a type argument for a generic method invocation, a generic class instance creation.

Upper Bounded Wildcards

To write the method that works on lists of Number and the subtypes of Number, such as Integer, Double, and Float, you would specify List<? extends Number>. The term List<Number> is more restrictive than List<? extends Number> because the former matches a list of type Number only, whereas the latter matches a list of type Number or any of its subclasses.

package net.java_school.examples;

import java.util.Arrays;
import java.util.List;

public class WildCardTest {

	public static double sumOfList(List<? extends Number> list) {
		double s = 0.0;
		for (Number n : list) {
			s += n.doubleValue();
		}
		return s;
	}

	public static void main(String[] args) {
		List<Integer> li = Arrays.asList(1,2,3);
		System.out.println("sum = " + sumOfList(li));
	}

}
sum = 6.0
Arrays.asList
The Arrays.asList method converts the specified array and returns a fixed-size list. Note the fixed-size. The following causes a runtime error.
List<Integer> list = Arrays.asList(1,2,3);
list.add(4);//Runtime error

Unbounded Wildcards

A wildcard, such as List<?>, is called Unbounded Wildcards.
You can consider using Unbounded Wildcards in the following cases:

  • If you are writing a method that can be implemented using functionality provided in the Object class.
  • When the code is using methods in the generic class that don't depend on the type parameter. For example, List.size or List.clear. In fact, Class<?> is so often used because most of the methods in Class<T> do not depend on T.

Consider the following method, printList:

package net.java_school.examples;

import java.util.Arrays;
import java.util.List;

public class PrintListTest {
	
	public static void printList(List<Object> list) {
		for (Object elem : list) {
			System.out.print(elem + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		List<Integer> li = Arrays.asList(1,2,3);
		List<String> ls = Arrays.asList("one","two","three");
		printList(li);//compile-time error
		printList(ls);//compile-time error
	}

}

The following compilation error occurs in printList(li); and printList(ls);.
The method printList(List<Object>) is not applicable for the arguments (List<Integer>)
The method printList(List<Object>) is not applicable for the arguments (List<String>)

The goal of printList is to print a list of any type, but it fails to achieve that goal — it prints only a list of Object instances; it cannot print List<Integer>, List<String>, List<Double>, and so on, because they are not subtypes of List<Object>. To write a generic printList method, use List<?>. Because for any concrete type A, List<A> is a subtype of List<?>, you can use printList to print a list of any type:

package net.java_school.examples;

import java.util.Arrays;
import java.util.List;

public class PrintListTest {
	public static void printList(List<?> list) {
		for (Object elem : list) {
			System.out.print(elem + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		List<Integer> li = Arrays.asList(1,2,3);
		List<String> ls = Arrays.asList("one","two","three");
		printList(li);
		printList(ls);
	}

}
1 2 3
one two three

Lower Bounded Wildcards

A lower bounded wildcard is expressed using the wildcard character ('?'), following by the super keyword, followed by its lower bound: <? super A>.

To write the method that works on lists of Integer and the supertypes of Integer, such as Integer, Number, and Object, you would specify List<? super Integer>.

public static void addNumbers(List<? super Integer> list) {
	for (int i = 1; i <= 10;i++) {
		list.add(i);
	}
}

Wildcards and Subtyping

generics-listParent
Although Integer is a subtype of Number, List<Integer> is not a subtype of List<Number> and, in fact, these two types are not related. The common parent of List<Number> and List<Integer> is List<?>. The following diagram shows the relationships between several List classes declared with both upper and lower bounded wildcards.
Generics Wildcard Subtyping

Type Erasure

To implement generics, the Java compiler applies type erasure to:

  • Replace all type parameters in generic types with their bounds or Object if the type parameters are unbounded. The produced bytecode, therefore, contains only ordinary classes, interfaces, and methods.
  • Insert type casts if necessary to preserve type safety.
  • Generate bridge methods to preserve polymorphism in extended generic types.

Consider the following generic class that represents a node in a singly linked list:

package net.java_school.examples;

public class Node<T> {

	private T data;
	private Node<T> next;

	public Node(T data, Node<T> next) {
		this.data = data;
		this.next = next;
	}

	public T getData() {
		return data;
	}
	
}

Because the type parameter T is unbounded, the Java compiler replaces it with Object:

package net.java_school.examples;

public class Node {

	private Object data;
	private Node next;

	public Node(Object data, Node next) {
		this.data = data;
		this.next = next;
	}

	public Object getData() {
		return data;
	}
	
}

In the following example, the generic Node class uses a bounded type parameter:

package net.java_school.examples;

public class Node<T extends Comparable<T>> {

	private T data;
	private Node<T> next;

	public Node(T data, Node<T> next) {
		this.data = data;
		this.next = next;
	}

	public T getData() {
		return data;
	}
	
}

The Java compiler replaces the bounded type parameter T with the first bound class, Comparable:

package net.java_school.examples;

public class Node {

	private Comparable data;
	private Node next;

	public Node(Comparable data, Node next) {
		this.data = data;
		this.next = next;
	}

	public Comparable getData() {
		return data;
	}
	
}

The Java compiler also erases type parameters in generic method arguments. Consider the following generic method:

public static <T> int count(T[] anArray, T elem) {
	int cnt = 0;
	for (T e : anArray) {
		if (e.equals(elem)) {
			++cnt;
		}
	}
	return cnt;
}

Because T is unbounded, the Java compiler replaces it with Object:

public static int count(Object[] anArray, Object elem) {
	int cnt = 0;
	for (Object e : anArray) {
		if (e.equals(elem)) {
			++cnt;
		}
	}
	return cnt;
}

Suppose the following classes are defined:

class Shape { /* ... */ }
class Circle extends Shape { /* ... */ }
class Rectangle extends Shape { /* ... */ }

You can write a generic method to draw different shapes:

public static <T extends Shape> void draw(T shape) { /* ... */ }

The Java compiler replaces T with Shape:

public static void draw(Shape shape) { /* ... */ }

Effects of Type Erasure and Bridge Methods

Sometimes type erasure causes a situation that you may not have anticipated.
The following example shows how this can occur.

package net.java_school.examples;

public class Box<T> {

	private T t;

	public void set(T t) {
		this.t = t;
	}

	public T get() {
		return t;
	}
	
}
package net.java_school.examples;

public class IntBox extends Box<Integer> {

	@Override
	public void set(Integer t) {
		super.set(t);
	}

	@Override
	public Integer get() {
		return super.get();
	}

}
package net.java_school.examples;

public class BridgeTest {

	public static void main(String[] args) {
		IntBox ibox = new IntBox();
		Box box = ibox;
		box.set("Hello World!");//runtime error!
	}
	
}

box.set("Hello World!") throws Runtime exception as follows:

Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer
	at net.java_school.examples.IntBox.set(IntBox.java:1)
	at net.java_school.examples.BridgeTest.main(BridgeTest.java:8)

ClassCastException: The message "java.lang.String can not be cast to java.lang.Integer" is due to the bridge method created by the compiler. Box and IntBox are changed through the type erase process as follows.

package net.java_school.examples;

public class Box {

	public Object t;

	public Object set(Object t) {
		this.t = t;
	}

	public void get(Object t) {
		return t;
	}

}
package net.java_school.examples;

public class IntBox extends Box {

	@Override
	public void set(Integer t) {
		super.set(t);
	}
	
	//Bridge method generated by the compiler
	public void set(Object t) {
		setData((Integer) t);
	}
	
	@Override
	public Integer get(Integer t) {
		return super.get();
	}

}

After type erasure, the method signatures do not match. The Box method becomes set(Object) and the IntBox method becomes set(Integer). Therefore, the IntBox set(Integer) method does not override the Box set(Object) method. To solve this problem and preserve the polymorphism of generic types after type erasure, a Java compiler generates a bridge method to ensure that subtyping works as expected. For the IntBox class, the compiler generates the bridge method for set(Integer).

Non-Reifiable Types

A reifiable type is a type whose type information is fully available at runtime. This includes primitives, non-generic types, raw types, and invocations of unbound wildcards.

Non-reifiable types are types where information has been removed at compile-time by type erasure — invocations of generic types that are not defined as unbounded wildcards. A non-reifiable type does not have all of its information available at runtime. Examples of non-reifiable types are List<String> and List<Number> the JVM cannot tell the difference between these types at runtime.

Heap Pollution

Heap pollution occurs when a variable of a parameterized type refers to an object that is not of that parameterized type. This situation occurs if the program performed some operation that gives rise to an unchecked warning at compile-time. An unchecked warning is generated if, either at compile-time (within the limits of the compile-time type checking rules) or at runtime, the correctness of an operation involving a parameterized type (for example, a cast or method call) cannot be verified. For example, heap pollution occurs when mixing raw types and parameterized types, or when performing unchecked casts.

In normal situations, when all code is compiled at the same time, the compiler issues an unchecked warning to draw your attention to potential heap pollution. If you compile sections of your code separately, it is difficult to detect the potential risk of heap pollution. If you ensure that your code compiles without warnings, then no heap pollution can occur.

Potential Vulnerabilities of Varargs Methods with Non-Reifiable Formal Parameters

Generic methods that include vararg input parameters can cause heap pollution.

Varargs is a feature introduced in Java 5. It allows a method take an arbitrary number of values as arguments.

package net.java_school.examples;

public class VarargsTest {

	public static void sum(int ... a) {
		int sum = 0;
		for (int i : a) {
			sum += i;
		}
		ystem.out.println(sum);
	}
	
	public static void main(String[] args) {
		sum();
		sum(1);
		sum(1,2,3);
		sum(1,2,3,4);
	}

}
0
1
6
10
public static void faultyMethod(List<String>... l) {
	List[] listArr = l;
	//..
}

When compiled, the following warning is produced by the definition of the faultyMethod method:
warning: [varargs] Possible heap pollution from parameterized vararg type l
why?

When the compiler encounters a varargs method, it translates the varargs formal parameter into an array. However, the Java programming language does not permit the creation of arrays of parameterized types. The variable l has the type List[]. The following statement assigns the varargs formal parameter l to the List array listArr:
List[] listArr = l;
This statement can potentially introduce heap pollution.

Restrictions on Generics

To use Java generics effectively, you must consider the following restrictions:

  1. Cannot Instantiate Generic Types with Primitive Types
  2. Cannot Create Instances of Type Parameters
  3. Cannot Declare Static Fields Whose Types are Type Parameters
  4. Cannot Use Casts or instanceof With Parameterized Types
  5. Cannot Create Arrays of Parameterized Types
  6. A generic class cannot extend the Throwable class directly or indirectly
  7. A method cannot catch an instance of a type parameter
  8. Cannot Overload a Method Where the Formal Parameter Types of Each Overload Erase to the Same Raw Type

1. Cannot Instantiate Generic Types with Primitive Types

class Password<T> {
	private T t;

	public Password(T t) {
		this.t = t;
	}
}

When creating a Password object, you cannot substitute a primitive type for the type parameter T:

Password<int> pw = new Password<>(19019);//compile-time error

2. Cannot Create Instances of Type Parameters

public static <E> append(List<E> list) {
	E elem = new E();//compile-time error
	list.add(elem);
}

3. Cannot Declare Static Fields Whose Types are Type Parameters

public class BasketballPlayer<T> {
	private static T teamFouls; //Suppose you can do this.
}

Create three BasketballPlayer objects as follows:

BasketballPlayer<Byte> jodan = new BasketballPlayer<>();
BasketballPlayer<Short> pippen = new BasketballPlayer<>();
BasketballPlayer<Integer> rodman = new BasketballPlayer<>();

The type of teamFouls field can not be a Byte, Short, or Integer at the same time.

4. Cannot Use Casts or instanceof With Parameterized Types

Because the Java compiler removes all type parameters from the generic code, the runtime does not know if the generic type parameter is used.

public static <E> void rtti(List<E> list) {
	if (list instanceof ArrayList<Integer>) { //compile-time error
		//..
	}
}

The runtime does not distinguish between ArrayList<Integer> and ArrayList<String>.
If you use wildcards without constraints, you can ensure that the List is an ArrayList.

public static void rtti(List<?> list) {
	if (list instanceof ArrayList<?>) { //ok
		//..
	}
}

5. Cannot Create Arrays of Parameterized Types

List<Integer>[] arrayOfLists = new ArrayList<Integer>[2];//compile-time error

The following code illustrates what happens when different types are inserted into an array:

Object[] strings = new String[2];
strings[0] = "Hello";
strings[1] = 2019;//An ArrayStoreException is thrown.

If you try the same thing with a generic list, there would be a problem:

Object[] stringLists = new List<String>[];// compiler error, but pretend it's allowed
stringLists[0] = new ArrayList<String>();// OK
stringLists[1] = new ArrayList<Integer>();// An ArrayStoreException should be thrown, but the runtime can't detect it.

Because the runtime can not distinguish List<String> from List<Integer>, if arrays of parameterized lists were allowed, the previous code would fail to throw the desired ArrayStoreException.

6. A generic class cannot extend the Throwable class directly or indirectly.

For example, the following classes will not compile:

// Extends Throwable indirectly
class MathException<T> extends Exception { .. } //compile-time error
// Extends Throwable directly
class QueneFullException<T> extends Throwable { .. } //compile-time error

7. A method cannot catch an instance of a type parameter.

public static <T extends Exception> void execute(List<T> jobs) {
	try {
		for (T job : jobs) {
			//..
		}
	} catch (T e) {//compile-time error: Cannot use the type parameter T in a catch block
		//..
	}
}

You can, however, use a type parameter in a throws clause:

class Parser<T extends Exception> {
	public void parse(File file) throws T { //ok
		//..
	}
}

8. Cannot Overload a Method Where the Formal Parameter Types of Each Overload Erase to the Same Raw Type

public class Example {
	public void print(Set<String> strSet) { .. }
	public void print(Set<Integer> intSet) { .. }
}

A class cannot have two overloaded methods that will have the same signature after type erasure.

References