Java Collections and
Generics
·
The
Java Collections Framework
·
Java
Generics
13.1. The Java
Collections Framework
·
Java
arrays have limitations.
o They cannot
dynamically shrink and grow.
o They have limited
type safety.
o Implementing
efficient, complex data structures from scratch would be difficult.
·
The
Java Collections Framework is a set of classes and interfaces implementing
complex collection data structures.
o A collection is
an object that represents a group of objects.
·
The
Java Collections Framework provides many benefits:
o Reduces programming
effort (already there)
o Increases performance
(tested and optimized)
o Part of the core API
(available, easy to learn)
o Promotes software
reuse (standard interface)
o Easy to design APIs
based on generic collections
The
Java Collections Framework consists of:
Collection
interfaces
Collection, List,
Set, Map, etc.
General-purpose
implementations
ArrayList,
LinkedList, HashSet, HashMap, etc.
Special-purpose
implementations
designed for
performance characteristics, usage restrictions, or behavior
Concurrent
implementations
designed for use in
high-concurrency contexts
Wrapper
implementations
adding
synchronization, immutability, etc.
Abstract
implementations
building blocks for
custom implementations
Algorithms
static methods that
perform useful functions, such as sorting or randomizing a collection
Infrastructure
interfaces to support
the collections
Array
utilities
static methods that
perform useful functions on arrays, such as sorting, initializing, or converting
to collections
13.2. The
Collection Interface
·
java.util.Collection is the root
interface in the collections hierarchy.
o It represents a group
of Objects.
o Primitive types
(e.g., int) must be boxed
(e.g., Integer) for inclusion in a collection.
o More specific
collection interfaces (e.g., List) extend this interface.
·
The
Collection interface includes a variety of methods:
o Adding objects to the
collection: add(E), addAll(Collection)
o Testing size and
membership:
size(), isEmpty(), contains(E),containsAll(Collection)
o Iterating over
members: iterator()
o Removing members:
remove(E), removeAll(Collection), clear(),retainAll(Collection)
o Generating array
representations: toArray(), toArray(T[])
The
Collection interface does not say anything about:
·
the
order of elements
·
whether
they can be duplicated
·
whether
they can be null
·
the
types of elements they can contain
This
interface is typically used to pass collections around and manipulate them in
the most generic way.
13.3. Iterating
Over a Collection
·
An iterator is
an object that iterates over the objects in a collection.
·
java.util.Iterator is an interface
specifying the capabilities of an iterator.
o Invoking the iterator() method
on a collection returns an iterator object that implements Iterator and knows
how to step through the objects in the underlying collection.
·
The
Iterator interface specifies the following methods:
o hasNext() -
Returns true if there are
more elements in the collection; false otherwise
o next() -
Returns the next element
o remove() -
Removes from the collection the last element returned by the iterator
13.4. The List
Interface
·
The java.util.List Interface extends the Collection interface.
·
The
List interface declares methods for managing an ordered collection of object (asequence).
You can:
o Control where each
element is inserted in the list
o Access elements by
their integer index (position in the list)
o Search for elements
in the list
o Insert duplicate
elements and null values, in most
List implementations
·
Some
additional methods provided by List include:
o add(int index, E element) — Insert
an element at a specific location (without an index argument, new elements are
appended to the end)
o get(int index) — Return
an element at the specified location
o remove(int index) — Remove
an element at the specified location
o set(int index, E element) — Replace
the element at the specified location
o subList(int fromIndex, int toIndex) — Returns
as a List a modifiable view of the
specified portion of the list (that is, changes to the view actually affect the
underlying list)
13.5. Classes
Implementing List
·
Java
provides several classes that implement the List interface.
·
Two
are used most commonly:
java.util.ArrayList
An ArrayList is
usually your best bet for a List if the values remain fairly static once you’ve
created the list. It’s more efficient than a LinkedList for random access.
java.util.LinkedList
A LinkedList provides
better performance than an ArrayList if you’re frequently inserting and
deleting elements, especially from the middle of the collection. But it’s
slower than an ArrayList for random-access.
13.6. The Set
and SortedSet Interfaces
·
The java.util.Set Interface extends the Collection interface.
·
The
Set interface declares methods for managing a collection of objects that
contain no duplicates.
o The basic Set
interface makes no guarantee of the order of elements.
o A Set can contain at
most one null element.
o Mutable elements
should not be changed while in a Set.
·
The
Set interface adds no methods beyond those of the Collection interface.
o The Set interface
simply enforces behavior of the collection.
·
The java.util.SortedSet interface extends Set so that
elements are automatically ordered.
o A SortedSet Iterator
traverses the Set in order.
o A SortedSet also adds
the methods first(), last(), headSet(), tailSet(),
and subSet()
13.7. Classes
Implementing Set
·
Java
provides several classes that implement the Set interface, including:
+ java.util.HashSet:: A hash table implementation of the
Set interface. The best all-around implementation of the Set interface,
providing fast lookup and updates.
java.util.LinkedHashSet
A hash table and
linked list implementation of the Set interface. It maintains the insertion
order of elements for iteration, and runs nearly as fast as a HashSet.
java.util.TreeSet
A red-black tree
implementation of the SortedSet interface, maintaining the collection in sorted
order, but slower for lookups and updates.
13.8. The Queue
Interface
·
The java.util.Queue interface is a collection designed for holding
elements prior to processing.
o Besides basic
Collection operations, queues provide additional insertion, extraction, and
inspection operations.
o Queues can implement
FIFO (queue), LIFO (stack), and priority ordering.
o Queues generally do
not accept null elements.
·
Queue
operations include:
o Inserting
elements: add() and offer()
o Removing and
returning elements: remove() and poll()
o Returning elements
without removal: element() and peek()
o
·
The java.util.concurrent.BlockingQueue interfaces declare additional
blocking put() andtake() methods,
designed for concurrent access by multiple threads.
General-purpose
Queue implementations:
·
java.util.LinkedList
·
java.util.PriorityQueue
·
Concurrency-specific
BlockingQueue implementations:
·
java.util.concurrent.ArrayBlockingQueue
·
java.util.concurrent.ConcurrentLinkedQueue
·
java.util.concurrent.DelayQueue
·
java.util.concurrent.LinkedBlockingQueue
·
java.util.concurrent.PriorityBlockingQueue
·
java.util.concurrent.SynchronousQueue
13.9. The Map
Interface
·
The java.util.Map interface does not extend the
Collection interface!
·
A
Map is a collection that maps key objects to value objects.
o A Map cannot contain
duplicate keys
o Each key can map to
at most one value.
·
The
Map interface methods include:
o Adding key-value
pairs to the collection: put(K,
V), putAll(Map)
o Retrieving a value by
its key: get(K)
o Testing size: size(), isEmpty()
o Testing
membership: containsKey(K), containsValue(V)
o Removing
members: remove(K), clear()
·
The java.util.SortedMap interface extends Map so that
elements are automatically ordered by key.
o Iterating over a
SortedMap iterates over the elements in key order.
o A SortedMap also adds
the methods firstKey(), lastKey(), headMap(), tailMap(),
andsubMap()
13.10. Retrieving
Map Views
·
You
can also also retrieve collections as modifiable views from
the Map representing the keys (keySet()), the values (values()),
and a Set of key-value pairs (entrySet()).
o These collections are
used typically to iterate over the Map elements.
o These collections are
backed by the Map, so changes to the Map are reflected in the collection views
and vice-versa.
·
Iterating
over Map elements is done typically with a Set of objects implementing thejava.util.Map.Entry interface.
o You retrieve the Set
of Map.Entry objects by invoking Map.entrySet().
o To iterate over the
Map elements using an explicit Iterator:
o for
(Iterator i = map.entrySet().iterator; i.hasNext(); ) {
o Map.Entry entry = (Map.Entry) i.next();
o System.out.println( entry.getKey() +
":\t" + entry.getValue() );
o }
o To iterate over the
Map elements using the for-each syntax:
o for (
Map.Entry entry: map.entrySet() ) {
o System.out.println(entry.getKey() +
":\t" + entry.getValue());
o }
13.11. Classes
Implementing Map
·
Java
provides several classes that implement the Map interface, including:
+ java.util.HashMap:: A hash table implementation of the
Map interface. The best all-around implementation of the Map interface,
providing fast lookup and updates.
java.util.LinkedHashMap
A hash table and
linked list implementation of the Map interface. It maintains the insertion
order of elements for iteration, and runs nearly as fast as a HashMap.
java.util.TreeMap
A red-black tree
implementation of the SortedMap interface, maintaining the collection in sorted
order, but slower for lookups and updates.
13.12. The
Collections Class
·
The java.util.Collections class (note the final "s"
) consists exclusively of static methods that operate on or return collections.
Features include:
o Taking a collection
and returning an unmodifiable view of the collection
o Taking a collection
and returning a synchronized view of the collection for thread-safe use
o Returning the minimum
or maximum element from a collection
o Sorting, reversing,
rotating, and randomly shuffling List elements
·
Several
methods of the Collections class require objects in the collection to be
comparable.
o The object class must
implement the java.lang.Comparable interface.
o The object class must
provide an implementation of the compareTo() method, which a
negative integer, zero, or a positive integer as this object is less than,
equal to, or greater than the specified object.
13.13. Type
Safety in Java Collections
·
The
Java Collections Framework was designed to handle objects of any type.
o In Java 1.4 and
earlier they used Object as the type for any object added to the collection.
o You had to explicitly
cast the objects to the desired type when you used them or else you would get
compile-time errors.
Employee e = (Employee)
list.get(0);
o Worse yet, if you
were dealing with a collection of objects, say of type Dog, and then accidentally
added an object of an incompatible type, say a Cat, your code could eventually
try to cast the object to the incompatible type, resulting in a runtime
exception.
13.14. Java
Generics
·
Java
Generics, introduced in Java 5, provide stronger type safety.
·
Generics
allow types to be passed as parameters to
class, interface, and method declarations. For example:
List<Employee> emps =
new ArrayList<Employee>();
·
The <Employee> in this example is a type parameter.
o With the type
parameter, the compiler ensures that we use the collection
with objects of a compatible type only.
o Another benefit is
that we won’t need to cast the objects we get from the collection:
Employee e = emps.get(0);
o Object type errors
are now detected at compile time, rather than throwing casting exceptions at
runtime.
13.15. Generics
and Polymorphism
·
What
can be confusing about generics when you start to use them is that collections
of a type are not polymorphic on the type.
o That is, you
can not assign a List<String> to a reference
variable of type List<Object>(and by extension,
pass a List<String> as an argument
to a method whose parameter is type List<Object>); it results in a
compiler error.
o Why? If allowed, we
could then add objects of an incompatible type to the collection through the
more “generic” typed reference variable.
·
So
if you define a printCollection() to accept a
parameter typed List<Person>, you can pass
only List<Person> collections as
arguments.
o Even if Employee is a
subclass of Person, a List<Employee> can’t be
assigned to aList<Person>.
Here’s
an illustration of how type parameters are not polymorphic for collections:
13.16. Type
Wildcards
·
The ? type
parameter wildcard is interpreted as “type unknown.”
o So declaring a
variable as List<?> means that you
can assign a List of any type of object to the reference variable.
o However, once
assigned to the variable, you can’t make any assumptions about the type of the
objects in the list.
·
So
defining your method as printCollection(List<?>
persons) means
that it can accept a List of any type.
o But when invoked, you
can’t make any assumptions as to the type of objects that the list contains.
o Remember, ? is
“type unknown”.
o At best, you know
that everything can be treated as an Object.
13.17. Qualified
Type Wildcards
·
Declaring
a variable or parameter as List<?
extends Person>,
says that the list can be of all Person objects, or all objects can be of (the
same) subclass of Person.
o So you can access any
existing object in the List as a Person.
o However, you
can’t add new objects to the List.
o The list might
contain all Person objects… or Employee objects, or Customer objects, or
objects of some other subclass of Person. You’d be in trouble if you could add
a Customer to a list of Employees.
·
Another
type wildcard qualifier is super.
o List<? super Employee> means a List of objects of type
Employee or some supertype of Employee.
o So the type is
“unknown,” but in this case it could be Employee, Person, or Object.
o Because you don’t
know which, for “read” access the best you can do is use only Object methods.
o But you can add new
Employee objects to the list, because polymorphism allows the Employee to be
treated as a Person or Object as well.
·
Both extends and super can
be combined with the wildcard type.
import java.util.*;
public class
GenericsWildcardExample2 {
public static void main( String[] args) {
List<Dog> kennel = new
ArrayList<Dog>();
kennel.add( new Dog() );
List<? extends Animal> objs =
kennel;
for (Animal o: objs) {
o.identify();
}
/*
* However, it would be a compilation
error to try to
* add new objects to the list through
objs. We don't know
* what type of objects the List
contains. They might be
* all Dogs, or all Cats, or all
"generic" Animals.
*/
}
}
13.18. Generic
Methods
·
A generic
method is one implemented to work with a variety of types.
o The method definition
contains one or more type parameters whose values are determined when the
method is invoked.
o Type parameters are
listed within <> after any
access modifiers and before the method return type.
o You can use any
identifier for a type parameter, but single letters like <T> are
used most often.
·
For
example:
·
static <T> void addToCollection(T p, Collection<T>
c) {
·
}
o In this example, the
object p and the objects
in the collection c must all be the
same type.
·
You
can use type wildcards, extends, and super in
generic method definitions as well.
import java.util.*;
public class
GenericsWildcardExample{
public static <T> void addOne( T obj,
Collection<? super T> c) {
c.add(obj);
}
public static <U, T extends U> void
addTwo( T obj, Collection<U> c) {
c.add(obj);
}
public static void main( String[] args) {
List<Animal> menagerie = new
ArrayList<Animal>();
// Add a Cat and a Dog
menagerie.add( new Cat() );
menagerie.add( new Dog() );
// And now let's try using our generic
methods to add objects
addOne( new Cat(), menagerie);
addTwo( new Dog(), menagerie);
for (Animal o: menagerie) {
o.identify();
}
}
}
No comments:
Post a Comment