Friday, May 25, 2012

GIST NOTES 7 - Java Generics and Collections

GIST NOTES 7 - Java Generics and Collections

[DISCLAIMER: This is solely for non-commercial use. I don't claim ownership of this content. This is a crux of all my readings studies and analysis. Some of them are excerpts from famous books on  the subject. Some of them are my contemplation upon experiments with direct hand coded code samples using IDE or notepad.

I've created this mainly to reduce an entire book into few pages of critical content that we should never forget. Even after years, you don't need to read the entire book again to get back its philosophy. I hope these notes will help you to replay the entire book in your mind once again.]

[JDK 7]

> Object.equals() uses == operator to compare two objects. It just compares the two references refer to the same object or not

    public boolean equals(Object obj) {
        return (this == obj);

> trying to narrow the access level while overriding a method causes compilation error (be wary when overriding equals() method)

equals() contract
Reflexive: x.equals(x) returns true
Symmetric: if x.equals(y) true, then y.equals(x) should be true
Transitive: if x.equals(y) and y.equals(z) are true, then x.equals(z) also true
Consistent: equals() method should be consistent always within a JVM for a given pair of objects no matter how many times equals() method is called

null equality: for any non-null x, x.equals(null) should be false

hashCode() compatibility: honor the hashCode() method while implementing equals()

public int hashCode() is a native method in Object class.

Hashcodes are typically used to increase the performance of large collections of data.

Hashcode need not be unique to a particular object.

If two objects are considered equal, then their hashCode also should be equal in order for java Collections framework to work consistently with your class objects. Java Collections framework uses hashcode of the object to distribute keys across different buckets. If hashcode is not consistent, your class objects may be lost forever in Collections classes(e.g. HashMap).

hashCode() contract
>whenever hashCode() is invoked on the same object more than once during an execution of a java application it must return the same value unless otherwise the information used in equals() comaparison has changed; during another execution of the same application it can return a different value

>if two objects are equal according to equals() method, then hashCode() method should produce same integer for both objects

>if two objects are different according to equals(), then it is not required for hashCode() to return different hash codes; however producing different hash code for unequal objects would improve the performance of the hashtables

>if hash codes are different for two objects, then they cannot and should not be equal; equals() method should uphold this

>transient variables should not be used in hashCode() implementation; though compiler will not complain, it might cause problems while trying to locate your object in collections; since transient variables are not saved while serializing, the restored object may not be the same and might break hashCode() implementation; same goes for equals() method; say NO to transient variables while implementing these two methods

The core collections interfaces



The core concrete Classes
Maps:: HashMap, Hashtable, TreeMap, LinkedHashMap
Sets:: HashSet, LinkedHashSet, TreeSet
Lists:: ArrayList, Vector, LinkedList
Queues:: PriorityQueue
Utilities:: Collections, Arrays

>not all collections in collection framework implement "Collection" interface
>none of the map related interfaces and classes extend from "Collection" interface, though they are thought of as collections

1.collection - represents general data structures
2.Collection - represents java.util.Collection interface (Set, List and Queue extend from this);
 there are no direct implementation of Collection interface;
3.Collections - represents java.util.Collections concrete class which has loads of static utility methods

Class Hierarchy (refer the image)

I:Collection <- I:Set <- HashSet <- LinkedHashSet
I:Collection <- I:Set <- I:SortedSet <- I:NavigableSet <- TreeSet**

I:Collection <- I:List <- ArrayList/Vector/LinkedList*
I:Collection <- I:Queue <- PrioriotyQueue/LinkedList

I:Map <- Hashtable
I:Map <- HashMap <- LinkedHashMap
I:Map <- I:SortedMap <- I:NavigableMap <- TreeMap

[Interfaces start with 'I:' and parents come on the left hand side, children on the right]

* LinkedList is both a Queue as well as a List
** Tree things(which has tree in the name) are both navigable and sorted
*** Those that are unordered by nature(map and set), given Tree status

Collection Flavors
List - list of things
Set - bunch of unique things
Map - things with unique ID
Queue - things arranged in order

>A class can be 'unsorted and unordered'
>A class can be 'ordered but unsorted'
>A class can be 'ordered and sorted'
>A class can NEVER be 'sorted but unordered', because sorting is a specific type of ordering inherently

Sorting:: order in the collection is based on the natural order of elements, based on some rules known as sort order

HashSet - unordered and unsorted
LinkedHashSet - ordered but not sorted(ordered by addition)
Hashtable - unordered and unsorted (when iterating over, the order is random)
ArrayList - ordered but not sorted (ordered by position index, can insert anywhere)
LinkedHashSet - ordered but not sorted(ordered by addition)

>cares about index
>index related methods like get(int index) are available only in List based classes
>lists are ordered by index position
>can add elements at a particular index or at the end of the list

>growable array
>gives fast iteration and fast random access
>ordered but not sorted
>implements RandomAccess interface(marker interface), hence ArrayList supports fast(generally constant time) random access
>choose this over LinkedList when you need fast iteration but aren't as likely to be doing a lot of insertion and deletion
>methods are not synchronized

>holdover from earliest days of java; Vector and Hashtable were the original collections (rest were added at 1.2 and 1.4)
>same as ArrayList but methods are synchronized for thread safety
>due to synchronized, Vector is slow in performance
>thread safety can be obtained from Collections utility methods as well instead of using Vector
>Vector is the only class other than ArrayList to implement RandomAccess

>is ordered by index position(like ArrayList), except that elements are doubly-linked to one another
>methods to add/remove from beginning or end
>easy choice to implement stack or queue
>iterates more slowly than ArrayList
>but a good choice for fast insertion and deletion
>as of java 5, it was enhanced to implement Queue interface as well; hence supports peek(), poll(), offer() and such methods

>cares about uniqueness
>doesn't allow duplicates
>bases itself on equals() method implementation

>unsorted and unordered set
>uses hashcode of the object being inserted; the more efficient hashCode() implementation, the better access performance
>use this when you want no duplicates and don't care about order when you iterate through the elements

>an ordered version of HashSet
>maintains doubly-linked list across all elements
>if you care about iteration order, use this
>it lets you iterate through in the order in which elements were inserted(or added)

# when using HashSet or LinkedHashSet, you must override hashCode(), otherwise uniqueness of objects is not guaranteed

>is one of the two sorted collections (the other being TreeMap)
>uses Red-Black tree structure(special binary search tree with minimum possible height)
>guarantees that the elements will be in ascending order according to natural order
>lets you specify your own ordering rules by using Comparable or Comparator
>as of java 6, TreeSet also implements NavigableSet

>cares about unique identifiers for each value
>both key and value are objects
>relies on equals() to determine two keys are same or not

>unsorted unordered map
>access performance depends on the hashCode() implementation for your keys
>allows one null key and multiple null values

>legacy class
>synchronized counter part to HashMap
>doesn't allow null keys or values(throws NullPointerException in such cases)

>maintains insertion order(optionally access order, thru a flag to the constructor)
>slower than HashMap for adding removing elements
>faster iteration than HashMap

>sorted Map and hence ordered in the natural order
>lets you define custom sort order through Comparable or Comparator interfaces
>as of java 6, implements NavigableMap

>list of TO-DOs
>typically thought of as FIFO(first-in first-out)
>supports standard Collection methods + methods to add/subtract/review queue elements

>new with Java 5
>basic queues can be implemented with LinkedList
>purpose of PriorityQueue is to create "priority-in priority-out" queue as opposed to "first-in first-out)
>elements are ordered according to natural order or according to the Comparator set
>elements that are sorted first are accessed first; ordering represents the relative priority between elements

ArrayList over arrays
>ArrayList can grow dynamically
>it provides more powerful insertion and search mechanisms than arrays
>if there are duplicate elements in ArrayList, and when you try to remove an element, it removes the first encountered element that satisfies equals() method
>be vary of remove(Object o) and remove(int index) overloaded methods getting confused when you use autoboxing for an array list of Integer type (ArrayList); e.g. if you try to remove element 54 with remove(54), it tries to remove element at index 54 rather than an Integer object with value 54; if you are lucky you will get index out of bounds exception if index 54 is not present; remove(new Integer(54)) works fine

>when you override equals() method you always take 'Object type' argument because the method is inherited from Object class
>but when you implement compareTo() method from Comparable interface, you should take 'argument of the type of the object you are comparing' because Comparable interface supports generics and it lets you specify the type of the thing being compared before hand

equals(Object o){}
compareTo(MyDvd dvd){}

>to sort a class objects in multiple different ways without getting stuck with one implementation of Comparable interface, go for Comparator where the rule of comparing is stored externally in your own Comparator class and you can make any number of different Comparator classes and use them wherever appropriate

>you can even sort classes which you can't modify using this external Comparator

>int obj1.compareTo(obj2)
>returns negative int when obj2 is greater, positive int when obj1 is greater, zero when both are equal
>you must modify the class whose instances you want to sort
>only one sort sequence can be done
>implemented frequently by APIs such as String, Wrapper classes, Date, Calendar, etc

>int compare(obj1, obj2)
>return value is same as Comparable
>you build a class separate from the class whose instances you want to sort
>many sort sequences can be created
>meant to be implemented by third party classes

*both Comparable and Comparator are interfaces; they are appropriately put in different packages based on their purpose

# Arrays.sort() provides sorting capability for arrays in the same way Collections.sort() provides

Sorting arrays
>Arrays.sort(arrayToSort[], Comparator)
>loads of sort() overloaded methods to sort primitive data arrays in their natural order without the use of Comparator

#both Arrays.sort() and Collections.sort() are static methods; both alter the same object they are sorting and do not return result as a separate object;

#if two objects that are not comparable present in the array or collection, the sort will fail

Searching arrays and collections
>searches are performed using the binarySearch() method
>successful search returns the int index of the element searched
>unsuccessful search returns insertion point(index) as return value; insertion point is where the searched element can be added without affecting the sorted order of other elements
>0 and positive return values indicate successful search
>negative return value indicates insertion point on unsuccessful search
>since 0 is not available for negative range, -1 indicates 0th index, -2 indicates 1st index and so on; so insertion point is calculated by [-n -1] where n is the signed insertion index returned.

>the collection/array being searched must be sorted before you can search it
>attempting to search an unsorted array or collection will result in unpredictable results(not compiler error :))
>the collection/array sorted in natural order can only be searched in natural order using binarySearch() method; hence no Comparator is allowed
>comparators cannot be used while searching arrays of primitives(nobody wants your own way of arranging integers, strings, etc)
>the same comparator used to sort has to be used while searching; otherwise the consequences are dire
>even trying to search an array or collection that has been reverse-sorted(descending) will return incorrect result


