Movatterモバイル変換

dictionary

(data structure)

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

Formal Definition: The operations new(), insert(k, v, D), and find(k, D) may be defined withaxiomatic 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

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

4. delete(k, new()) = new()
5. delete(k, insert(k, v, D)) = delete(k, D)
6. delete(k, insert(j, v, D)) = insert(j, v, delete(k, D)) if k ≠ j

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

7. 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,invertible Bloom lookup table with high probability.

See alsototal 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 abinary relation that maps keys to values. The keys of a dictionary are aset.

Contributions by Rob Stewart 16 March 2004.

Author:PEB

Implementation

If you have suggestions, corrections, or comments, please get in touchwithPaul Black.

Entry modified 2 November 2020.
HTML page formatted Wed Oct 30 12:15:30 2024.

Cite this as:
Paul E. Black, "dictionary", inDictionary 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