Developer.com content and product recommendations are editorially independent. We may make money when you click on links to our partners. Learn More.
A common need for all but the most trivial of Java applications is the ability to gather together a collection of object references. Java has always had minimal support for object collections, with the Vector, Stack and Hashtable classes. There is also, of course, the handy array of objects (though the array is fixed in size). The Java 2 platform takes this one step further, by providing a common framework for representing object collections, as well as some concrete implementations of data structures. The Java collections framework is a set of interfaces and classes that provide an easy way to store collections of objects.
Why introduce a new API just for data structures?
The data structures provided by earlier editions of the Java platform are primitive tools for serious application development. For example, adding and deleting from an array requires reshuffling, and extra code has to be added for sorting. While a class like Vector helps with resizing, it still doesn’t guarantee order. That means extra work for developers, every time they want to use it. Wouldn’t it be nice if you didn’t care about the implementation of the data structure, and could just use it?
That’s what the collections framework provides. It introduces a variety of interfaces and classes, which belong to two distinct groups (Collection and Map). Collections are for storing a sequence of object references, whereas Maps provide a key-value pair mapping to objects. Together with some support classes, the collection framework offers developers the following benefits:
A wider variety of data structures, for those who don’t want to write their own
A standard framework for developing new data structures that are interoperable
Easy-to-use interfaces, with implementations that can be transparently substituted to improve application performance.
This new framework adds a new degree of maturity to the Java programming language, by providing a more-useful data structure API consistent with the flexibility and versatility of other parts of the Java API.
Introducing the
Collection
interface
The
Collection
interface provides a base from which other collection interfaces are extended. It declares several methods, which provide the means by which object references can be added to a collection, searched, accessed, and removed.
Collection Method
Purpose
add (Object)
Adds the specified object
addAll (Collection)
Adds all of the objects contained in the specified collection
clear ()
Dumps all stored objects
boolean contains (Object o)
Checks for presence of specified object
boolean containsAll (Collection)
Checks for presence of all objects contained in the specified collection
boolean isEmpty ()
Checks for an empty collection
Iterator iterator ()
Returns an
Iterator
– a sequence of data elements
remove (Object o)
Removes the specified object
removeAll (Collection)
Removes all objects contained in the specified collection
retainAll (Collection)
Removes all objects not contained in the specified collection
int size()
Returns the number of elements in the collection
Object[] toArray ()
Converts the collection to an array
The
Collection
interface offers a standard set of methods, regardless of the actual type of collection that is used. Indeed, in many situations the actual data structure used will be irrelevant to the code, and could be easily substituted (perhaps for performance reasons). By referring to the data structure as a
Collection
instance, and not its class, you can substitute it at a later date without requiring any further code changes.
Collection c;
c = new ArrayList(); OR
c = new LinkedList();
// Add elements to the collection
c.add ( … );
The collections framework also makes an important distinction between types of collections, by offering a further two new interfaces. A
Set
is a collection that accepts only one copy of an object, whereas a
List
can accept multiple copies. Figure One shows the relationship between the
Collection, Set,
and
List
interfaces.
Figure 1. Collection interfaces.
More often than not, programmers will be using implementations of the
List
interface, which corresponds to the old
java.util.Vector
class. In fact, the
Vector
class has been modified to make it compatible with the new
List
interface. Also, there is another interface (
SortedSet
) which imposes a further condition that a
Set
be sorted. When writing data structure implementations, these interfaces will be very useful (and corresponding
AbstractCollection
,
AbstractList
, and
AbstractSet
templates are also provided). However, in normal circumstances, developers will choose existing implementations provided as part of the collections framework.
Introducing the
Map
interface
The
Map
interface declares methods for classes that implement a mapping between keys and values. While part of the collections framework, it does not subclass the
Collection
interface — it is for representing mappings not aggregations.
Map
implementations are subject to a few restrictions:
Each key maps to a single
Object
(though this object can itself be a
Collection
)
Each key is unique.
If these restrictions sound extreme, remember that multiple values can be achieved by storing a
Collection
rather than an
Object
. Maps are extremely useful, and even before their introduction in JDK 1.2, were quite commonplace. The
Hashtable
class is a
Map
that most developers will be familiar with, and it has been modified in JDK 1.2 to implement the
Map
interface. The following table shows the most useful methods of the
Map
interface.
Map Method
Purpose
clear ()
Dumps all stored objects
boolean containsKey (Object)
Checks for the presence of a key
boolean containsValue (Object)
Checks for the presence of a value
Set entrySet ()
Returns a
Set
collection of key-value mappings represented as
Map.Entry
instances
boolean equals (Object)
Checks for equality between two maps
Object get (Object)
Returns the value associates with the specified key, and
null
if no such mapping exists, or if the key is mapped to the
null
value
boolean isEmpty ()
Checks for an empty map
Set keySet()
Returns a
Set
collection of all keys
Object put (Object key, Object value)
Maps the key to the specified value, overwriting any previous mapping for that key. Returns the previous mapping (which may be
null
)
Object putAll (Map)
Puts all key-value pair mappings in the specified map into the current map. Similiar to the
Collection.addAll
(Collection)
method
remove (Object o)
Removes specified object
int size()
Returns number of elements in collection
As in the
Collection
interface, the
Map
interface provides a standard set of methods that can be used with Maps. By maintaining reference to the
Map
interface, and not
Map
implementations, it is easy to later substitute an alternate data structure. Also, the
Map
interface is similar to the older JDK 1.0
java.util.Dictionary
abstract class. When designing new implementations, the
Map
interface should be used in place of the
Dictionary
class. This means implementing the
Map
interface, instead of extending the
Dictionary
class.
// Old way of creating a map-like data structure public class FileBasedHashTable extends java.util.Dictionary
// New way of creating a map-like data structure public class FileBasedHashtable implements java.util.Map
There is also a
SortedMap
interface, which provides a method for sorting the key mappings. When using a
SortedMap
, all keys must implement the new
Comparable
interface, which is required to allow comparison during the sorting process. The good news is that most of the wrapper objects for primitive data-types (
Byte, Character, Double, Float,
String,
, etc.) implement the
Comparable
interface, but when using custom-designed classes as keys, you will need to implement
Comparable
, or avoid using a
SortedMap
.
Summary
With the new collections framework included in the Java 2 platform, developers finally have at their fingertips a good suite of data structure implementations and interfaces from which further classes can be built. In the next part of our lesson (The Java Collections Framework: Implementations), we’ll examine the new classes that form the collections framework, such as linked lists and trees. We’ll also look at how you can safely use collections in a multithreaded environment and how to convert from a
David Reilly is a software engineer and freelance technical writer living in Australia. A Sun Certified Java 1.1 Programmer, his research interests include the Java programming language, as well as networking and distributed systems. He can be reached via e-mail at java@davidreilly.com, or via his personal Web site.