Collection to Arrays
List and Set have toArray() methods to convert the collection into an array(returns a copy of the internal array)

Arrays to Collection
Arrays.asList() copies an array into a List; this list is backed by the original array; changes to the returned list write through to the array; that is changing either the array or the list, updates the other automatically; array and list both become joined at the hip;(makes the given array as the internal array for the new list)

> list.toArray() can return a new array or you can pass your own destination array list.toArray(dest[])

Lists and Iterators
list.iterator() returns an Iterator object;

Iterator methods: boolean hasNext() and Object next()

>no duplicates are allowed
>adding duplicate object, add() method returns false without adding the object to the set
>HashSet is fast because it uses hashcodes
>TreeSet keeps the unique objects sorted; adding uncomparable objects to a TreeSet throws ClassCastException; e.g. adding String to an integer TreeSet

>Class of objects used as keys in map, should override equals() and hashCode() methods for the map to work properly at runtime
>enums can be used as keys in maps; because enum overrides equals() and hashCode() methods
>if the object that is used as key is modified after using it in the map, then retrieval of the corresponding value for that key will fail because the attributes used by equals() method could have been modified in that object

Navigating TreeSet and TreeMap
>Since TreeSet and TreeMap are sorted in nature, Java 6 added NavigableMap and NavigableSet interfaces to their behavior in order to make arbitrary searching or navigation a lot easier than before
>before Java 6, headSet(), tailSet(), first() and last() methods were used to navigate TreeSet and methods like headMap(), tailMap(), firstKey() and lastKey() were used to navigate TreeMap
>now, more modern and easy to use methods are provided for navigation by NavigableSet and NavigableMap interfaces

