Types of collections

The

standard Java 1.0

and 1.1 library comes with a bare minimum set of collection classes, but
they’re probably enough to get by with for many of your programming
projects. (As you’ll see at the end of this chapter, Java 1.2
provides a radically redesigned and filled-out library of collections.)

Vector
BitSet
Stack
Hashtable
Enumerators revisited

Vector

The

Vector

is quite simple to use, as you’ve seen so far. Although most of the time

you’ll just use

addElement( )

to insert objects,

elementAt( )

to get them out one at a time, and

elements( )

to get an

Enumeration

to the sequence, there’s also a set of other methods that can be useful.

As usual with the Java libraries, we won’t use or talk about them all

here, but be sure to look them up in the electronic documentation to get a feel

for what they can do.

Crashing
Java

The

Java standard collections contain a

toString( )

method so they can produce a

String

representation of themselves, including the objects they hold. Inside of

Vector

for example, the

toString( )

steps through the elements of the

Vector

and calls

toString( )

for each one. Suppose you’d like to print out the address of your class.

It seems to make sense to simply refer to

this

(in

particular, C++ programmers are prone to this approach):

//: CrashJava.java
// One way to crash Java
import java.util.*;
 
public class CrashJava {
  public String toString() {
    return "CrashJava address: " + this + "n";
  }
  public static void main(String[] args) {
    Vector v = new Vector();
    for(int i = 0; i &lt; 10; i++)
      v.addElement(new CrashJava());
    System.out.println(v);
  }
} ///:~

turns out that if you simply create a

CrashJava

object and print it out, you’ll get an endless sequence of exceptions.

However, if you place the

CrashJava

objects in a

Vector

and print out that

Vector

as shown here, it can’t handle it and you don’t even get an

exception; Java just crashes. (But at least it didn’t bring down my

operating system.) This was tested with Java 1.1

What’s

happening is automatic type conversion for

String

When you say:

"CrashJava address: " + this

The

compiler sees a

String

followed by a ‘

’

and

something

that’s not a

String

so it tries to convert

this

to a

String

It does this conversion by calling

toString( )

which produces a

recursive
call. When this occurs inside a
Vector,
it appears that the stack
overflows without the exception-handling mechanism getting a chance to respond.

you really do want to print the address of the object in this case, the

solution is to call the

Object
toString( )

method, which does just that. So instead of saying

this

you’d say

super.toString( )

(This only works if you

’

re directly inheriting from

Object

or if none of your parent classes have overridden the

toString( )

method).

BitSet

BitSet
is really a
Vector
of bits, and it is used if you want to efficiently store a lot of on-off
information. It’s efficient only from the standpoint of size; if
you’re looking for efficient access, it is slightly slower than using an
array of some native type.

addition, the minimum size of the

BitSet

is that of a long: 64 bits. This implies that if you’re storing anything

smaller, like 8 bits, a

BitSet

will be wasteful, so you’re better off creating your own class to hold

your flags.

a normal

Vector

the collection will expand as you add more elements. The

BitSet

does this as well – sort of. That is, sometimes it works and sometimes it

doesn’t, which makes it appear that the Java version 1.0 implementation of

BitSet

is just badly done. (It is fixed in Java 1.1.

)
The following example shows how the
BitSet
works
and demonstrates the version 1.0 bug:

//: Bits.java
// Demonstration of BitSet
import java.util.*;
 
