In the Beginning

The collection framework introduced with the Java 1.2 API provided much needed new functionality, but several collection classes have been a part of the language since the beginning. Namely, the Vector, Stack, and Hashtable classes and the Enumeration interface have been around since the 1.0 API. With the release of Java 1.2, Vector and Hashtable were retrofitted to implement List and Map, respectively. This was done to integrate them into the collection framework, but, beyond that, their functionality has remained unchanged.

This section provides an overview of how these classes are used because it is likely you will see them in practice for some time to come. You should view them as legacy classes only, however. When you are developing new classes that will operate with a Java 1.2 or higher virtual machine, you should always prefer the newer collection classes to these. However, if you are restricted to an earlier Java release for any reason, these classes are your only option for object containers.

Vector

The Vector class represents an ordered collection of objects that can be referenced using indexes, and can grow and shrink in size . Since the release of the 1.2 API, Vector has extended AbstractList, which implements the List interface in the collections framework. The major difference between Vector and other implementations of List is that the methods of Vector are implemented as synchronized to provide thread-safe access, whether your application requires it or not. The majority of the Vector methods correspond to equivalent List methods, although there are differences in some of the method names . Vector also provides a few convenience methods that the designers of the collections framework decided not to make a part of the List interface.

If you are limited to JDK 1.1.x, you should use Vector for the type of collection it supports. Otherwise, you should use ArrayList, which is a standard implementation of List discussed later in this chapter. If you require synchronization, the Collections class contains a utility method that returns a synchronized view of a List. This functionality is covered a little later also.

Just like List, the intent of Vector has been to provide an alternative to the array. Java arrays perform well and are truly useful, but they don't always fit your needs. Sometimes you might prefer to put items into an array, but, at the point you need to allocate the array, you don't know how many items you will eventually have to store. One way to solve this is to create an array larger than you think you'll need. This is an approach sometimes used in C programming. A Vector is similar to an array in that it holds multiple objects and you can retrieve the stored objects using an index value. However, the primary difference between an array and a Vector is that a Vector automatically grows when its capacity is exceeded. A Vector also provides extra methods for adding and removing elements that you would normally have to do manually in an array, such as inserting an element between two others. Effectively, a Vector is an extensible array.

When you create a Vector, you can specify its initial capacity and how much it should grow each time its capacity is reached. You can also just set one of these values, or neither , and rely on the class defaults. If you have an idea of how many elements a specific Vector will typically store, you can improve its performance by specifying the initial capacity and capacity increment accordingly . To accomplish these various forms of initialization, the JDK 1.1.x Vector class defines three constructors:

 public Vector() public Vector(int initialCapacity) public Vector(int initialCapacity, int capacityIncrement) 

JDK 1.2 added one more constructor to support the collections framework. This constructor accepts a Collection as a parameter and initializes the Vector to hold each of the objects found in the specified collection:

 public Vector(Collection c) 

The remainder of this section focuses on how Vector differs from the List interface. To use Vector in a JDK 1.1.x application, you should consult the API documentation for the exact details of the supported methods. In particular, this section omits any discussion of Vector methods that are declared by the List interface, such as contains, indexOf, isEmpty, and size.

Vector provides addElement and insertElementAt methods to either add an object to the end of its collection or insert one at a specified index. These methods are functionally equivalent to the two overloaded add methods in the List interface:

 public final synchronized void addElement(Object newElement) public final synchronized void insertElementAt(Object newElement, int index) 

You can change the object at a specific position in a Vector with the setElementAt method, which is equivalent to set in the List interface:

 public final synchronized void setElementAt(Object ob, int index) 

Vector allows you to retrieve an object based on its index using the elementAt method, which is equivalent to get in the List interface:

 public final synchronized Object elementAt(int index) 

You can also access the first and last elements in a Vector with its firstElement and lastElement methods, which were not carried over when List was defined:

 public final synchronized Object firstElement() public final synchronized Object lastElement() 

From a performance standpoint, you might want to use a Vector to build up a container of objects but then convert the Vector into an array after all the objects, or at least the number of objects, are known. Vector provides the copyInto method for this purpose, which is similar to the toArray methods of List:

 public final synchronized void copyInto(Object[] obArray) 

Vector defines three methods that are not a part of the List interface for removing one or more objects from its collection. These are removeAllElements, which is equivalent to clear, and removeElement and removeElementAt, which are equivalent to the two overloaded remove methods:

 public final synchronized void removeAllElements() public final synchronized boolean removeElement(Object ob) public final synchronized void removeElementAt(int index) 

A Vector has two notions of size ”the number of elements it currently holds and the currently allocated capacity. The capacity method tells you how many objects the Vector can hold before having to grow:

 public final int capacity() 

You can increase the capacity of a Vector using the ensureCapacity method:

 public final synchronized void ensureCapacity(int minimumCapacity) 

This method tells the Vector that it should allocate more space if its current capacity is less than minimumCapacity. Using this method improves performance by avoiding a lot of small capacity adjustments when the eventual size requirement for a Vector is known. Conversely, if you want to reduce the the capacity, use the trimToSize method:

 public final synchronized void trimToSize() 

This method reduces the capacity of a Vector down to the number of elements it is currently storing.

You can use the setSize method to change the current number of elements:

 public synchronized final void setSize(int newSize) 

If the new size is less than the old size, the elements at the end of the Vector are lost. If the new size is greater than the old size, new elements set to null are added. Calling setSize(0) is the same as calling removeAllElements or clear.