Methods from SortedSet and SortedMap interfaces
headSet(item)/headMap(item) -> returns the portion of the set/map which is strictly less than 'item'; the sub set/map is tied to the original one; modifying one will update the other automatically; item is key in case of Map

tailSet(item)/tailMap(item) -> returns the portion strictly higher than 'item'

first()/firstKey() -> returns the first element(lowest) in the current set/map

last()/lastKey() -> returns the last element(highest) in the current set/map

subSet(fromVal,toVal)/subMap(fromVal,toVal) -> returns the portion of the set/map from value 'fromVal' (inclusive) to value 'toVal' (exclusive)

Methods from NavigableSet and NavigableMap interfaces
From NavigableSet:-

TreeSet.ceiling(e) - returns lowest possible element >= e (nothing but returning the next value to e or e itself)
TreeSet.higher(e)  - returns lowest possible element > e  (returns next value to e)
TreeSet.floor(e)   - returns highest possible element <= e (returns previous value to e or e itself)
TreeSet.lower(e)   - returns highest possible element < e  (returns previous value to e)
TreeSet.pollFirst()      - removes and returns the first element
TreeSet.pollLast()       - removes and returns the last element
TreeSet.descendingSet()  - returns a NavigableSet in reverse order

From NavigableMap:-

TreeMap.ceilingKey(k)  - returns lowest possible key >= k (same as TreeSet)
TreeMap.higherKey(k)   - returns lowest possible key > k  (-do-)
TreeMap.floorKey(k)    - returns highest possible key <= k
TreeMap.lowerKey(k)    - returns highest possible key < k
TreeMap.pollFirstEntry() - returns first key-value pair
TreeMap.pollLastEntry()  - returns last key-value pair
TreeMap.descendingMap()  - returns a NavigableMap in reverse order

