The Java Course provides a general introduction to programming in Java. It is based on A.B. Downey's book, How to Think Like a Computer Scientist. Click here for details.

Table

A Vector Implementation

An easy way to implement the Table ADT is to use a Vector of entries, where each entry is an object that contains a key and a value. These objects are called key-value pairs.

A class definition for a KeyValuePair might look like this:

class KeyValuePair {
Object key, value;

public KeyValuePair (Object key, Object value) {
this.key = key;
this.value = value;
}

public String toString () {
return "{ " + key + ", " + value + " }";
}
}

Then the implementation of Table looks like this:

public class Table {
Vector v;

public Table () {
v = new Vector ();
}
}

To put a new entry in the table, we just add a new KeyValuePair to the Vector:

public void put (Object key, Object value) {
KeyValuePair pair = new KeyValuePair (key, value);
v.add (pair);
}

Then to look up a key in the Table we have to traverse the Vector and find a KeyValuePair with a matching key:

public Object get (Object key) {
Iterator iterator = v.iterator ();
while (iterator.hasNext ()) {
KeyValuePair pair = (KeyValuePair) iterator.next ();
if (key.equals (pair.key)) {
return pair.value;
}
}
return null;
}

The idiom to traverse a Vector is the one we saw in Section 17.11. When we compare keys, we use deep equality (the equals method) rather than shallow equality (the == operator). This allows the key class to specify the definition of equality. In our example, the keys are Strings, so it will use the built-in equals method in the String class.

For most of the built-in classes, the equals method implements deep equality. For some classes, though, it is not easy to define what that means. For example, see the documentation of equals for Doubles.

Because equals is an object method, this implementation of get does not work if key is null. We could handle null as a special case, or we could do what the build-in Hashtable does---simply declare that null is not a legal key.

Speaking of the built-in Hashtable, it's implementation of put is a bit different from ours. If there is already an entry in the table with the given key, put updates it (give it a new value), and returns the old value (or null if there was none. Here is an implementation of their version:

public Object put (Object key, Object value) {
Object result = get (key);
if (result == null) {
KeyValuePair pair = new KeyValuePair (key, value);
v.add (pair);
} else {
update (key, value);
}
return result;
}

The update method is not part of the Table ADT, so it is declared private. It traverses the vector until it finds the right KeyValuePair and then it updates the value field. Notice that we don't have to modify the Vector itself, just one of the objects it contains.

private void update (Object key, Object value) {
Iterator iterator = v.iterator ();
while (iterator.hasNext ()) {
KeyValuePair pair = (KeyValuePair) iterator.next ();
if (key.equals (pair.key)) {
pair.value = value;
break;
}
}
}

The only methods we haven't implemented are containsKey and keys. The containsKey method is almost identical to get except that it returns true or false instead of an object reference or null.

As an exercise, implement keys by building a Vector of keys and returning the elements of the vector. See the documentation of elements in the Vector class for more information.

Home

Table

A Vector Implementation

Last Update: 2011-01-24