Chapter 8: Dictionaries

The familiar phrase, `Go look it up,' might be heard when a lazy student asks for the definition of a word from an equally lazy teacher. This phrase is also the principle behind the dictionary abstract data type, which we discuss in this chapter.

As the name implies, the primary use of a dictionary is to store elements so that they can be located quickly using keys. The motivation for such searches is that each element in a dictionary typically stores additional useful information besides its search key, but the only way to get at that information is to use the search key. For example, a dictionary may hold bank accounts. Each account is an object that is identified by an account number and stores a wealth of additional information, including the current balance, the name and address of the account holder, and the history of deposits and withdrawals performed. An application wishing to operate on an account would have to provide the account number as a search \ind{key} to get the account object from the dictionary.

As another example, a dictionary might hold a set of windows open in a graphical interface. The window objects are stored in the dictionary according to some identifier (like a process number), to determine a unique key value, but additional information is stored with each window object, including its dimensions, descriptions of its pull-down menus, its fonts, and its colors. A process wishing to send a message to a particular window object would need to be given a reference to this object, which it could request from the dictionary using the window's ID as a key.

Like a priority queue, a dictionary is a container of key-element pairs. However, although a total order relation on the keys is always required for a priority queue, it is optional for a dictionary. Indeed, the simplest form of a dictionary assumes only that we can determine whether two keys are equal. When a total order relation on the keys is defined, then we can talk about an ordered dictionary, and we can specify additional ADT methods that refer to the ordering of the keys in such cases.

A computer dictionary is similar to a paper dictionary of words in the sense that both are used to look things up. The paper dictionary metaphor is not fully appropriate, however, for we typically desire a computer dictionary to be dynamic, so as to support element insertion and removal. Thus, the dictionary abstract data type has methods for the insertion, removal, and searching of elements with keys.