* all the subsets or submaps returned in above methods are backed by the original set or map; when you add a new element to the original set/map, the subset/submap also gets updated as well(as long as the new element satisfies the condition to be part of the submap), not just the one way

* such behavior is called "backed collections"

* any attempt to add out of range element to a subset or submap, it throws exception

Inclusivity of subsets or submaps
headSet(element, boolean isInclusive)
headSet(element) -----behaves like-----> headSet(element, false)

tailSet(element, boolean isInclusive)
tailSet(element) ------behaves like------> tailSet(element, true)

subSet(fromEle, boolean isFromInclusive, toEle, boolean isToInclusive)
subSet(fromEle, toEle) ------behaves like------> subSet(fromEle, true, toEle, false)

*overloaded methods with isInclusive boolean argument are from NavigableSet interface; their normal counter parts are from SortedSet
*methods without isInclusive bool argument include starting point element as a rule
*the above inclusivity discussion applies to headMap(), tailMap() and subMap() methods from TreeMap in the similar manner
*methods without bool argument return SortedSet or SortedMap(old interfaces - before Java 6)
*methods with bool argument return NavigableSet or NavigableMap(interfaces that are new to Java 6)
*pollFirst/pollLast/pollFirstEntry and such polling methods are available only in Navigable[Set/Map]
*while creating sub sets or maps(using methods with bool arg), be sure to assign them to Navigable[Set/Map] variable; can't be assigned to Sorted[Set/Map] variable or Tree[Set/Map] variables; using methods without bool arg returns Sorted[Set/Map] and they don't have polling methods; so if you want to do some polling, you have to use methods with bool arg only
*polling either on parent set/map or sub set/map removes that element from both parent as well as the sub set/map if that element is present in both; so polling on sub set always affects the parent, but polling on parent may not affect the sub set because that element may not present in the sub set/map so no updates there

>orders elements using a user-defined priority
>can be a natural ordering (1 is higher priority than 2)
>priority can be ordered through a Comparator also that lets you define your own ordering
>Queue specific methods are peek(), poll() and offer()
>PriorityQueue uses natural ordering or a given Comparator to prioritize

peek() - returns top element without removing it from the queue
poll() - returns top element and removes it from the queue
offer() - puts the element into the queue according to its priority; top priority item goes to the top of the queue, least priority item goes to the end of the queue

static List asList(T[])

static int binarySearch(Object[], key) - search or detect insertion point
static int binarySearch(primitive[], key)
static int binarySearch(T[], key, Comparator)

static boolean equals(Object[], Object[])
static boolean equals(primitive[], primitive[])

public static void sort(Object[])
public static void sort(primitive[])
public static void sort(T[], Comparator)

public static String toString(Object[])
public static String toString(primitive[])

static int binarySearch(List, key)
static int binarySearch(List, key, Comparator)

