patternMinor
Are dictionaries and associative arrays the same thing?
Viewed 0 times
samearraystheareanddictionariesassociativething
Problem
With respect to abstract datatypes (ADTs), are the terms "dictionary" and "associative array" perfect synonyms or are there slight differences between them?
Solution
As far as I can tell, associative array is a newer term, maybe emerging from popular use in dynamic programming languages. In algorithms as an academic field, it seems to denote a generalisation of the dictionary but one usually works with dictionaries (probably because most resource characteristics carry over so one does not need to complicate notation).
Citing from theory-leaning [1, p281] (bold emphasis mine):
The dictionary, symbol table, or simply search problem is a fundamental one in computer science: a set of distinct keys is to be organized so that client queries whether or not a given key is in the set can be efficiently answered.
More generally, with distinct keys, we can use binary search trees to implement an associative array, where we associate information with each key and can use the kry to store or retrieve such information.
CLRS [2, p229] make no mention of associative arrays but define dictionaries:
We call a dynamic set that supports [insertion, deletion and membership test] a dictionary.
In the more practically inclined [3, p361 ff], the term symbol table is used as a synonym for dictionary but defined in a slightly different way:
A symbol table is a data structure for key-value pairs that supports two operations: insert (put) a new pair into the table and search for (get) the value associated with a given key.
Later, they write:
[The conventions "no duplicate keys" and "put on an existing key replaces the old value"] define the associative array abstraction, where you can think of a symbol table as being just like an array, where keys are indices and values are array entries.
Summarising this small literature research (which is not without contradictions) and from a theoretical viewpoint, I'd state the following:
-
A dictionary is a data structure that implements a (dynamic) set with insertion, deletion and membership test.
Mathematically speaking, a dictionary over universe $X$ represents an element of the power set $2^X$ of $X$.
-
An associative array is a data structure that implements a (dynamic) mapping with insertion/update, deletion and retrieval.
Mathematically speaking, an associative array over key universe $X$ and value universe $Y$ represents an element of the set of functions $X \to Y$.
One can thus view a dictionary over universe $X$ as associative array over $(X,\{0,1\})$; this closely resembles the indicator function of sets.
I think this fits programmers' reality quite well, but terms may be used differently over there.
Important: The usage of the term "array" may suggest $O(1)$ accesses. This can, in general, not be expected to be true; at least not in the worst-case and without amortisation arguments. Implementations using hash tables come closest; see here for a discussion about what to expect w.r.t. performance.
Citing from theory-leaning [1, p281] (bold emphasis mine):
The dictionary, symbol table, or simply search problem is a fundamental one in computer science: a set of distinct keys is to be organized so that client queries whether or not a given key is in the set can be efficiently answered.
More generally, with distinct keys, we can use binary search trees to implement an associative array, where we associate information with each key and can use the kry to store or retrieve such information.
CLRS [2, p229] make no mention of associative arrays but define dictionaries:
We call a dynamic set that supports [insertion, deletion and membership test] a dictionary.
In the more practically inclined [3, p361 ff], the term symbol table is used as a synonym for dictionary but defined in a slightly different way:
A symbol table is a data structure for key-value pairs that supports two operations: insert (put) a new pair into the table and search for (get) the value associated with a given key.
Later, they write:
[The conventions "no duplicate keys" and "put on an existing key replaces the old value"] define the associative array abstraction, where you can think of a symbol table as being just like an array, where keys are indices and values are array entries.
Summarising this small literature research (which is not without contradictions) and from a theoretical viewpoint, I'd state the following:
-
A dictionary is a data structure that implements a (dynamic) set with insertion, deletion and membership test.
Mathematically speaking, a dictionary over universe $X$ represents an element of the power set $2^X$ of $X$.
-
An associative array is a data structure that implements a (dynamic) mapping with insertion/update, deletion and retrieval.
Mathematically speaking, an associative array over key universe $X$ and value universe $Y$ represents an element of the set of functions $X \to Y$.
One can thus view a dictionary over universe $X$ as associative array over $(X,\{0,1\})$; this closely resembles the indicator function of sets.
I think this fits programmers' reality quite well, but terms may be used differently over there.
Important: The usage of the term "array" may suggest $O(1)$ accesses. This can, in general, not be expected to be true; at least not in the worst-case and without amortisation arguments. Implementations using hash tables come closest; see here for a discussion about what to expect w.r.t. performance.
- An Introduction to the Analysis of Algorithms by R. Sedgewick and P. Flajolet (2nd ed, 2013)
- Introduction to Algorithms by T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein (3rd ed, 2009)
- Algorithms by R. Sedgewick and K. Wayne (4th ed, 2011)
Context
StackExchange Computer Science Q#29982, answer score: 6
Revisions (0)
No revisions yet.