The TAO of Java

Dictionaries

Summary: We consider the essential features of dictionaries, another form of collection. We also consider a straightforward implementation of the dictionary ADT.

Prerequisites: Linear Structures, Arrays, Vectors, Polymorphism, Inheritance, Generics.

Contents:

• Dictionary Basics
• A Dictionary Interface
• Applications of Dictionaries
• A Vector-Based Implementation of Dictionaries

Dictionary Basics

At this point in your career, you've seen a variety of abstract data types, most of which are used to collect values. You've seen linear structures, which collect values and permit you to access the values one-by-one by removing them. Different kinds of linear structures provide different policies for which value you get.

You've also seen arrays and vectors. Like linear structures, arrays and vectors let you add and get values. Unlike linear structures, arrays and vectors index the values you add: When you add a value, you specify a numeric index and when you get a value, you also specify that index. (Arrays and vectors also differ from linear structures in that when you get a value, it is not deleted.)

Is it possible to index collections by values other than integers? Certainly. We might use strings as indices, we might use real numbers (although, given that reals are approximated, that's probably a bad idea), we might use points in two-space (e.g., to look up what's at a particular location in space), we might use almost any type.

The generalized forms of arrays in which indices can have a variety of types are often called dictionaries. Others call them as keyed tables and maps. In general, the indices are called keys and the values stored by those indices are called values.

A Dictionary Interface

Just as the simplest version of arrays has three core methods: put(int i, E val), get(int i), and length(), so too do dictionaries have only a few basic methods. We certainly need put and get methods that use keys rather than integers. However, since we don't restrict the size of dictionaries, we don't really need length

On the other hand, it's much more difficult to specify what valid keys are. In an array, the valid indices are integers between 0 and the length of the vector. In a typical dictionary, any key is valid for a call to put, but only previously used keys are valid for a call to get. When an invalid key is used, we should throw an exception.

To make dictionaries homogeneous, we parameterize the class with the type to use for keys (K) and the type to use for values (V).

Putting it all together, we get the following interface.

package username.dict;

import java.io.PrintWriter;

/**
 * Dictionaries that can have specified index and value types.
 *
 * @author Samuel A. Rebelsky
 * @version 1.1 of April 2006
 */
public interface Dict<K,V>
{
  /**
   * Add something to the dictionary (or replace something already
   * in the dictionary).
   * 
   * @pre
   *   key is not null.
   * @pre
   *   value is not null.
   * @post
   *   this.get(key) returns value.
   */
  public void put(K key, V value);

  /**
   * Get something from the dictionary.
   *
   * @pre
   *   key is not null.
   * @post
   *   Returns the most recent value for this.put(index,value).
   * @exception NoSuchKeyException
   *   If the key does not appear in the dictionary.
   */
  public V get(K key)
    throws NoSuchKeyException;

  /**
   * Dump the dictionary to the screen or to a file.
   */
  void dump(PrintWriter pen);
 
} // interface Dict<K,V>

You'll note that I've included a dump method. That method is there primarily to support debugging and testing.

Applications of Dictionaries

Why would computer scientists and programmers use dictionaries? The most obvious is to implement things that correspond to what we traditionally think of as dictionaries: things in which you look up words.

Another reason is that dictionaries make many more tasks much more convenient. For example, we can use a dictionary to keep track of objects we've seen as we explore a set of values, so that we don't check the same value twice.

We can also use a dictionary to count things. The first time you see an object, you create a new pair that uses the object as a key and a counter as the value. Each time you see the same object again, you grab the counter and increment it. Such a technique is useful in looking at work frequencies in a document.

Some programmers also use dictionaries to implement a simple form of database.

A Vector-Based Implementation of Dictionaries

It is also fairly easy to implement dictionaries, at least once we have another data structure, such as a vector. In a vector-based implementation of dictionaries, we typically implement the put method by adding a key/value pair at an appropriate place in the vector. The easiest place to put the pair is at the end of the vector, but, as we will see in the lab, that may cause difficulties.

When we get a value using a particular key, we simply search through the vector for a pair that uses that key.

If you use a list instead of a vector, the implementation is called an association list. If you used a functional language in your first course, you may have seen association lists before.

History

Sunday, 9 April 2006 [Samuel A. Rebelsky]

• Created.