static void reverse(List)
static Comparator reverseOrder() - reverse comparator for all Comparable objects
static Comparator reverseOrder(Comparator) - reverse comparator for the given Comparator

static void sort(List)
static void sort(List, Comparator)

List, Set and Map methods
boolean add(element) -> List/Set
boolean add(index, element) -> List

boolean contains(Object) -> List/Set
boolean containsKey(Object key) -> Map
boolean containsValue(Object value) -> Map

Object get(index) -> List
Object get(key) -> Map

int indexOf(Object) -> List

Iterator iterator() -> List/Set

Set keySet() -> Map

put(key,value) -> Map

remove(index) -> List
remove(Object) -> List/Set
remove(key)  -> Map

int size() -> List/Set/Map

Object[] toArray() -> List/Set
T[] toArray(T[]) -> List/Set

String natural order
>space comes before letters
>uppercase letters come before lowercase letters
>e.g. " f", "FF", "f ", "ff" are alphabetically sorted

Iterator - provided by all collections; helps to navigate the collection; Iterator also provides method to remove an element; more modern than Enumeration; throws ConcurrentModificationException when somebody else directly modified the collection while we are trying to modify the same collection through Iterator; has shorter method names than Enumeration[hasNext(), next() and remove()]

Enumeration - Some of the collections provide Enumeration to iterate over the collection; older version; does not provide facility to remove elements from the collection; since it doesn't modify the collection underneath, there is no need for ConcurrentModificationException

ConcurrentModificationException - it is a failfast feature on a best effort basis; rather than continuing to function under erraneous conditions it is better to fail quickly; though this behavior is not guaranteed, but provided on best effort basis; never rely on this behavior for decision making in your program or for correctness of the logic.

Hashtable provides both Enumerations and Iterators on certain views of the map; only Iterators throw ConcurrentModificationException for obvious reasons as stated above.

Initial Capacity - can be specified in the constructor; denotes no.of buckets used for distributing the keys; specifying large initial capacity for maps that would hold large no.of items, is beneficial because auto reallocation and rehashing is avoided and hence good performance;

Load Factor - can be specified in the constructor; denotes how much of current capacity has to be reached before reallocation is initiated; high load value, makes searching slow; low load value doesn't utilize the space but faster performance; trade off between time and space; default value 0.75;

Rehashing - whenever capacity of the map is increased, all the keys that were distributed across buckets have to be redistributed once again across the newer no.of buckets; quite performance intensive

*Values of Initial Capacity and Load Factor are just indicators; otherwise their actual behavior is implementation dependent

Big O Notation or order of complexity or computation time
Big O notation - describes a simplified maximum possible value of a function in terms of a factor variable the function depends on; this simplified function tells about what level of scale of the function value was caused by that factor variable

Let n be the factor variable of a function say time taken for performing an algorithm.

>Constant time O(1) - takes constant time to execute the algorithm for any n
>Linear time - O(n)
>Logarithmic - O(log n)
>Polynomial or algebraic - O(n^c)  where c > 1
>Exponential - O(c^n) where c > 1

Generic Types
*arrays had always been type safe, but collections had not
*a non-generic collection can hold any object or mix of different varieties(types) of objects together
*things in generic syntax angle bracket are called "parameterized type" or "type parameter"
*lets say the generic version of variables as 'type safe' variables
*method input arguments can be declared as type safe
*method return value can be declared as type safe
*compiler will stop you from using any container(object) other than the one that holds the declared type (illegal attempts especially inside those, those whose signature boasts the generic type safety)

e.g. List getDogList(){}
void process(ArrayList nameList){}

*generics way of allowing anything:

List list = new ArrayList();

[is identical to]

List list = new ArrayList();

[but they are not entirely same 100%]

*declarations (of all types including return args, method args) and constructors are where we put generics to convert a non-geric code into a generic code

*mixing generic and non generic collections:

One can say, generic code is like a strict law-enforcement area, and older non-geric codes are like lawless slums; when we mix these two codes, people can break your precious laws(type safety) in the non-generic code without any complaints from the compiler, while laws are still being enforced into geric version of code; but when some objects from generic area visit non-generic area and come back home, they would have become corrupted, holding banned objects in them!

But then compiler does a nice thing; any possible attempt to do unsafe/unchecked operations on a generic argument in non-generic codes, generates a compiler warning; funny thing is, it generates warning regardless the attempt to modify is within the type-safety law or not.