public class Bits {
  public static void main(String[] args) {
    Random rand = new Random();
    // Take the LSB of nextInt():
    byte bt = (byte)rand.nextInt();
    BitSet bb = new BitSet();
    for(int i = 7; i &gt;=0; i--)
      if(((1 &lt;&lt; i) &amp;  bt) != 0)
        bb.set(i);
      else
        bb.clear(i);
    System.out.println("byte value: " + bt);
    printBitSet(bb);
 
    short st = (short)rand.nextInt();
    BitSet bs = new BitSet();
    for(int i = 15; i &gt;=0; i--)
      if(((1 &lt;&lt; i) &amp;  st) != 0)
        bs.set(i);
      else
        bs.clear(i);
    System.out.println("short value: " + st);
    printBitSet(bs);
 
    int it = rand.nextInt();
    BitSet bi = new BitSet();
    for(int i = 31; i &gt;=0; i--)
      if(((1 &lt;&lt; i) &amp;  it) != 0)
        bi.set(i);
      else
        bi.clear(i);
    System.out.println("int value: " + it);
    printBitSet(bi);
 
    // Test bitsets &gt;= 64 bits:
    BitSet b127 = new BitSet();
    b127.set(127);
    System.out.println("set bit 127: " + b127);
    BitSet b255 = new BitSet(65);
    b255.set(255);
    System.out.println("set bit 255: " + b255);
    BitSet b1023 = new BitSet(512);
// Without the following, an exception is thrown
// in the Java 1.0 implementation of BitSet:
//    b1023.set(1023);
    b1023.set(1024);
    System.out.println("set bit 1023: " + b1023);
  }
  static void printBitSet(BitSet b) {
    System.out.println("bits: " + b);
    String bbits = new String();
    for(int j = 0; j &lt; b.size() ; j++)
      bbits += (b.get(j) ? "1" : "0");
    System.out.println("bit pattern: " + bbits);
  }
} ///:~

The

random number generator is used to create a random

byte

short

and

int

and each one is transformed into a corresponding bit pattern in a

BitSet

This works fine because a

BitSet

is 64 bits, so none of these cause it to increase in size. But in Java 1.0

,
when the
BitSet
is greater than 64 bits, some strange behavior occurs. If you set a bit
that’s just one greater than the
BitSet’s
currently-allocated storage, it will expand nicely. But if you try to set bits
at higher locations than that without first just touching the boundary,
you’ll get an exception, since the
BitSet
won’t expand properly in Java 1.0. The example shows a
BitSet
of 512 bits being created. The constructor allocates storage for twice that
number of bits. Then if you try to set bit 1024 or greater without first
setting bit 1023, you’ll throw an exception in Java
1.0. Fortunately, this is fixed in Java 1.1,
but avoid using the
BitSet
if you write code for Java 1.0.

Stack

Stack
is sometimes referred to as a “last-in, first-out” (LIFO)
collection. That is, whatever you “push” on the
Stack
last is the first item you can “pop” out. Like all of the other
collections in Java, what you push and pop are
Objects,
so you must cast what you pop.

What’s

rather odd is that instead of using a

Vector
as a building block to create a
Stack,
Stack
is
inherited from
Vector.
So it has all of the characteristics and behaviors of a
Vector
plus
some extra
Stack
behaviors. It’s difficult to know whether the designers explicitly
decided that this was an especially useful way to do things, or whether it was
just a naïve design.

Here’s

a simple demonstration of

Stack

that reads each line from an array and pushes it as a

String

//: Stacks.java
// Demonstration of Stack Class
import java.util.*;
 
public class Stacks {
  static String[] months = {
    "January", "February", "March", "April",
    "May", "June", "July", "August", "September",
    "October", "November", "December" };
  public static void main(String[] args) {
    Stack stk = new Stack();
    for(int i = 0; i &lt; months.length; i++)
      stk.push(months[i] + " ");
    System.out.println("stk = " + stk);
    // Treating a stack as a Vector:
    stk.addElement("The last line");
    System.out.println(
      "element 5 = " + stk.elementAt(5));
    System.out.println("popping elements:");
    while(!stk.empty())
      System.out.println(stk.pop());
  }
} ///:~

Each

line in the

months

array

is inserted into the

Stack

with

push( )

and later fetched from the top of the stack with a

pop( )

To make a point,

Vector

operations

are also performed on the

Stack

object. This is possible because, by virtue of inheritance, a

Stack
is

Vector

Thus, all operations that can be performed on a

Vector

can also be performed on a

Stack

