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.
The modifier function delete(k, D) may be defined as follows.
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.
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, invertible Bloom lookup table with high probability.
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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 2 November 2020.
HTML page formatted Mon Nov 2 12:36:42 2020.
Cite this as:
Paul E. Black, "dictionary", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 2 November 2020. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/dictionary.html