Book Excerpt Index
Mastering JavaTM
Chapter 17: Java Collections
by John Zukowski
(December 1998)
This is an excerpt from Mastering JavaTM 1.2, published by
Sybex
Inc. Written by John Zukowski, a long-time contributer to the JDC, this
book offers in-depth coverage of Java 2, including such topics as building
forms with Swing, creating Java graphics with the 2D API, implementing
drag-and-drop support, providing built-in security with the Java Cryptography
architecture, integrating your Java program with CORBA, enhancing server-side
performance with servlets, and building fast Java solutions. The book comes
with a CD that contains all the example code and executable files, along
with links to third-party tools to use with Java.
This chapter focuses on supporting advanced data structures with the
Collections API.
Developing in Java frequently requires you to work with unknown
quantities of objects. Even when working with fixed amounts of objects,
sequential access (arrays) is not always the best access method. To
support working with groups of objects, Java provides a whole slew of
classes. In fact, the concept is so important that how Java handles
collections of objects changed dramatically in Java 1.2. An entirely new
set of around 25 classes was added to the java.util
package
to describe the Java Collections API framework.
This chapter reviews data structures. Starting off with the familiar
array object, we look at how Java handles a single object representing a
group of objects. Next, we go through the various pre-Collections API
containers. Although new programs should avoid the historic collection
classes, existing programs still use them. Understanding how they work,
and their limitations, will help you understand why the new collection
classes were added. Finally, the chapter explores the Collections
framework introduced in Java 1.2.
NOTE:
If you like the Java 1.2 Collections framework, you can use
a subset in Java 1.1. Download the libraries from
http://java.sun.com/beans/infobus/#collections
and read the informational file at
http://java.sun.com/beans/infobus/#collectionsreadme.html
for usage instructions.
Arrays Review
Chapter 6 provided an overview of Java arrays. Basically, an
array is a fixed-size collection of objects of the same type. Besides
storing objects, arrays can also store primitive datatypes. When you
create an array, you specify the type of object (or primitive) to
store in the array and the number of elements you wish to store. This
allows array usage to be type-safe and very efficient. Since you can only
store one type of data in an array, you can only get that same type back.
Also, since you've allocated all the space for the array at declaration
time, placing an element into an array is very fast. But therein lies the
potential problem with arrays. You must allocate all their space at once,
and they cannot get bigger than you anticipated—at least not without
an expensive array copy operation. If you know the datatype beforehand and
you know what the final size should be, you're OK with arrays. Otherwise,
you need to look at one of Java's other collection classes.
Working with an array is just like working with any other object. You
can access its single instance variable length
to discover
the array's size or you can get the element at a certain location by
passing an int
to the brackets ([]) of an array reference
variable. Array access also always performs bounds checking and throws
an ArrayIndexOutOfBoundsException
if you attempt to access
a nonexistent element.
WARNING:
The index into an array cannot be a long
variable.
This is a compile-time error, instead of a runtime
exception.
The following program demonstrates array usage by performing runtime
type checking to determine the array datatype. When the array is an array
of integers, the square root of each element is printed. When the array
is an array of doubles, the trigonometric sine function is performed:
public class MyArrays {
public static void printValues (Object array) {
if (array instanceof int[]) {
// Cast to int array
int intArray[] = (int[])array;
int len = intArray.length;
for (int i=0;i<len;i++) {
System.out.print (
Math.sqrt (intArray[i]) + " ");
}
} else if (array instanceof double[]) {
// cast to double array
double doubleArray[] = (double[])array;
int len = doubleArray.length;
for (int i=0;i<len;i++) {
System.out.print (
Math.sin (doubleArray[i]) + " ");
}
}
System.out.println ();
}
public static void main (String args[]) {
int ints[] = {1, 4, 9, 16, 25, 36};
double doubles[] = {0.0, Math.PI / 6.0,
Math.PI / 2.0, 3.0 * Math.PI / 2.0};
printValues (ints);
printValues (doubles);
try {
ints[90] = 27;
} catch (ArrayIndexOutOfBoundsException e) {
System.err.println (
"Invalid array access: " + e.getMessage());
}
}
}
The output from running the program follows:
1.0 2.0 3.0 4.0 5.0 6.0
0.0 0.49999999999999994 1.0 -1.0
Invalid array access: 90
NOTE:
The second value on the second line is really 0.5 when rounded
off. The print method does not provide the means to format output,
and Math.sin(PI/6.0) is not 0.5, because of limitations in the sin
routine and/or roundoff in PI and PI/6.0.
Vectors, Stacks, and Enumeration
The historic collection classes have existed since the beginning of
Java's time. While there is nothing technically wrong with them, their
usage should be limited to the maintenance of Java 1.0 and 1.1 programs.
The primary, historic collection classes that provide ordered access are
Vector
and Stack
. The interface
Enumeration
offers the means to step through the contents.
Working with Vectors
While arrays are required to be of fixed size and have a homogenous
datatype, class Vector
encapsulates a heterogeneous
linked-list and array hybrid:
- Vectors are heterogeneous because they do not insist
on each element being of a certain type—many object
types can be mixed within one vector.
- Vectors are an array hybrid because they can grow
dynamically when elements are added.
Here is the definition of Vector
:
public class Vector extends AbstractList
implements List, Cloneable, Serializable {
protected int capacityIncrement;
protected int elementCount;
protected Object elementData[];
public Vector();
public Vector(int initialCapacity);
public Vector(
int initialCapacity,
int capacityIncrement);
public Vector(Collection c);
public void add(int index, Object obj);
public synchronized boolean add(Object obj);
public synchronized boolean addAll(
int index,
Collection c);
public synchronized boolean addAll(Collection c);
public synchronized void addElement(Object obj);
public int capacity();
public void clear();
public synchronized Object clone();
public boolean contains(Object obj);
public synchronized boolean containsAll(Collection c);
public synchronized void copyInto(Object anArray[]);
public synchronized Object elementAt(int index);
public Enumeration elements()
;
public synchronized
void ensureCapacity(int minCapacity);
public synchronized boolean equals(Object obj);
public synchronized Object firstElement();
public synchronized Object get(int index);
public synchronized int hashCode();
public int indexOf(Object obj);
public synchronized int indexOf(
Object obj,
int startIndex);
public synchronized void insertElementAt(
Object obj,
int index);
public boolean isEmpty();
public synchronized Object lastElement();
public int lastIndexOf(Object obj);
public synchronized int lastIndexOf(
Object obj,
int startIndex);
public synchronized Object remove(int index);
public boolean remove (Object obj);
public synchronized removeAll (Collection c);
public synchronized void removeAllElements();
public synchronized boolean
removeElement(Object obj);
public synchronized void removeElementAt(int index);
public synchronized boolean
retainAll (Collection c);
public synchronized Object set(
int index, Object obj);
public synchronized void setElementAt(
Object obj,
int index);
public synchronized void setSize(int newSize);
public int size();
public synchronized Object[] toArray();
public synchronized Object[] toArray(Object aType[]);
public synchronized String toString ();
public synchronized void trimToSize();
}
NOTE:
If you've used the historical collection classes prior to Java
1.2, you may notice that some of these have been retrofitted into
the Collections API added with Java 1.2.
Since vectors can store any datatype, all vector operations work with
the Object
class. This means you lose the type safety
provided by an array. And, whenever you access anything acquired from
a vector, you have to cast it back to its original type. This, and
the cost associated with dynamic growth, are the penalties associated
with using Vector
.
While working with arrays, you access the size with the length instance
variable and set elements with an assignment (=
) operation.
For a vector, the length is acquired with the size()
method
and assignment is via the set(int position, Object obj)
or
setElementAt(Object obj, int position)
method. Neither
set()
nor setElementAt()
support dynamic growth.
For a vector to grow without bounds, you would use either
add(Object obj)
or addElement(Object obj)
,
which both add the object at the end. Retrieval of
elements is via either the get(int position)
or the
getElement(int position)
method.
TIP:
If you need to store a primitive datatype within a vector, or any
other collection besides an array, you need to use the wrapper
classes found in the java.lang
package. For instance,
to store an int
, you wrap it into an Integer:
Integer in = new Integer (5)
. Then, you can add the
Integer
object in
to the collection.
To demonstrate the vector class, the following program works with
some of its basic operations. It stores planets in a vector and then
prints out each planet object, using the implicit call to
Object.toString ()
made by println()
.
import java.util.*;
public class ThePlanets {
static class Planet {
private String name;
Planet (String s) {
name = s;
}
public String toString () {
return getClass().getName() + "[" + name + "]";
}
}
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", " Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto"};
int namesLen = names.length;
Vector planets = new Vector (namesLen);
for (int i=0; i < namesLen; i++) {
planets.addElement (new Planet (names[i]));
}
int planetsLen = planets.size();
for (int i=0; i < planetsLen; i++) {
System.out.println (planets.elementAt (i));
}
}
}
While this shows the basic vector operations, you will frequently need
to do something more with each element retrieved from the vector than an
operation inherited from Object
. The following example extends
the first by adding the number of moons to each planet definition. Instead
of using the toString()
method to print the planet data, specific
methods of Planet
are used to get information about the vector
elements:
import java.util.*;
public class ThePlanetsAndMoons {
static class Planet {
private String name;
private int moonCount;
Planet (String s, int moons) {
name = s;
moonCount = moons;
}
public String toString () {
return getClass().getName() +
"[" + name + "-" + moonCount + "]";
}
public final String getName() {
return name;
}
public final int getMoonCount () {
return moonCount;
}
}
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", "Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto"};
int moons[] = {0, 0, 1, 2, 16, 18, 17, 8, 1};
int namesLen = names.length;
Vector planets = new Vector (namesLen);
for (int i=0; i < namesLen; i++) {
planets.addElement (
new Planet (names[i], moons[i]));
}
Planet p;
int planetsLen = planets.size();
for (int i=0; i < planetsLen; i++) {
p = (Planet)(planets.elementAt (i));
System.out.println (
p.getName() + " : " + p.getMoonCount());
}
}
}
To demonstrate the potential for problems, the following defines a new
class Comet
and adds one to the planets
vector
used previously. Since Vector
allows you to add anything
to the vector, addElement()
doesn't cause any problems.
However, when you cast the value retrieved with elementAt()
to a Planet
, you'll get a ClassCastException
thrown:
static class Comet {
private String name;
Comet (String s) {
name = s;
}
public String toString() {
return getClass().getName() + "[" + name + "]";
}
public final String getName() {
return name;
}
}
…
planets.addElement (new Comet ("Hale-Bopp"));
…
// Exception thrown here for Comet
p = (Planet)(planets.elementAt (i));
This just goes to show that you should always know what you are getting
out of a collection when you use any of them.
NOTE:
For an online multimedia tour of the solar system, stop by
http://seds.lpl.arizona.edu/nineplanets/nineplanets/nineplanets.html
.
TIP:
In C++, the ability to specify the use of a specific datatype for
something at compile-time is supported directly in the language by
templates. The concept itself is called parameterized types.
Java provides support for neither parameterized types nor collections
of a specific datatype.
Pushing Stacks
Class Stack
implements that old faithful data structure:
a simple last-in-first-out (LIFO) stack. In Java, the Stack
class is actually a subclass of Vector
. So, in addition to
all the vector operations, you can also push objects onto the stack, pop
objects off the stack, peek at the object on the top of the stack, check
whether the stack is empty, and search for an object on the stack. The
definition of class Stack
shows off this functionality:
public class Stack extends Vector {
public Stack();
public boolean empty();
public synchronized Object peek();
public synchronized Object pop();
public Object push (Object obj);
public synchronized int search (Object obj);
}
The following provides a simple demonstration of the Stack
class. Notice that the Vector
methods are available since
Stack
is a subclass; however, they should be avoided for
the sake of clarity:
import java.util.Stack;
public class JupiterMoons {
public static void main (String args[]) {
String names[] = {
"Metis", "Adrastea", "Amalthea",
"Thebe", "Io", "Europa", "Ganymede", "Callisto",
"Leda", "Himalia", "Lysithea", "Elara",
"Ananke", "Carme", "Pasiphae", "Sinope"
};
int namesLen = names.length;
Stack moons = new Stack ();
for (int i=0; i < namesLen-1; i++) {
moons.push (names[i]);
}
// Vector methods still work
moons.addElement (names[namesLen-1]);
while (!moons.empty()) {
System.out.print (moons.pop() + " ");
}
System.out.println();
}
}
Running the program generates the following output:
Sinope Pasiphae Carme Ananke Elara Lysithea
Himalia Leda Callisto Ganymede Europa Io Thebe
Amalthea Adrastea Metis
Stepping through Enumerations
While the Vector
and Stack
classes have natural
orderings, there are times when you don't really care about the actual
order a collection is traversed, only that every node is visited. Or,
you may only care that you have a collection of objects, not what the
underlying data structure is. This allows you to think at a higher level
during your application's design. For instance, there may come a time
when a vector is inefficient because you need frequent additions in the
middle of a collection. If that time comes, you shouldn't need to change
everything just because you want to use a LinkedList
(found
in Java 1.2) instead of a Vector
. The appropriate Java 1.1
interface that offers that level of abstraction is Enumeration
,
defined here:
public interface Enumeration
{
public abstract boolean hasMoreElements();
public abstract Object nextElement();
}
NOTE:
The Gamma, et al., Design Patterns book (Addison Wesley,
ISBN 0-201-63361-2) describes this pattern as an Iterator
.
In Java 1.2, Iterator is the actual interface name used to
represent the behavior.
The Enumeration
interface requires any collection-oriented
class to implement two methods: hasMoreElements()
and
nextElement()
. These two methods mean that any object
that supports enumerating its components can be explored using the
following while
loop:
Enumeration enum =
someContainer.methodReturningEnumeration();
while (enum.hasMoreElements()) {
Object obj = enum.nextElement();
// process this object
}
When working with Vector
, you get the set of elements
with the elements()
method. Since Stack
is a subclass of Vector
, you use elements()
there, too. Now, instead of the following block of code from the earlier
example:
Planet p;
for (int i=0, n=planets.size(); i < n; i++) {
p = (Planet)(planets.elementAt (i));
System.out.println (
p.getName() + " : " + p.getMoonCount());
}
you would walk through the planets
enumeration with this code:
Enumeration enum = planets.elements();
Planet p;
while (enum.hasMoreElements()) {
p = (Planet)(enum.nextElement());
System.out.println (
p.getName() + " : " + p.getMoonCount());
}
When creating your own types of collections, you need to implement the
two methods of Enumeration
interface. The following program
demonstrates this by converting any array into an Enumeration
;
just pass your array to
ArrayEnumerationFactory.makeEnumeration()
and you're all set.
import java.lang.reflect.Array;
import java.util.Enumeration;
final public class ArrayEnumerationFactory {
static public Enumeration makeEnumeration (
final Object obj) {
Class type = obj.getClass();
if (!type.isArray()) {
throw new IllegalArgumentException (
obj.getClass().toString ());
} else {
return (new Enumeration() {
int size = Array.getLength(obj);
int cursor;
public boolean hasMoreElements() {
return (cursor<size);
}
public Object nextElement() {
return Array.get (obj, cursor++);
}
});
}
}
public static void main (String args[]) {
Enumeration enum = makeEnumeration (args);
while (enum.hasMoreElements()) {
System.out.println (enum.nextElement());
}
enum = makeEnumeration (new int[] {1, 3, 4, 5});
while (enum.hasMoreElements()) {
System.out.println (enum.nextElement());
}
try {
enum = makeEnumeration (new Double(Math.PI));
} catch (IllegalArgumentException e) {
System.err.println (
"Can't enumerate that: " + e.getMessage());
}
}
}
The class includes a sample test run in the main()
method.
Running the program with the following input:
java ArrayEnumerationFactory one two three
produces the following output:
one
two
three
1
3
4
5
Can't enumerate that: class java.lang.Double
Dictionaries, Hashtables, and Properties
While arrays, vectors, and stacks provide ordered access to your
collections' contents, maintaining that order can be costly. To provide an
alternative collection methodology where order or sequential access isn't
necessary, Java provides support for key-value pair collections. Instead
of looking up elements by an integer position, you provide a key for every
value you would like to place in your collection, like a lookup map.
Figure 17.1 shows an example of this lookup scheme.
The abstract class to support this concept in the historical
collections group is Dictionary
. Hashtable
and Properties
provide two specific implementations of
these capabilities.
Figure 17.1:
Dictionary
lookup example
 |