such as

elementAt( )

Hashtable

Vector

allows you to select from a sequence of objects using a number, so in a sense

it associates numbers to objects. But what if you’d like to select from a

sequence of objects using some other criterion? A

Stack

is an example: its selection criterion is “the last thing pushed on the

stack.” A powerful twist on this idea of “selecting from a

sequence” is alternately termed a

map,
a dictionary,
or an associative
array
.
Conceptually, it seems like a vector, but instead of looking up objects using a
number, you look them up using
another
object
!
This is often a key process in a program.

The

concept shows up in Java as the

abstract

class

Dictionary

The interface for this class is straightforward:

size( )

tells you how many elements are within,

isEmpty( )

true

if there are no elements,

put(Object
key, Object value)

adds a value (the thing you want), and associates it with a key (the thing you

look it up with).

get(Object
key)

produces the value given the corresponding key, and

remove(Object
key)

removes the key-value pair from the list. There are enumerations:

keys( )

produces an

Enumeration

of the keys, and

elements( )

produces an

Enumeration

of all the values. That’s all there is to a

Dictionary

isn’t terribly difficult to implement. Here’s a simple approach,

which uses two

Vector

one for keys and one for values:

//: AssocArray.java
// Simple version of a Dictionary
import java.util.*;
 
public class AssocArray extends Dictionary {
  private Vector keys = new Vector();
  private Vector values = new Vector();
  public int size() { return keys.size(); }
  public boolean isEmpty() {
    return keys.isEmpty();
  }
  public Object put(Object key, Object value) {
    keys.addElement(key);
    values.addElement(value);
    return key;
  }
  public Object get(Object key) {
    int index = keys.indexOf(key);
    // indexOf() Returns -1 if key not found:
    if(index == -1) return null;
    return values.elementAt(index);
  }
  public Object remove(Object key) {
    int index = keys.indexOf(key);
    if(index == -1) return null;
    keys.removeElementAt(index);
    Object returnval = values.elementAt(index);
    values.removeElementAt(index);
    return returnval;
  }
  public Enumeration keys() {
    return keys.elements();
  }
  public Enumeration elements() {
    return values.elements();
  }
  // Test it:
  public static void main(String[] args) {
    AssocArray aa = new AssocArray();
    for(char c = 'a'; c &lt;= 'z'; c++)
      aa.put(String.valueOf(c),
             String.valueOf(c)
             .toUpperCase());
    char[] ca = { 'a', 'e', 'i', 'o', 'u' };
    for(int i = 0; i &lt; ca.length; i++)
      System.out.println("Uppercase: " +
             aa.get(String.valueOf(ca[i])));
  }
} ///:~

The

first thing you see in the definition of

AssocArray

is that it

extends
Dictionary

This means that

AssocArray
is
a type of
Dictionary

so you can make the same requests of it that you can a

Dictionary

If you make your own

Dictionary

as is done here, all you need to do is fill in all the methods that are in

Dictionary

(And you

must

override all the methods because all of them – with the exception of the

constructor – are abstract.)

The

Vector

keys

and

values

are linked by a common index number. That is, if you call

put( )

with a key of “roof” and a value of “blue” (assuming

you’re associating the various parts of a house with the colors they are

to be painted) and there are already 100 elements in the

AssocArray

then “roof” will be the 101 element of

keys

and “blue” will be the 101 element of

values

And if you look at

get( )

when you pass “roof” in as the key, it produces the index number

with

keys

indexOf( )

and then uses that index number to produce the value in the associated

values

vector.

The

test in

main( )

is simple; it’s just a map of lowercase characters to uppercase

characters, which could obviously be done in a number of more efficient ways.

But it shows that

AssocArray

is functional.

The

standard Java library contains only one embodiment of a

Dictionary

called

Hashtable

[34]

Java’s

Hashtable

has the same basic interface as

AssocArray

