NIST

dictionary

(data structure)

Definition: An abstract data type storing items, or values. A value is accessed by an associated key. Basic operations are new, insert, find and delete.

Formal Definition: The operations new(), insert(k, v, D), and find(k, D) may be defined with axiomatic semantics as follows.

  1. new() returns a dictionary
  2. find(k, insert(k, v, D)) = v
  3. find(k, insert(j, v, D)) = find(k, D) if k ≠ j
where k and j are keys, v is a value, and D is a dictionary.

The modifier function delete(k, D) may be defined as follows.

  1. delete(k, new()) = new()
  2. delete(k, insert(k, v, D)) = delete(k, D)
  3. delete(k, insert(j, v, D)) = insert(j, v, delete(k, D)) if k ≠ j

If we want find to be a total function, we could define find(k, new()) using a special value: fail. This only changes the return type of find.

  1. find(k, new()) = fail

Also known as association list, map, property list.

Generalization (I am a kind of ...)
binary relation, abstract data type.

Specialization (... is a kind of me.)
associative array.

See also total order, set Some implementations: linked list, hash table, B-tree, jump list, directed acyclic word graph.

Note: The terms "association list" and "property list" are used with LISP-like languages and in the area of Artificial Intelligence. These suggest a relatively small number of items, whereas a dictionary may be quite large. Professionals in the Data Management area have specialized semantics for "dictionary" and related terms.

A dictionary defines a binary relation that maps keys to values. The keys of a dictionary are a set.

Contributions by Rob Stewart 16 March 2004.

Author: PEB

Implementation

(C++, Pascal, and Fortran). Maksim Goleta's Collections (C#) implementing stacks, queues, linked lists, binary search trees, AVL trees, and dictionaries.
Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.

Entry modified 23 May 2011.
HTML page formatted Tue Dec 6 16:16:32 2011.

Cite this as:
Paul E. Black, "dictionary", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 23 May 2011. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/dictionary.html

to NIST home page