Thumbing through Dictionaries
The abstract Dictionary
class describes the interface for
working with key-value maps. The way a dictionary works is if you provide
an object as a key, it will return at most one object as its value from
the collection. If the key isn't in the map, you get nothing back, or
null
in Java terms. The same object can be the value for
multiple keys. However, the key can only be the handle for one value
term. How the actual key-value pairs are stored is dependent on the
specific implementation. The abstract Dictionary
definition
follows:
public abstract class Dictionary {
public Dictionary();
public abstract Enumeration elements();
public abstract Object get(Object);
public abstract boolean isEmpty();
public abstract Enumeration keys();
public abstract Object put(Object, Object);
public abstract Object remove(Object);
public abstract int size();
}
NOTE:
Technically speaking, Dictionary
should be an interface as all
the methods are abstract. Apparently, Dictionary
predates the
concept of interfaces within Java, so it is just an abstract class. Since
Dictionary
is one of those historical collection classes,
you should really use the Map
interface, introduced in Java
1.2, when working with key-value collections.
Living with Hashtables
The Hashtable
class represents a concrete implementation
of the Dictionary
architecture, shown here:
public class Hashtable extends Dictionary
implements Map, Cloneable, Serializable {
public Hashtable();
public Hashtable(int initialCapacity);
public Hashtable(
int initialCapacity, float loadFactor);
public Hashtable(Map m);
public synchronized void clear();
public synchronized Object clone();
public synchronized boolean contains(Object value);
public synchronized boolean containsKey(Object key);
public boolean containsValue(Object value);
public synchronized Enumeration elements();
public Set entrySet();
public synchronized boolean equals(Object obj);
public synchronized Object get(Object key);
public synchronized int hashCode();
public boolean isEmpty();
public Set keySet();
public synchronized Enumeration keys();
public synchronized Object put(
Object key, Object value);
public synchronized void putAll(Map m);
protected void rehash();
public synchronized Object remove(Object key);
public int size();
public synchronized String toString();
public Collection values();
}
The class name is so called because of the means of storing the keys.
When you provide the key for a value to the hashtable, the data structure
generates a hash code and uses that as the means to look up the value when
it is necessary to retrieve it. As long as the algorithm for generating
the hash codes always generates the same value for the same key (two keys
are equivalent if equals()
says so) and distributes the codes
as evenly as possible, the hashtable represents an efficient means of storing
key-value pairs. The means of generating a key's hash code is by the
hashCode()
method, either the one from Object
,
or an overridden version from a subclass.
NOTE:
Two entries are not necessarily equal if hashCode()
returns the same value. In fact, if many entries result in the
same hash code value, this is usually the result of a poor hashing
algorithm. If you've overridden the hashCode()
method,
you should redesign how you generate hash codes for instances of
your class. For instance, the length of a String
is a bad hashing algorithm, as many unequal strings would have the
same code.
The operations you can do with a Hashtable
are mostly
inherited from Dictionary
(or part of the new
Map
interface).
- Adding a key-value pair is done with
put (Object key, Object value)
- Getting a value for a key is done with
get (Object key)
- Removing an element is done with
remove (Object key)
- Checking the size is done with
size()
- Checking if the size is 0 is done with
empty()
- Getting the set of all keys or values is done with
keys()
or elements()
, which both return
an Enumeration
- Getting the set of all keys or values for use with the
newer Collections API is done with
keySet()
or
entrySet()
, which both return a Set
Additionally, Hashtable
allows you to empty out the
collection with clear()
, check if a specific key is
present with containsKey (Object key)
, or even check
if a value is present with containsValue (Object value)
.
The last operation, while possible, is very expensive since a hashtable
is being used backwards.
Using the planet names as the keys and the planet diameter (in kilometers)
as the values, the following demonstrates the use of Hashtable
:
import java.util.Enumeration;
import java.util.Hashtable;
public class PlanetDiameters {
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", "Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto"};
float diameters[] = {4800f, 12103.6f, 12756.3f,
6794f, 142984f, 120536f, 51118f, 49532f, 2274f};
Hashtable hash = new Hashtable();
for (int i=0, n=names.length; i < n; i++) {
hash.put (names[i], new Float (diameters[i]));
}
Enumeration enum = hash.keys();
Object obj;
while (enum.hasMoreElements()) {
obj = enum.nextElement();
System.out.println (
obj + ": " + hash.get(obj));
}
}
}
Running the program produces the following results:
Earth: 12756.3
Mercury: 4800.0
Uranus: 51118.0
Pluto: 2274.0
Saturn: 120536.0
Jupiter: 142984.0
Neptune: 49532.0
Venus: 12103.6
Mars: 6794.0
Notice that the resulting order has absolutely no correlation to the
order the elements were added. Also, like with Vector
,
the get()
routine returns an Object
. If
you need to call a method of the specific class that was added into
the table, you have to cast the value returned to the appropriate class.
Examining Properties
When the objects to store in your hashtable are strings, you should
consider using the Properties
class. Instead of having
to cast return values to the String
class, the
Properties
class does this for you with its
supporting methods:
public class Properties extends Hashtable {
protected Properties defaults;
public Properties();
public Properties(Properties defaults);
public String getProperty(String key);
public String getProperty(
String key,
String defaultValue);
public void list(PrintStream out);
public void list(PrintWriter out);
public synchronized void load(InputStream in)
throws IOException;
public Enumeration propertyNames();
public synchronized Object put(
Object key,
Object value);
public synchronized Object setProperty(
String key,
String value);
public synchronized void store(
OutputStream out,
String header)
throws IOExcepition
}
Since Properties
is a Dictionary
subclass,
you can continue to add entries with put()
and retrieve
entries with get()
. However, these methods work with
Object
values. The more natural way to work with the
Properties
class is with the following methods:
- Adding a key-value String pair is done with
setProperty
(String key, String value)
.
- Getting a value for a key is done with
getProperty(String key)
or getProperty(String key, String defaultValue)
, for when
key is not set.
- Getting the set of all keys is done with
propertyNames()
instead of keys()
. Properties
can have default
values. Using propertyNames()
creates an Enumeration
that is the union of the keys()
and the default values.
Besides the convenience methods, you can also load properties from an
input stream, like a file, or save them, with load()
and
store()
respectively. (The save()
method was
deprecated because it didn't throw an IOException
when there
were problems saving.) The way property settings are specified in a
text file is separated by an equal sign (=
).
If the file planet.properties
contained the following values:
Mercury=god of commerce, travel and thievery
Venus=goddess of love and beauty
Earth=not derived from Greek/Roman mythology
Mars=god of War
Jupiter=King of the Gods
Saturn=god of agriculture
Uranus=deity of the Heavens
Neptune=god of the Sea
Pluto=god of the underworld
you would have nine properties, one for each planet name. The
following program would then load the file, add a new property for
a fictitious 10th planet, save
the properties to a new file, list all properties and values to
standard output, and finally locate a specific one:
import java.io.*;
import java.util.Properties;
public class PlanetProperties {
public static void main (
String args[]) throws IOException {
String header = "A header";
Properties props = new Properties();
props.load (new FileInputStream (
"planets.properties"));
props.setProperty ("Planet X", "god of dreams");
props.store (new FileOutputStream (
"save.the.planets"), header);
props.list (System.out);
System.out.println (props.getProperty ("Pluto"));
}
}
The most common use of Properties
is with a list of system
properties. If you ask the System
class for its list of
properties (getProperties()
), you can find out information
like the version of Java the person running the program is using, the URL
of where to send bug reports for that specific version of Java, and even
what directory to store temporary files in. Just add
System.getProperties().list (System.out);
to the previous
program to see.
Bit Sets
Class BitSet
implements a set of bits or a vector of boolean
values. Unlike many of the other bit set classes or language features in
other languages, this bit set has no limits. You can therefore go way
beyond the typical 32- or 256-bit limits imposed by other implementations.
First, let's look at the class definition:
public class BitSet
implements Cloneable, Serializable {
public BitSet();
public BitSet(int nbits);
public void and(BitSet set);
public void andNot(BitSet set);
public void clear(int bitIndex);
public Object clone();
public boolean equals(Object obj);
public boolean get(int bitIndex);
public int hashCode();
public int length();
public void or(BitSet set);
public void set(int bitIndex);
public int size();
public String toString ();
public void xor(BitSet set);
}
BitSet
operations include the following:
- Setting, clearing, and getting single bits
- Anding, and notting, oring, and xoring bit sets together
- Comparing bit sets
The following program demonstrates their usage, by placing in a
BitSet
whether or not a planet has an even number of
moons. Normally, you would store much larger groups of bits in a
BitSet
to truly save space:
import java.util.*;
public class TwoBitPlanets {
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", "Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto"};
int moons[] = {0, 0, 1, 2, 16, 18, 17, 8, 1};
int namesLen = names.length;
BitSet bits = new BitSet(namesLen);
for (int i=0; i < namesLen; i++) {
if ((moons[i] % 2) == 0) {
bits.set (i);
}
}
for (int i=0; i < namesLen; i++) {
System.out.println (
names[i] + " Even # Moons? " + bits.get(i));
}
}
}
NOTE:
Although BitSet
is part of the historical collection
classes, the new Collections framework has no replacement. Also,
the size()
method of BitSet
returns the
size of the internal structure used, not necessarily the maximum bit
number utilized. Since the bit values are stored with the help of a
double, size()
jumps up by 64 when necessary. More
frequently you want the length()
method, which returns
the highest set bit position.
Collections and Iterators
The world of Java collection classes was overturned in Java 1.2. A set
of about 25 classes was added to the java.util
package to
define the Java Collections API. Figure 17.2 shows the class hierarchy
diagram showing the makeup of this framework.
Figure 17.2: The Collections Framework Class Hierarchy diagram
 |