(since

they both inherit

Dictionary

but it

differs

in one distinct way: efficiency. If you look at what must be done for a

get( )

it seems pretty slow to search through a

Vector

for the key. This is where

Hashtable

speeds things up. Instead of the tedious linear search for the key, it uses a

special value called a

hash
code

The

hash code is a way to take some information in the object in question and turn

it into a “relatively unique”

int

for that object. All objects have a hash code, and

hashCode( )
is a method in the root class Object.
A
Hashtable
takes
the
hashCode( )
of the object and uses it to quickly hunt for the key. This results in a
dramatic performance improvement.
[35]
The
way
that a
Hashtable
works is beyond the scope of this book
[36]
– all you need to know is that
Hashtable
is a fast
Dictionary,
and that a
Dictionary
is a useful tool.

an example of the use of a

Hashtable

consider a program to check the randomness of Java’s

Math.random( )
method. Ideally, it would produce a perfect distribution of random numbers, but
to test this you need to generate a bunch of random numbers and count the ones
that fall in the various ranges. A
Hashtable
is perfect for this, since it associates objects with objects (in this case,
the values produced by
Math.random( )
with the number of times those values appear):

//: Statistics.java
// Simple demonstration of Hashtable
import java.util.*;
 
class Counter {
  int i = 1;
  public String toString() {
    return Integer.toString(i);
  }
}
 
class Statistics {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i &lt; 10000; i++) {
      // Produce a number between 0 and 20:
      Integer r =
        new Integer((int)(Math.random() * 20));
      if(ht.containsKey(r))
        ((Counter)ht.get(r)).i++;
      else
        ht.put(r, new Counter());
    }
    System.out.println(ht);
  }
} ///:~

main( )

each time a random number is generated it is wrapped inside an

Integer

object so that handle can be used with the

Hashtable

(You can’t use a primitive with a collection, only an object handle.) The

containsKey( )

method checks to see if this key is already in the collection. (That is, has

the number been found already?) If so, the

get( )
methods gets the associated value for the key, which in this case is a
Counter
object. The value
i
inside the counter is then incremented to indicate that one more of this
particular random number has been found.

the key has not been found yet, the method

put( )
will place a new key-value pair into the
Hashtable.
Since
Counter
automatically initializes its variable
i
to one when it’s created, it indicates the first occurrence of this
particular random number.

display the

Hashtable

it is simply printed out. The

Hashtable
toString( )

method moves through all the key-value pairs and calls the

toString( )

for each one. The

Integer
toString( )

is pre-defined, and you can see the

toString( )

for

Counter

The output from one run (with some line breaks added) is:

{19=526, 18=533, 17=460, 16=513, 15=521, 14=495,
 13=512, 12=483, 11=488, 10=487, 9=514, 8=523,
 7=497, 6=487, 5=480, 4=489, 3=509, 2=503, 1=475,
 0=505}

You

might wonder at the necessity of the class

Counter,

which seems like it doesn’t even have the functionality of the wrapper

class

Integer

Why not use

int

Integer

Well, you can’t use an

int

because all of the collections can hold only

Object

handles. After seeing collections the wrapper classes might begin to make a

little more sense to you, since you can’t put any of the primitive types

in collections. However, the only thing you

can

do with the Java

wrappers
is to initialize them to a particular value and read that value. That is,
there’s no way to change a value once a wrapper object has been created.
This makes the
Integer
wrapper immediately useless to solve our problem, so we’re forced to
create a new class that does satisfy the need.

Creating
“key” classes

the previous example, a standard library class (

Integer

)

was used as a key for the

Hashtable

It worked fine as a key, because it has all the necessary wiring to make it

work correctly as a key. But a common pitfall occurs when using

Hashtable

when you create your own classes to be used as keys. For example, consider a

weather predicting system that matches

Groundhog

objects to

Prediction

objects. It seems fairly straightforward: you create the two classes and use

Groundhog

as the key and

Prediction

as the value:

//: SpringDetector.java
// Looks plausible, but doesn't work right.
import java.util.*;
 
