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 Black.

Entry modified 2 September 2014.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "dictionary", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 September 2014. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/dictionary.html