The Enumeration Interface

If you want to cycle through all the elements in a Vector, you can use the elements method to get a corresponding Enumeration object. An Enumeration is responsible for accessing elements in a collection sequentially. It contains two methods, hasMoreElements and nextElement:

 public abstract boolean hasMoreElements() public abstract Object nextElement() 

hasMoreElements returns true while there are still more elements to access. nextElement returns a reference to each element in turn as the collection is traversed. If there are no more elements to access when you call nextElement, you get a NoSuchElementException. You should always use hasMoreElements when working with an Enumeration to avoid this exception.

As an example, the following code fragment uses the Enumeration interface to examine every object in a Vector:

 Enumeration vectEnum = myVector.elements();     // get the vector's enumeration while (vectEnum.hasMoreElements()) {    // while there's something to get   Object nextOb = vectEnum.nextElement();       // get the next object   // do whatever you want with the next object } 

The Enumeration interface is the preferred approach for traversing a Vector in a JDK 1.1.x application; however, for JDK 1.2 and above, you should obtain a ListIterator from one of the overloaded listIterator methods of List instead.

Stack

A stack is a data structure that inserts and retrieves objects in a last-in-first-out (LIFO) manner. In other words, when you ask a stack to give you the next item, it hands back the most recently added item.

The Stack class is implemented as a subclass of Vector that is created with a no-argument constructor:

 public Stack() 

To add an item to the top of the stack, you push it onto the stack:

 public Object push(Object newItem) 

The pop method removes the top item from the stack:

 public Object pop() 

If you try to pop an item off an empty stack, you get an EmptyStackException. You can find out which item is on top of the stack without removing it by using the peek method:

 public Object peek() 

The empty method returns true if there are no items on the stack:

 public boolean empty() 

The search method tells you how far an object is from the top of the stack:

 public int search(Object ob) 

If the object is not on the stack at all, search returns “1.

As with its superclass Vector, Stack is a legacy class. With JDK 1.2 and above, you should use LinkedList instead. This class is discussed in the "General-Purpose Implementations" section later in this chapter.

Hashtable

The Hashtable class holds mappings between keys and value objects. The benefit of using this structure over a simple collection of objects is in the efficiency of object retrieval. When you can associate a key with an object, it is much faster to locate that object in a Hashtable than to iterate through a collection searching for it. If you have not used this type of construct before, you should definitely add it to your toolkit as a programmer.

With JDK 1.2, Hashtable was updated to implement the Map interface. With this in mind, the same basic comments apply to Hashtable as did to Vector. You should prefer HashMap, the true collection framework implementation of Map, to Hashtable if you are working with JDK 1.2 or above. Hashtable differs from HashMap in that it is synchronized and does not allow null for either a key or value. This synchronization results in unnecessary overhead if your application does not require it. Beyond this, the differences between the two are mostly limited to method naming.

Effectively, you can think of Hashtable as a class that uses the hash codes of its key objects to perform lookups for the associated objects. A hash code refers to associating an integer value with an object to help distinguish it from other objects. The Object class defines the hashCode method to support the concept. The particular value of a hash code is unimportant, but it must remain the same for an object during a single execution of an application unless the object changes significantly. Also, any objects that are equal must report the same hash code value. Objects that are not equal are not required to have different hash codes, but the performance of any lookup that uses hash codes is greatly improved when they do.

A Hashtable groups its keys into "buckets" based on their hash codes. When it needs to locate a key, it queries the key's hash code, uses the hash code to find the correct bucket, and then searches the bucket for the correct key. Usually, the number of keys in a bucket is small compared to the total number of keys in the Hashtable, so the number of comparisons performed is much smaller than what is required in a collection such as Vector for a similar search.

A Hashtable has a capacity, which defines the number of buckets it uses, and a load factor, which is the ratio of the number of entries it holds to the number of buckets. When you create a Hashtable, you can specify a load factor threshold value. When the current load factor exceeds this threshold, the capacity is increased by its protected rehash method. The default load factor threshold is 0.75, but you can specify any load factor threshold greater than 0 and less than or equal to 1. A smaller threshold means a faster lookup because there will be few keys per bucket (maybe no more than one), but the table will have far more buckets than elements, so there is some wasted space. A larger threshold means the possibility of slower lookups, but the number of buckets is closer to the number of elements.

The JDK 1.1.x Hashtable class has three constructors that support various options related to initial capacity and load factor. You have the flexibility to specify both of these parameters, to accept a default value for either one, or both:

 public Hashtable() public Hashtable(int initialCapacity) public Hashtable(int initialCapacity, float loadFactorThreshold) 

JDK 1.2 added one more constructor to support the collections framework. This constructor accepts a Map as a parameter and initializes the Hashtable to hold each of the associations found in the specified Map:

 public Hashtable(Map m) 

The remainder of this section focuses on how Hashtable differs from the Map interface. To use Hashtable in a JDK 1.1.x application, you should consult the API documentation for the exact details of the supported methods.

The Map interface defines the containsKey and containsValue methods for querying a Map on whether it holds a specific key or value object. The original implementation of Hashtable supported the containsValue operation with a method named contains. The functionality is equivalent, only the name is less clear. This method is declared as follows :

 public synchronized boolean contains(Object value) 

The keySet and values methods of Map return a map's keys and value objects as a Set and a Collection, respectively. Hashtable also allows these objects to be retrieved through an Enumeration using its keys and elements methods:

 public abstract Enumeration elements() public abstract Enumeration keys()