class Groundhog {
  int ghNumber;
  Groundhog(int n) { ghNumber = n; }
}
 
class Prediction {
  boolean shadow = Math.random() &gt; 0.5;
  public String toString() {
    if(shadow)
      return "Six more weeks of Winter!";
    else
      return "Early Spring!";
  }
}
 
public class SpringDetector {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i &lt; 10; i++)
      ht.put(new Groundhog(i), new Prediction());
    System.out.println("ht = " + ht + "n");
    System.out.println(
      "Looking up prediction for groundhog #3:");
    Groundhog gh = new Groundhog(3);
    if(ht.containsKey(gh))
      System.out.println((Prediction)ht.get(gh));
  }
} ///:~

Each

Groundhog

is given an identity number, so you can look up a

Prediction

in the

Hashtable

by saying “Give me the

Prediction

associated

with

Groundhog

number 3.” The

Prediction

class contains a

boolean

that is initialized using

Math.random( )

and a

toString( )

that interprets the result for you. In

main( )

Hashtable

is filled with

Groundhog

and their associated

Prediction

The

Hashtable

printed so you can see that it has been filled. Then a

Groundhog

with an identity number of 3 is used to look up the prediction for

Groundhog

#3.

seems simple enough, but it doesn’t work. The problem is that

Groundhog

is inherited from the common root class

Object