Generally compiler warnings do not matter; but matters when we mix generic and non-generic codes and if you heed the warning, you can detect bugs during compile time itself;

Why at runtime still the legacy code is allowed to insert wrong type objects? because...

JVM(runtime) does not know anything about generics. Generics is for compiler only. Compiler strips generics related stuff from the code through the process called "type erasure" and produces legacy version of code in class files; it even adds casting for you in the generics-stripped version.

That's how arrays are different from generics. They are type safe even at runtime.

They made generics feature this way to support legacy codes.

Compiling with "-Xlint:unchecked" flag shows all the dangerous operations in the legacy code.

So, all in all, the generics protection vanishes(even from your generics-version code) the moment you hand over your type safe collections to a legacy code or namely mixing generic and non-generic codes.

Boxing/Unboxing works between primitives and wrapper objects only. They cannot convert an Object type object into wrapper objects. The wrapper objects coming out of unsafe/untyped collections are of Object type. So, Unboxing would fail there.

Polymorphism and Generics
*arrays provide certain polymorphic behavior and generics collection do not
*generic type should match(exactly the same with no polymorphic treatment) on left and right side of the assignment operator(=), though the variable and object involved in the assignment can be of different types with polymorphic relationship (that is the conatiners/collections are allowed to have polymorphic treatment but not to their generics type marker)

*base types and generic types

List list = new ArrayList(); //legal

List and ArrayList are base types; JButton is generic type;

Object[] list = new JButton[3]; //legal
ArrayList list = new ArrayList(); //illegal

public class ArrayStoreException extends RuntimeException

Thrown to indicate that an attempt has been made to store the wrong type of object into
an array of objects.

For example, the following code generates an ArrayStoreException:

     Object x[] = new String[3];
     x[0] = new Integer(0);

*the above problem is due to polymorphic treatment of arrays (assigning a subtype array to a super type array reference)
*since generic collections try to provide the same type safety arrays do, generic also has the possibility to encounter ArrayStoreException kind of situations; but generics does not exist at runtime and no way to handle this situation with an exception and hence this rule of 'no polymorphism facility for generic collection assignment'
*type safety provided by arrays exist even at runtime
*but one can put elements in a polymorphic way inside those collections; only thing is they cannot treat the collection itself in a polymorphic way

ArrayList list = new ArrayList();
list.add(new Integer(0));//legal and no warnings either

Method arguments
#this way you can even send Number list which contains all Integers to a method which expects Number list and might try to add Float objects to it(which is ArrayStoreException kind of situation)

* allows you to pass collections that hold subtypes, to a method which expects collections holding supertype
* but it takes away something that was available earlier; that is, 'it doesn't allow any unsafe operation on the type-safe collection inside that method

CASE 1: no wildcard

public void process(List list)
list.add(new Dog()); //legal

process(new ArrayList()); //illegal

CASE 2: with wildcard

public void process(List list)
list.add(new Dog()); //illegal - was legal before using wild card in generics type

Animal ani = list.get(0);//legal - cast not required

process(new ArrayList()); // legal now

* wildcard becomes very strict and makes all possible attempts to modify the collection or unsafe assumptions/operations on that collection as ERRORS which were earlier treated as warnings
*even if T is an interface, only keyword 'extends' should be used in the wildcard syntax; e.g.
*'implements' keyword is not allowed in wildcard notations

*wildcard allows you to do modifications also to the generic collection; this is safe because it only allows collections of T or collections of super types of T and no peers of T are allowed

public void process(List list)
list.add(new Dog());//legal
list.add(new Cat());// compiler error
list.add(new Animal());//compiler error (very strict :) super type also not allowed)
list.add( (Dog) (new Animal()) );//legal - but cheating and dangerous

Animal ani = new Cat();
list.add((Dog)ani);//legal - but cheating and causes runtime error

Dog d = list.get(0);//compiler error - explicit cast required
Animal dd = list.get(0);//compiler error - explicit cast required

process(new ArrayList());//compiler error - no peer
process(new ArrayList());//legal
process(new ArrayList());//legal - super type allowed

#though this wildcard allows adding Dog objects, it doesn't allow adding Animal object; very funny, especially when the method accepts List marked for Animal; it also takes away the usual generics feature of castless assignment

