Aqua Phoenix
     >>  Lectures >>  Java 3  


3.4 Data Structures

Java includes a variety of pre-implemented common data structures besides Arrays, e.g. Hashtables, Vectors, etc. These classes are found ubiquitously in code, because of their general applicability.

3.4.1 Vector

A Vector embodies a collection of objects in linear fashion. It can be considered an Array, with the exception that it can grow and shrink dynamically. Arrays are declared with a certain number of elements and do not have the ability to re-size once created.

Vectors are useful as a replacement of Arrays, when the developer is not sure how large a collection of objects is. Vectors contain ordered objects, which means an object is identified by its location. Adding objects to a vector always add them to the end of the list.

It is important to note that Vectors cannot be of specific types. A vector contains objects of type Object. A vector cannot be created for specific types, e.g. int or Circle. However, since all objects in Java inherit from class Object, it is possible to populate a vector with any kind of objects, including those of type Integer and Circle.

Vectors are created like most other objects:

Vector v = new Vector();
The most important or most used methods for this class are:

int size();
void add(Object o);
boolean contains(Object o);
Object elementAt(int index);
int indexOf(Object o);
Using these methods, a vector can be populated with data: add(Object o) , the size or number of items in the vector can be determined: size() , elements at specific positions in the vector can be retrieved: elementAt(int index) , and the vector can be searched for specific objects: contains(Object o) and their location can be identified: indexOf(Object o) .

For example, the following code creates a vector of random integer objects. There is no possibility of adding primitive data types to the vector without wrapping them in some sort of object. Primitive data type int can be wrapped in the corresponding object Integer:

Vector v = new Vector();
for (i = 0; i < 20; i++) {
  v.add(new Integer((int)(Math.random() * 100)));
To iterate over the collection of objects, it is possible to use methods size() and elementAt() :

for (int i = 0; i < v.size(); i++) {
  Integer integer = (Integer)v.elementAt(i);
Another more common way of iterating over the elements of a vector is to use Enumerations:

for (Enumeration e = v.elements(); e.hasMoreElements(); ) {
  Integer integer = (Integer)e.nextElement();
or in a while-loop:

Enumeration e = v.elements()
while (e.hasMoreElements()) {
  Integer integer = (Integer)e.nextElement();
All three of these methods achieve the same result. It is a matter of coding style to select one of them.

3.4.2 Hashtable

A hashtable is a mapping between unique keys and some (possibly non-unique) values. Hashtables tend to be efficient data structures that, if implemented correctly, allow for quick retrieval of data. As opposed to searching through an array one element at a time to find some object, a hashtable hashes keys so that the values are found in dramatically fewer operations.

Hashtables are pre-implemented in Java and are instantiated as follows:

Hashtable h = new Hashtable();
The most important or most used methods are:

void put(Object key, Object value);
Object get(Object key);
boolean containsKey(Object key);
boolean containsElement(Object value);
Object remove(Object key);
int size()
These methods are used to insert items by key and value: put(Object key, Object value) , get an object by its key: get(Object key) , determine if a key or value exist: containsKey(Object key) , containsValue(Object value) , remove values from the hashtable: remove(Object key) (which also returns the value), and find out how many items are in the hashtable: size() .

For example, the following code inserts 20 keys of class Integer, with some corresponding random Integer values:

Hashtable h = new Hashtable();
for (int i = 0; i < 20; i++) {
  h.put(new Integer(i), new Integer((int)(Math.random() * 100)));
To iterate over the collection of keys in the hashtable, the only possiblity is to retrieve the collection of keys, and iterate over them. There are no numerical indices that can be used. To iterate using an Enumeration:

for (Enumeration e = h.keys(); e.hasMoreElements(); ) {
  Integer integer = (Integer)e.nextElement();
  Integer randomValue = (Integer)h.get(integer);
  System.out.println(integer.intValue() + ": " + randomValue.intValue());
This iteration can be done using a while loop as well, as has been demonstrated with Vectors above.

Because hashtables have values in addition to keys, it is also possible to iterate over the values. However, here we cannot use an Enumeration, but we must instead use a Collection and an Iterator as follows:

for (Iterator c = h.values().iterator(); c.hasNext(); ) {
  Integer randomValue = (Integer);
Iterating over values is less common.