(which is what happens if you don’t specify a base class, thus all

classes are ultimately inherited from

Object

It is

Object

’s

hashCode( )

method that is used to generate the hash code for each object, and by default

it just uses the address of its object. Thus, the first instance of

Groundhog(3)

does

not

produce a hash code equal to the hash code for the second instance of

Groundhog(3)

that we tried to use as a lookup.

You

might think that all you need to do is write an appropriate override for

hashCode( ).
But it still won’t work until you’ve done one more thing: override
the equals( )
that is also part of
Object.
This method is used by the
Hashtable
when trying to determine if your key is equal to any of the keys in the table.
Again, the default
Object.equals( )
simply compares object addresses, so one
Groundhog(3)
is not equal to another
Groundhog(3).

Thus,

to use your own classes as keys in a

Hashtable

you must override both

hashCode( )

and

equals( )

as shown in the following solution to the problem above:

//: SpringDetector2.java
// If you create a class that's used as a key in
// a Hashtable, you must override hashCode()
// and equals().
import java.util.*;
 
class Groundhog2 {
  int ghNumber;
  Groundhog2(int n) { ghNumber = n; }
  public int hashCode() { return ghNumber; }
  public boolean equals(Object o) {
    if ((o != null) &amp;&amp; (o instanceof Groundhog2))
      return
        ghNumber == ((Groundhog2)o).ghNumber;
    else return false;
  }
}
 
public class SpringDetector2 {
  public static void main(String[] args) {
    Hashtable ht = new Hashtable();
    for(int i = 0; i &lt; 10; i++)
      ht.put(new Groundhog2(i),new Prediction());
    System.out.println("ht = " + ht + "n");
    System.out.println(
      "Looking up prediction for groundhog #3:");
    Groundhog2 gh = new Groundhog2(3);
    if(ht.containsKey(gh))
      System.out.println((Prediction)ht.get(gh));
  }
} ///:~

Note

that this uses the

Prediction

class from the previous example, so

SpringDetector.java

must be compiled first or you’ll get a compile-time error when you try to

compile

SpringDetector2.java

Groundhog2.hashCode( )

returns the ground hog number as an identifier. (In this example, the

programmer is responsible for ensuring that no two ground hogs exist with the

same ID number.) The

hashCode( )

not required to return a unique identifier, but the

equals( )

method must be able to strictly determine whether two objects are equivalent.

The

equals( )

method does two sanity checks: to see if the object is

null

and if not, whether it is an instance of

Groundhog2

(using the

instanceof

keyword, which is fully explained in Chapter 11). It should be a

Groundhog2

even continue executing

equals( )

The comparison, as you can see, is based on the actual

ghNumber

This time, when you run the program, you’ll see it produces the correct

output. (Many of the Java library classes override the

hashcode( )

and

equals( )

methods to be based upon their contents.)

Properties:
a type of Hashtable

the first example in this book, a type of

Hashtable

was used called

Properties

In that example, the lines:

Properties p = System.getProperties();
p.list(System.out);

called

the

static

method

getProperties( )
to get a special
Properties
object that described the system characteristics. The method
list( )
is a method of
Properties
that
sends the contents to any stream output that you choose. There’s also a
save( )
method to allow you to write your property list to a file in a way that it can
be retrieved later with the
load( )
method.

Although

the

Properties
class is inherited from
Hashtable,
it also
contains
a second
Hashtable
that acts to hold the list of “default” properties. So if a
property isn’t found in the primary list, the defaults will be searched.

The

Properties

class is also available for use in your programs (an example is

ClassScanner.java

in Chapter 17). You can find more complete details in the Java library

documentation.

Enumerators
revisited

can now demonstrate the true power of the

Enumeration:
the ability to separate the operation of traversing a sequence from the
underlying structure of that sequence. In the following example, the class
PrintData
uses an
Enumeration
to move through a sequence and call the toString( )
method for every object. Two different types of collections are created, a Vector
and a Hashtable,
and they are each filled with, respectively,
Mouse
and
Hamster
objects.
(These classes are defined earlier in the chapter; notice you must have compiled
HamsterMaze.java
and
WorksAnyway.java
for the following program to compile.) Because an
Enumeration
hides
the structure of the underlying collection,
PrintData
doesn’t know or care what kind of collection the
Enumeration
comes
from:

//: Enumerators2.java
// Revisiting Enumerations
import java.util.*;
 
class PrintData {
  static void print(Enumeration e) {
    while(e.hasMoreElements())
      System.out.println(
        e.nextElement().toString());
  }
}
 
class Enumerators2 {
  public static void main(String[] args) {
    Vector v = new Vector();
    for(int i = 0; i &lt; 5; i++)
      v.addElement(new Mouse(i));
 
    Hashtable h = new Hashtable();
    for(int i = 0; i &lt; 5; i++)
      h.put(new Integer(i), new Hamster(i));
 
    System.out.println("Vector");
    PrintData.print(v.elements());
    System.out.println("Hashtable");
    PrintData.print(h.elements());
  }
} ///:~

Note

that

PrintData.print( )

takes advantage of the fact that the objects in these collections are of class

Object

so it can call

toString( )

It’s more likely that in your problem, you must make the assumption that

your

Enumeration

is walking through a collection of some specific type. For example, you might

assume that everything in the collection is a

Shape

with a

draw( )

method. Then you must downcast from the

Object

that

Enumeration.nextElement

()

returns to produce a

Shape

[34]

If you plan to use RMI (described in Chapter 15), you should be aware that

there’s a problem when putting remote objects into a

Hashtable

(See

Core
Java

by Cornell

Horstmann, Prentice-Hall 1997).

[35]

If these speedups still don’t meet your performance needs, you can

further accelerate table lookup by writing your own hash table routine. This

avoids delays due to casting to and from

Object

and synchronization built into the Java Class Library hash table routine. To

reach even higher levels of performance, speed enthusiasts can use Donald

Knuth’s

The
Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition

to replace overflow bucket lists with arrays that have two additional benefits:

they can be optimized for disk storage characteristics and they can save most

of the time of creating and garbage collecting individual records

[36]

The best reference I know of is

Practical
Algorithms for Programmers

by Andrew Binstock and John Rex, Addison-Wesley 1995.

Contents

Types of collections

Vector

BitSet

Stack

Hashtable

Enumerators
revisited

CodeGuru Staff

Company

Categories

Types of collections

Vector

BitSet

Stack

Hashtable

Enumerators revisited

CodeGuru Staff

Company

Categories

Enumerators
revisited