*wildcard indicates any collection is allowed to be passed as method argument; but disallows all possible modifications and castless assignments regarding the collection

public void process(List list)
list.add("");//compiler error

Object obj = list.get(0);//legal
Dog d = list.get(0);//compiler error

process(new ArrayList());//legal
process(new ArrayList());//legal
process(new ArrayList());//legal

*how differs from

public void process(List list)
list.add(new Integer(0));//legal

Object obj = list.get(0);//legal - obviously

process(new ArrayList());//compiler error
process(new ArrayList());//legal


>takes all types of collections (, , , etc)
>disallows all possible modifications(adding even new Object() creates compile error)
>Object obj = list.get(0) is legal

*how differs from

>takes only collections
>allows adding any objects(anything at all from a Broom to Mountain) to the collection
>Object obj = list.get(0);//legal

*wildcards can only be used for reference declarations; they cannot be used with new operators while instantiating collections because, 'new' needs absolute type to create objects in the first place;

List list = new ArrayList();//compile error


>generic templates only provide as placeholder in your genericfied class; attempts to use the placeholder types(like or , etc) in a way that would require runtime dynamic behavior change, will not compile/work because generics is a compile time feature. I have seen codes in java APIs like T t = val; t.hashCode();  since all generic types are erased at compile time and replaced with 'Object', using Object class methods on these template place holders works fine. Trying to use any other methods, other than Object class methods will cause compile error. Because this is not C++ templates!

============DUE TO TYPE ERASURE=====================
public class MyClass {
    public static void myMethod(Object item) {
        if (item instanceof E) {  //Compiler error
        E item2 = new E();       //Compiler error
        E[] iArray = new E[10];  //Compiler error
        E obj = (E)new Object(); //Unchecked cast warning

class Generic {

public void add(K k, V v){
k.start(); //Doesn't compile because compiler can no way ensure that type K would have start() method

class Generic {

public void add(K k, V v){
k.start(); //COMPILES FINE

Generic methods and constructors
*type variables can only be used for a method alone
*type declaration identifier is placed before the return type in the method signature
*type variables have to be declared before start using them(either in the class signature or method signature)
*type variables localized to a constructor is also possible; they have to placed before constructor name

class Test{

Test(List list, X x){}

public void add(Y t){}

*it is possible to have a type variable same as the class name; compiler can infer what is what

class X{
X(X x){} //constructor X using generic type variable X; in this case the constructor argument is taken as generic type

* if you understand the following, you are a genious

  new Generic().hello(new ArrayList());//compiles
  new Generic().hello(new ArrayList());//compiles

//Generic class uses two generic types, and method hello() uses third generic type(localized to the method) and explicit mention of the type to a method is permitted but can be omitted; since methods can't be instantiated, this is how it looks when you say you are using a generic version of that method; if omitted, compiler can infer the type; say if hello() method only takes type objects the following will not compile since compiler's inferred type is not matching with the actual object passed

new Generic().hello(new ArrayList());

*wildcards cannot be used for defining generic classes/methods

  public class Test{} //illegal - compiler error
  public class Test{} //legal

Heap Pollution

Most parameterized types, such as ArrayList and List, are non-reifiable types. A non-reifiable type is a type that is not completely available at runtime. At compile time, non-reifiable types undergo a process called type erasure during which the compiler removes information related to type parameters and type arguments. This ensures binary compatibility with Java libraries and applications that were created before generics. Because type erasure removes information from parameterized types at compile-time, these types are non-reifiable.

Heap pollution occurs when a variable of a parameterized type refers to an object that is not of that parameterized type. This situation can only occur if the program performed some operation that would give 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.

Consider the following example:

    List l = new ArrayList();
    List ls = l;       // unchecked warning
    l.add(0, new Integer(42)); // another unchecked warning
    String s = ls.get(0);      // ClassCastException is thrown

Here is something to think about:-

class Hi {//array type while declaring is not allowed
T[] t = null;

public void hi(){ //array type like U[] is not allowed while declaring
Hi h = new Hi();  //array type is allowed while using - for a place holder type 'U'
Hi hs = new Hi(); //array type is allowed while using - for a specific type 'String'
Hi hi = new Hi();

Reference: Kathy Sierra's SCJP Book