The TAO of Java

Dictionaries

Summary: We consider the essential features of the dictionary ADT, another form of collection.

Prerequisites: Linear Structures, Arrays, Dynamic Arrays, Interfaces, Generics.

Contents:

• Dictionary Basics
• A Dictionary Interface
• Applications 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 dynamic-arrays. Like linear structures, arrays let you add and get values. Unlike linear structures, arrays 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 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 is at a particular location in space); we might use almost any type.

One can think of dictionaries as generalized forms of arrays in which the indices can have a variety of types. Further, the indices need not be sequential. Dictionaries are also sometimes called keyed tables or 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.

Note that the get operation for a dictionary, like get for a dynamicArray, does not remove the specified element from the dictionary. Thus, we will also eventually need a method remove to perform this function.

It is much more difficult to specify what keys are valid in a given dictionary than in a given array. In an array, the valid indices are integers between 0 and the length of the array. 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 (i.e., to ensure that all keys in a given dictionary have the same type and to ensure that all values in a given dictionary have the same type), 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 reason 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 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 word frequencies in a document.

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