Generics Flashcards
Dynamic Data Structures in Java
Arrays are the only data structures in to the Java language
However, we’ve seen that:
⚫ Java fundamentally deals with object references.
⚫ Multiple references to the same object are possible…
⚫ … in fact extremely useful!
By connecting objects together in interesting ways, we can form complex data structures
⚫ As you saw in SCC120, these are much more flexible than arrays.
⚫ It’s possible to build any of the data structures you looked at in SCC.120
from first principles…
Java Collections API at 35000 feet
An extensible set of classes and interfaces
⚫ An interface hierarchy provides a well defined set of interfaces for implementing data structures (conceptual):
⚫ The API also provides general, reusable implementations of these interfaces for a range of common data structures…
⚫ …all of which are type safe, through its use of generics.
The Collection Interface
List Interface
Commonly used implementations
Collections API comes with a set of implementations of these interfaces for commonly used data structures:
- ArrayList (Ordered, indexed list)
- LinkedList (Ordered, non-indexed)
- PriorityQueue (FIFO with optional prioritisation)
- HashSet (Unique, unordered)
- TreeSet (Unique, ordered)
- HashMap (Hashed key-value pairs (no ordering))
- TreeMap (Hashed key-value pairs (ordered by key))
Using Collection: ArrayList
ArrayList
⚫ Behaviour is much like an extensible array…
⚫ Items are maintained in a sequence, add/removed dynamically, etc.
⚫ Items are also enumerated and indexed by location.
⚫ Implemented internally as a simple Object[]… if the array becomes full, a new one is created and the data copied from the old one.
⚫ As a performance optimisation, the initial size can therefore be defined in the ArrayList constructor.
⚫ O(1) complexity for index lookups
⚫ O(1) complexity for additions (on average!)
⚫ O(n) complexity for remove
⚫ Makes this a good choice for a general purpose data structure!
⚫ Choose a LinkedList only if you need more scalable, predictable list operations…
Using Collections: HashMap
HashMap
⚫ Unordered collection of key/value pairs
⚫ Note generic type contains two formal type parameters (key and value)
⚫ Used for pairing up two objects!
⚫ Particularly useful for caching applications,
⚫ VERY fast. Approaching O(1) for key based addition, deletion, lookup.
Generics: Concept
Actually quite simple…
⚫ When we write classes and methods use a new type free syntax…
⚫ Only when an instance of a class is created is it bound to specific, given types!
⚫ Generics operate purely at compile time (unlike previous concepts)
⚫ …at least in Java anyway!
Defining Generics
Generic ‘types’ are defined as classes or interfaces
⚫ Appended with one or more formal type parameters.
⚫ Takes the form of an identifier in angled brackets. e.g.
⚫ This parameter represents one or more types that the generic type
needs defined before it can be instantiated
⚫ Multiple type parameters are legal (and are comma separated).
⚫ Within that generic class, the formal type parameter can be used
anywhere a normal type can.
⚫ e.g. in instance variables, method parameters and return types…
⚫ It can also be used to form identifiers for other generic types.
Using Generic Classes
Generic types are implicitly created when a specific instance of
them is defined.
⚫ The actual types are defined also in angled brackets when we create an
instance of the (generic) class
⚫ At this point, a ‘new’ class is generated for that specific type…
⚫ …that class is then instantiated, and a strongly typed object reference
returned!
⚫ All the usual Java type safety checking applies from then on.
⚫ Can have multiple ‘instantiations’ of generic types into actual types…
Generics and Polymorphism
Take care when applying polymorphism!
⚫ Rules with generic classes are a little different…
⚫ Consider a type A that is a type of B (e.g. it extends B or implements B)
⚫ It does not follow that LinkedList<a> is a type of LinkedList<b> !
⚫ Although you can add an object of type A to a LinkedList<b> !
⚫ This is because Java does not treat arrays or collections as “covariant”
⚫ Therefore this code is not legal (would result in a compile time error):</b></b></a>
Wildcard Types
Sometimes we want to talk generically about generics!
⚫ Wildcard types can be used for this purpose
⚫ <?> as a parameter matches any generic instantiation of a generic type
⚫ <? extends T> matches any type that is a subtype of T
⚫ There are limitations though due to type erasure.
⚫ printStuff has lost the type information of list, so can’t invoke any methods that require this type information (e.g. the add method).
Type Inference
Making syntax less verbose…
⚫ Note the double use of the Person type in the previous example
⚫ To create the object reference, and also the class instantiation.
⚫ Java can look at the types of variables you store return values in, and use this to infer the type of generic class needed!
⚫ This can reduce bloat of code…
⚫ The ‘diamond’ syntax (empty generic type declaration) is a signal to Java
to infer the type from context…
Benefits of Using Generic Classes
Extensibility with compile time type safety
⚫ Define functionality in classes that will work with any user defined types.
⚫ But once created, the class is bound to that actual type.
⚫ Parameters and return values use that exact type.
⚫ nb. we no longer need to downcast the return type of search operations.
⚫ Attempts to use other types result in compile time errors.
⚫ More errors trapped at compile time than run time is a good thing!
Limitations of Generics in Java 1
Runtime Type Erasure
⚫ Java generics are purely compile time mechanisms.
⚫ Meta information of generic types is non-existent at runtime…
⚫ e.g. a LinkedList<Book> cannot be distinguished from a LinkedList<Person> at runtime.</Person></Book>
Implications of Type Erasure
⚫ The protection given by generics does not extend to runtime mechanisms.
⚫ Object Reference casting is a run time mechanism
⚫ Refection is a runtime mechanism
⚫ No guarantee that your generic types that are proven type safe at compile time will remain so at runtime!