As the diagram shows, the four interfaces, Collection
,
List
, Map
, and Set
, describe
the different types of collections. For each type of collection,
there are specific implementations, depending upon the type of data
structure used to store the collection. These are the classes like
ArrayList
, TreeSet
, and HashMap
.
The remaining classes in the hierarchy are support related. For instance,
the Iterator
interface replaces the Enumeration
interface from the historical collection classes.
When working with the various framework classes, you always have to
create specific implementations of the data structures, as the system needs
to know how to store objects within the collection. However, when you
access the actual collection, you should use the interface methods. This
allows you to change data structures, for instance, from an array-backed
collection to a hashtable-backed one, if the circumstances require it.
Then, since the collection class still implements the same collection
interface, no other code will need to change. For instance, the following
shows how you would create a HashMap
:
Map phoneBook = new HashMap();
If later you decide to maintain a sorted phone book, you can change the
data structure from a HashMap
to a TreeMap
:
Map phoneBook = new TreeMap ();
Since you only accessed the phoneBook
variable through the
Map
interface, the rest of your code would stay the same,
and your phone list will always be sorted.
Of the four primary interfaces, Collection
and Map
are the basic two. A Collection
is any group of objects, while
Map
is like Dictionary
and works with key-value
pairs. Two interfaces extend Collection
: Set
and
List
. A Set
behaves like its mathematical
definition: no duplicates; while List
preserves a sequence or
ordering, similar to Vector
's behavior. The SortedMap
and SortedSet
interfaces offer sorted
traversal through the elements of Map
and Set
respectively.
To get started with the new API, let's look at the Collection
interface definition:
public interface Collection {
public abstract boolean add(Object obj);
public abstract boolean addAll(Collection c);
public abstract void clear();
public abstract boolean contains(Object obj);
public abstract boolean containsAll(Collection c);
public abstract boolean equals(Object obj);
public abstract int hashCode();
public abstract boolean isEmpty();
public abstract Iterator iterator();
public abstract boolean remove(Object obj);
public abstract boolean removeAll(Collection c);
public abstract boolean retainAll(Collection c);
public abstract int size();
public abstract Object[] toArray();
public abstract Object[] toArray(Object obj[]);
}
Collection
operations include the following:
- Adding elements
- Removing elements
- Checking the contents
- Working with the elements
Most of the operations are self-explanatory. However, a couple deserve
a little explanation. The retainAll()
method combines two
collections by performing the set theory intersection operation. The
original collection is modified to include any elements in the
Collection
parameter that are not already members of the
collection. The toArray()
method allows you to convert a
Collection
into an array. This may be necessary for historical
purposes, where you need to send a set of data to another program that
doesn't work with the collection classes yet. The following program
demonstrates the capabilities of the Collection
interface,
using the soon-to-be-described ArrayList
class as the data
structure:
import java.util.*;
public class PlanetSet {
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", "Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto"};
int namesLen = names.length;
Collection planets = new ArrayList();
for (int i=0; i < namesLen; i++) {
planets.add (names[i]);
}
Object s[] = planets.toArray();
String s[] = (
String [])planets.toArray(new String [0]);
for (int i=0, n=s.length; i < n; i++) {
System.out.println (s[i]);
}
planets.remove (names[3]);
System.out.println (
names[1] +
" " +
planets.contains (names[1]));
System.out.println (
names[3] +
" " +
planets.contains (names[3]));
}
}
In order to access each element of the collection, the toArray()
method was used. While this works perfectly well, the more appropriate way
to do this is with the Iterator
interface. This interface,
defined here, replaces the Enumeration
interface from the
historical collection classes:
public interface Iterator {
public abstract boolean hasNext();
public abstract Object next();
public abstract void remove();
}
As with Enumeration
, you can have a similar while
loop to get through all the elements. Thankfully, the method names are a
little nicer and a remove()
method has been added. The new
remove()
method is actually an optional interface method,
though. Yes, this sounds contradictory — an optional interface
method — but it actually is the truth. When a collection doesn't
support removing entries during iteration, or ever, the method will throw
the new exception UnsupportedOperationException
.
WARNING:
This is not the only place you will see
UnsupportedOperationException
possibly thrown.
Various modification methods of the collection classes are
considered optional and will throw this exception. While this
is a RuntimeException
, programmatically trying to
perform an unsupported operation is a programming error that
should be encountered, and corrected, before a program reaches
real users.
In the previous example, you can print the contents of every element of
the collection with the following code:
Iterator it = planets.iterator();
while (it.hasNext()) {
System.out.println (it.next());
}
Now that we've described the top-level collection framework, let's take
a look at some of the concrete implementations.
The Generic Collection Library
ObjectSpace offers a Java package called the
Generic Collection Library for Java (JGL). (The acronym comes
from a prior name that infringed on Sun's Java trademark.)
For any developer transitioning from C++, JGL offers a set of
collection classes that is consistent with the C++ Standard
Template Library (STL). Prior to the 1.2 JDK, it was probably
the best collections-oriented package available, and many IDE
vendors licensed it for inclusion with their tools.
However, although similarities to the STL were JGL's strong
selling points, it required a large framework for support.
The Java Collections API introduced in the 1.2 JDK is much
smaller in size and appears, conceptually, to be easier to
understand.
For more information on the JGL package, stop by its Web site at
http://www.objectspace.com .
|
Sets
As previously mentioned, a set is a collection with no
duplicates. Since this doesn't add any new behavior, only adding
stipulations to existing behavior, the Set
interface is
identical to the Collection
interface. To avoid duplication,
adding elements to a set relies on the equals()
method
of the element being added to establish the uniqueness of the object.
There are two specific types of sets with which you can work. The
recommended general-purpose Set
data structure is
HashSet
. A HashSet
is a Set
collection backed by a hashtable. Like the Hashtable
class, elements added to the hashtable need to implement the
hashCode()
method.
The other set structure is good under specific circumstances. The
TreeSet
is the other available Set
implementation.
As the name implies, it is backed by a (balanced) tree data structure.
If ordering is important, then TreeSet
is the set collection
of choice. The TreeSet
class relies on the methods in the
SortedSet
interface, shown here, when examining the tree
in an ordered fashion:
public interface SortedSet extends Set {
public abstract Comparator comparator();
public abstract Object first();
public abstract SortedSet
headSet(Object toElement);
public abstract Object last();
public abstract SortedSet subSet(
Object fromElement,
Object toElement);
public abstract SortedSet tailSet(
Object fromElement);
}
The following program demonstrates using the Set
interface.
The primary goal here is to show that duplicates are not added to the set:
import java.util.*;
public class MoonSet {
public static void main (String args[]) {
String names[] = {"Metis", "Adrastea", "Amalthea",
"Thebe", "Io", "Europa", "Ganymede", "Callisto",
"Leda", "Himalia", "Lysithea", "Elara", "Ananke",
"Carme", "Pasiphae", "Sinope"
};
Set moons = new HashSet ();
int namesLen = names.length;
int index;
for (int i=0; i < 100; i++) {
index = (int)(Math.random()*namesLen);
moons.add (names[index]);
}
Iterator it = moons.iterator();
while (it.hasNext()) {
System.out.println (it.next());
}
}
}
Lists and ListIterator
The List
interface is your basic positional collection.
When you add elements to a list, you can add each at a specific position
or at the end. The following shows the interface's definition:
public interface List extends Collection {
public abstract void add(int index, Object element);
public abstract boolean add(Object obj);
public abstract boolean addAll(
int index, Collection c);
public abstract boolean addAll(Collection c);
public abstract void clear();
public abstract boolean contains(Object obj);
public abstract boolean containsAll(Collection c);
public abstract boolean equals(Object obj);
public abstract Object get(int index);
public abstract int hashCode();
public abstract int indexOf(Object obj);
public abstract boolean isEmpty();
public abstract Iterator iterator();
public abstract int lastIndexOf(Object obj);
public abstract ListIterator listIterator();
public abstract ListIterator listIterator(
int startPosition);
public abstract Object remove(int);
public abstract boolean remove(Object obj);
public abstract boolean removeAll(Collection c);
public abstract boolean retainAll(Collection c);
public abstract Object set(
int index, Object element);
public abstract int size();
public abstract subList(int fromIndex, int toIndex);
public abstract Object[] toArray();
}
There are two specific implementations of List
in the
Collections framework: ArrayList
and LinkedList
.
An ArrayList
is similar in functionality to a Vector
— both maintain the collection within a resizable array. When
maintaining List
-type collections, you will probably maintain
them in an ArrayList
. The downfall of ArrayList
is if you must do frequent inserts and removals in the middle of the list,
which is where LinkedList
shines. LinkedList
is a doubly linked list, with references to the previous and next elements
at each node. Because of this linkage, sequential access is satisfactory,
but random access is slow, relative to an ArrayList
.
Class ArrayList
provides two methods and three constructors,
in addition to the List
interface methods. In addition,
ArrayList
implements the Cloneable
interface:
public ArrayList();
public ArrayList(int initialCapacity);
public ArrayList(Collection c);
public Object clone();
public void ensureCapacity(int minCapacity);
public void trimToSize();
The LinkedList
class has its own set of constructors and
methods to add, as well as also implementing Cloneable
:
public LinkedList();
public LinkedList(Collection c);
public void addFirst(Object obj);
public void addLast(Object obj);
public Object clone();
public Object getFirst();
public Object getLast();
public Object removeFirst();
public Object removeLast();
If you desire a stack data structure, you can use LinkedList
and add elements with addFirst()
and remove them with
removeFirst()
. For a first-in-first-out (FIFO) queue, you would
add with addLast()
and remove with removeFirst();
the reverse is also possible, addFirst()/removeLast();
however, it seems more natural to add to the end and remove from the
beginning.
The following example revisits the planets
and moon count
example from the previous Vector
example, listing the
planets
in reverse order:
import java.util.*;
public class PlanetsAndMoonsList {
static class Planet {
private String name;
private int moonCount;
Planet (String s, int moons) {
name = s;
moonCount = moons;
}
public String toString () {
return getClass().getName() +
"[" + name + "-" + moonCount + "]";
}
public final String getName() {
return name;
}
public final int getMoonCount () {
return moonCount;
}
}
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", "Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto"};
int moons[] = {0, 0, 1, 2, 16, 18, 17, 8, 1};
int namesLen = names.length;
List planets = new ArrayList (namesLen);
for (int i=0; i < namesLen; i++) {
planets.add (new Planet (names[i], moons[i]));
}
for (int i=planets.size()-1; i >= 0; --i) {
Planet p = (Planet)(planets.get (i));
System.out.println (p.getName() +
" : " + p.getMoonCount());
}
}
}
Working with ListIterator
While the Iterator
interface is available for every
Collection
, those collections that also implement the
List
interface have the ListIterator
interface
available to them, as well. Instead of just providing uni-directional
traversal of a collection, with possible removal of elements,
ListIterator
is bi-directional, with possible removal,
replacement, and addition of elements. Here is its definition:
public interface ListIterator Iterator {
public abstract void add(Object obj);
public abstract boolean hasNext();
public abstract boolean hasPrevious();
public abstract Object next();
public abstract int nextIndex();
public abstract Object previous();
public abstract int previousIndex();
public abstract void remove();
public abstract void set(Object obj);
}
The following program demonstrates the interface by rearranging the
solar system:
import java.util.*;
public class MovingPlanets {
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", "Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto"};
int namesLen = names.length;
List planets = new ArrayList();
for (int i=0; i < namesLen; i++) {
planets.add (names[i]);
}
ListIterator lit = planets.listIterator();
String s;
lit.next();
lit.next();
s = (String )lit.next();
lit.remove();
lit.next();
lit.next();
lit.next();
lit.add(s);
lit.next(); // Gets back just added
lit.previous();
lit.previous();
s = (String )lit.previous();
lit.remove();
lit.next();
lit.next();
lit.add(s);
Iterator it = planets.iterator();
while (it.hasNext()) {
System.out.println (it.next());
}
}
}
The output from running this program follows:
Mercury
Venus
Mars
Saturn
Earth
Jupiter
Uranus
Neptune
Pluto
TIP:
If next()
or previous()
went past an end
of the List
, NoSuchElementException
would
be thrown.
Maps
Like a Dictionary
or phone book, a Map
is used
to maintain key-value pair collections. Every entry in the collection is
added by providing a value and the key to look it up. If someone asks you
for Joe's phone number, and you don't know his number, you look it up in a
phone book. The key here is "Joe," and the value is his phone number.
The actual definition of the Map
interface follows:
public interface Map {
public abstract void clear();
public abstract boolean containsKey(Object key);
public abstract boolean containsValue(Object value);
public abstract Set entrySet();
public abstract boolean equals(Object obj);
public abstract Object get(Object key);
public abstract int hashCode();
public abstract boolean isEmpty();
public abstract Set keySet();
public abstract Object put(
Object key, Object value);
public abstract void putAll(Map m);
public abstract Object remove(Object key);
public abstract int size();
public abstract Collection values();
}
Besides adding entries and looking up values, you can work with
three collections of the Map
: the set of keys
(keySet()
), the collection of values (values()
),
and a set of both (entrySet()
). If you ask for both,
each element of the collection is an instance of the Map.Entry
inner-interface, defined here:
public static interface Map.Entry {
public abstract boolean equals(Object obj);
public abstract Object getKey();
public abstract Object getValue();
public abstract int hashCode();
public abstract Object setValue(Object value);
}
Three concrete implementations of Map
are provided with the collection
classes: HashMap, WeakHashMap, and TreeMap. HashMap
serves as your
general-purpose map, backed by a hashtable. WeakHashMap
is your map backed
by a hashtable with weak references; if you do not retain a reference to a
key outside the map, the garbage collector can free it.
NOTE:
Examine the java.lang.ref.WeakReference class and
http://java.sun.com/products/jdk/1.2/docs/guide/refobs/
for more information about weak references.
TreeMap
is your map backed by a balanced tree. When looking
at its keys or values, these collections will be sorted. If sorting is a
must, but you don't want the cost associated with adding a node, you can
sort a HashMap
after all the nodes have been added, when you
truly need to get the results sorted:
Map map = new HashMap()
// add entries
map = new TreeMap (map);
The following example converts the earlier planet-diameter example to
use a TreeMap
:
import java.util.*;
public class DiameterMap {
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", "Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto"};
float diameters[] = {4800f, 12103.6f, 12756.3f,
6794f, 142984f, 120536f, 51118f, 49532f, 2274f};
Map map = new TreeMap();
for (int i=0, n=names.length; i < n; i++) {
map.put (names[i],
new Float (diameters[i]));
}
Iterator it = map.keySet().iterator();
Object obj;
while (it.hasNext()) {
obj = it.next();
System.out.println (obj + ": " + map.get(obj));
}
}
}
Now, the output will appear in sorted planet name (key) order:
Earth: 12756.3
Jupiter: 142984.0
Mars: 6794.0
Mercury: 4800.0
Neptune: 49532.0
Pluto: 2274.0
Saturn: 120536.0
Uranus: 51118.0
Venus: 12103.6
TreeMap
is the only map that allows you to get a submap:
headMap(Object toKey)
returns a map of everything less than key,
tailMap(Object fromKey)
returns a map of everything greater than
key, while subMap(Object fromKey, Object toKey)
returns a map
within a certain range. These are all part of the SortedMap
interface, described here:
public interface SortedMap extends Map {
public abstract Comparator comparator();
public abstract Object firstKey();
public abstract SortedMap headMap(Object toKey);
public abstract Object lastKey();
public abstract SortedMap subMap(
Object fromKey,
Object toKey);
public abstract SortedMap tailMap(Object toKey);
}
Synchronization and Readability
If you've used the historical collection classes of Java, you know that
one of their biggest problems is performance. It's not that they were
designed to be slow; they were designed to always be thread-safe.
That means if you have multiple running threads accessing a single data
structure, all access to the data structure is safe and synchronized
appropriately. This is great when you have multiple running threads
accessing a single data structure. However, when you do not require the
synchronized behavior, there is no way to turn it off. All usage of
classes like Hashtable
and Vector
are synchronized.
The collection classes added with Java 1.2 take another route. Instead
of synchronizing everything, they synchronize nothing. If you need the
synchronized behavior, after you have a collection to work with, you ask
the Collections
class to make it synchronized. Defined here, the
Collections
class provides this and other behavior to be described shortly.
Since all the methods of Collections
are static, and the constructor is
private, you do not need to, nor can you, create any instances of the
class:
public class Collections {
public static final List EMPTY_LIST;
public static final Set EMPTY_SET;
public static int binarySearch(
List list, Object key);
public static int binarySearch(
List list,
Object key,
Comparator comp);
public static void copy(List to, List from);
public static Enumeration enumeration(
Collection coll);
public static void fill(List list, Object o);
public static Object max(Collection coll);
public static Object max(
Collection coll,
Comparator comp);
public static Object min(Collection coll);
public static Object min(
Collection coll,
Comparator comp);
public static List nCopies(int count, Object obj);
public static void reverse(List list);
public static Comparator reverseOrder();
public static void shuffle(List list);
public static void shuffle(List list, Random r);
public static Set singleton(Object o);
public static void sort(List list);
public static void sort(List list, Comparator comp);
public static Collection synchronizedCollection(
Collection coll);
public static List synchronizedList(List list);
public static Map synchronizedMap(Map map);
public static Set synchronizedSet(Set set);
public static SortedMap synchronizedSortedMap(
SortedMap map);
public static SortedSet synchronizedSortedSet(
SortedSet set);
public static Collection unmodifiableCollection(
Collection coll);
public static List unmodifiableList(List list);
public static Map unmodifiableMap(Map map);
public static Set unmodi
unmodifiableSortedMap(SortedMap);
public static SortedSet
unmodifiableSortedSet(SortedSet);
}
For instance, to synchronize access to a Map
, you would do the
following:
Map map = new HashMap()
map = Collections.synchronizedMap (map);
// access map from multiple threads
TIP:
When you synchronize a collection, it is good practice
to not store the new collection in a new variable. If
you do, it is possible you could still access the collection
unsynchronized from the old one.
Besides synchronization, the Collections
class also offers
the ability to convert a specific collection to read-only mode. What this
does is cause any method that would alter the collection to throw an
UnsupportedOperationException
. So, to make a collection
read-only, you create it, fill it up, and then make it unmodifiable.
If you make it unmodifiable before filling it up, you get an
UnsupportedOperationException thrown
:
Map map = new HashMap()
// add entries
map = Collections.unmodifiableMap (map);
Algorithms and Sorting
The Java Collections API includes many algorithmic capabilities
behind the scenes. For instance, up to this point, when various balanced
tree-oriented collections were mentioned, how the tree was sorted was not.
The time has come to describe this behavior and other similar capabilities.
For random sorting or reordering of a List
, just use
Collections.shuffle()
.
Comparable and Comparator
Two interfaces are available to support sorting. The
Comparable
interface is for when a class has a natural
ordering. Given many objects of the same type, the interface allows
one to order all of them. The interface definition for
Comparable
is:
public interface Comparable {
public abstract int compareTo(Object obj);
}
A negative return value signals the instance of the interface implementer
comes before the parameter, zero signifies both are equal, and a positive
value means the parameter comes first. When a class implements the
Comparable
interface, objects of the class can be used as the
key for a tree-oriented collection. If an object doesn't implement
Comparable
, but you still wish it to be a key, you can
implement the Comparator
interface and have it do the
comparisons for you:
public interface Comparator {
public abstract int compare (
Object obj1, Object obj2);
}
NOTE:
The Java 1.2 classes that implement the Comparable
interface
are: BigDecimal
, BigInteger
, Byte
,
Character
, CollationKey
, Date
,
Double
, File
, Float
,
Integer
, Long
, ObjectStreamField
,
Short
, String
, and URL
.
To demonstrate, let's compare the results of sorting with the default
String
comparison and a comparator that doesn't distinguish
between uppercase and lowercase characters. To help, we need the
Arrays
class, shown here:
public class Arrays {
public static List asList(Object array[]);
public static int binarySearch(byte a[], byte key);
public static int binarySearch(char a[], char key);
public static int binarySearch(
double a[], double key);
public static int binarySearch(float a[], float key);
public static int binarySearch(int a[], int key);
public static int binarySearch(
Object a[], Object key);
public static int binarySearch(
Object a[],
Object key,
Comparator comp);
public static int binarySearch(long a[], long key);
public static int binarySearch(short a[], short key);
public static boolean equals(
boolean[], boolean a2[]);
public static boolean equals(byte a1[], byte a2[]);
public static boolean equals(char a1[], char a2[]);
public static boolean equals(
double a1[], double a2[]);
public static boolean equals(float a1[], float a2[]);
public static boolean equals(int a1[], int a2[]);
public static boolean equals(
Object a1[], Object a2[]);
public static boolean equals(long a1[], long a2[]);
public static boolean equals(short a1[], short a2[]);
public static void fill(boolean a[], boolean val);
public static void fill(
boolean a[],
int from,
int to,
boolean val);
public static void fill(byte a[], byte val);
public static void fill(
byte a[],
int from,
int to,
byte val);
public static void fill(char a[], char val);
public static void fill(
char a[],
int from,
int to,
char val);
public static void fill(double a[], double val);
public static void fill(
double a[],
int from,
int to,
double val);
public static void fill(float a[], float val);
public static void fill(
float a[],
int from,
int to,
float val);
public static void fill(int a[], int val);
public static void fill(
int a[],
int from,
int to,
int val);
public static void fill(
Object a[],
int from,
int to,
Object val);
public static void fill(Object a[], Object val);
public static void fill(
long a[],
int from,
int to,
long val);
public static void fill(long a[], long val);
public static void fill(
short a[],
int from,
int to,
short val);
public static void fill(short a[], short val);
public static void sort(byte a[]);
public static void sort(char a[]);
public static void sort(double a[]);
public static void sort(float a[]);
public static void sort(int a[]);
public static void sort(Object a[]);
public static void sort(
Object a[],
Comparator comp);
public static void sort(long a[]);
public static void sort(short a[]);
}
The Arrays
class is like Collections
, all
static methods and no constructor, just a collection of utilities for
working with arrays.
The Arrays
class provides a sort()
method for
sorting any array. Once an array is sorted, you could also perform a quick
binary search to find an element in the array. For the following example,
the program sorts a list of names with the default String
Comparable
interface, then sorts with the case-insensitive
Comparator
one:
import java.util.*;
public class SortingPlanets {
static class InsensitiveComp implements Comparator {
public int compare (Object a1, Object a2) {
String s1 = a1.toString ().toLowerCase();
String s2 = a2.toString ().toLowerCase();
return s1.compareTo (s2);
}
}
public static void main (String args[]) {
String names[] = {"Mercury", "Venus", "Earth",
"Mars", "Jupiter", "Saturn", "Uranus",
"Neptune", "Pluto",
"mercury", "venus", "earth",
"mars", "jupiter", "saturn", "uranus",
"neptune", "pluto"
};
Arrays.sort(names);
int namesLen = names.length;
for (int i=0; i<namesLen; i++) {
System.out.print (names[i] + " ");
}
System.out.println ();
Arrays.sort(names, new InsensitiveComp());
for (int i=0; i<namesLen; i++) {
System.out.print (names[i] + " ");
}
System.out.println ();
}
}
Running the program produces the following output. Notice how the
second run through ignores case:
Earth Jupiter Mars Mercury Neptune Pluto Saturn
Uranus Venus earth jupiter mars mercury neptune
pluto saturn uranus venus
Earth earth Jupiter jupiter Mars mars Mercury
mercury neptune Neptune pluto Pluto Saturn
saturn Uranus uranus Venus venus
WARNING:
If you perform a binarySearch()
on an array,
remember to sort()
first. If you don't,
undefined behavior occurs, including the possibility of an
infinite loop.
TIP:
To sort an object array in reverse order, use
Arrays.sort(anObjectArray, Collections.reverseOrder())
.
Miscellaneous Utilities
Besides sorting and searching with Arrays
and
Collections
, you can use Collections
to find
the minimum and maximum values of your Collection
. Unlike
when you use binarySearch()
, you do not have to
sort()
your collection beforehand. Just use the
min()
and max()
methods of
Collections
, which take an optional Comparator
.
Going between old and new style collections is relatively easy, too.
To create an Enumeration
from any Collection
,
just use Collections.enumeration()
. To go from an array
to a List
, use Arrays.asList()
.
Summary
Working with data structures in Java has many options, all depending
upon your specific needs. While Java 1.2 introduces the Java Collections
API, the historical collection classes are still available and readily used
with all the code out there. Knowing about arrays, Vector
,
Dictionary
, Hashtable
, Properties
,
and BitSet
will help you with Java 1.0 and 1.1 code.
Understanding Collection
, Set, List, and Map, along with
all their implementations, will put you well on your way to success
with the new Collections framework of 1.2. Where possible, using only
the 1.2 collection classes (and arrays) is the way to go.
About the Author
John Zukowski is a Software Mage with MageLang Institute. In addition to
being the author of Mastering Java 1.2, Java AWT Reference,
and Borland JBuilder: No Experience Required. John also serves as
the Focus on Java Guide
at The Mining Co.
Reader Feedback
Tell us what you think of this book excerpt.