In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection. Operations associated with this data type allow:
the addition of a pair to the collection the removal of a pair from the collection the modification of an existing pair the lookup of a value associated with a particular key
The dictionary problem is a classic computer science problem: the task of designing a data structure that maintains a set of data during 'search', 'delete', and 'insert' operations. The two major solutions to the dictionary problem are a hash table or a search tree. In some cases it is also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structures. Many programming languages include associative arrays as primitive data types, and they are available in software libraries for many others. Content-addressable memory is a form of direct hardware-level support for associative arrays. Associative arrays have many applications including such fundamental programming patterns as memoization and the decorator pattern.
1 Operations 2 Example 3 Implementation
3.2.1 Self-balancing binary search trees 3.2.2 Other trees
4 Language support 5 Permanent storage 6 See also 7 References 8 External links
Operations In an associative array, the association between a key and a value is often known as a "binding", and the same word "binding" may also be used to refer to the process of creating a new association. The operations that are usually defined for an associative array are:
Add or insert: add a new
( k e y , v a l u e )
pair to the collection, binding the new key to its new value. The arguments to this operation are the key and the value. Reassign: replace the value in one of the
( k e y , v a l u e )
pairs that are already in the collection, binding an old key to a new value. As with an insertion, the arguments to this operation are the key and the value. Remove or delete: remove a
( k e y , v a l u e )
pair from the collection, unbinding a given key from its value. The argument to this operation is the key. Lookup: find the value (if any) that is bound to a given key. The argument to this operation is the key, and the value is returned from the operation. If no value is found, some associative array implementations raise an exception.
Often then instead of add or reassign there is a single set operation that adds a new
( k e y , v a l u e )
pair if one does not already exist, and otherwise reassigns it. In addition, associative arrays may also include other operations such as determining the number of bindings or constructing an iterator to loop over all the bindings. Usually, for such an operation, the order in which the bindings are returned may be arbitrary. A multimap generalizes an associative array by allowing multiple values to be associated with a single key. A bidirectional map is a related abstract data type in which the bindings operate in both directions: each value must be associated with a unique key, and a second lookup operation takes a value as argument and looks up the key associated with that value. Example Suppose that the set of loans made by a library is represented in a data structure. Each book in a library may be checked out only by a single library patron at a time. However, a single patron may be able to check out multiple books. Therefore, the information about which books are checked out to which patrons may be represented by an associative array, in which the books are the keys and the patrons are the values. Using notation from Python or JSON, the data structure would be:
"Pride and Prejudice": "Alice", "Wuthering Heights": "Alice", "Great Expectations": "John"
A lookup operation on the key "Great Expectations" would return "John". If John returns his book, that would cause a deletion operation, and if Pat checks out a book, that would cause an insertion operation, leading to a different state:
"Pride and Prejudice": "Alice", "The Brothers Karamazov": "Pat", "Wuthering Heights": "Alice"
For dictionaries with very small numbers of bindings, it may make
sense to implement the dictionary using an association list, a linked
list of bindings. With this implementation, the time to perform the
basic dictionary operations is linear in the total number of bindings;
however, it is easy to implement and the constant factors in its
running time are small.
Another very simple implementation technique, usable when the keys are
restricted to a narrow range of integers, is direct addressing into an
array: the value for a given key k is stored at the array cell A[k],
or if there is no binding for k then the cell stores a special
sentinel value that indicates the absence of a binding. As well as
being simple, this technique is fast: each dictionary operation takes
constant time. However, the space requirement for this structure is
the size of the entire keyspace, making it impractical unless the
keyspace is small.
The two major approaches to implementing dictionaries are a hash table
or a search tree.
This graph compares the average number of cache misses required to look up elements in tables with separate chaining and open addressing.
Underlying data structure Lookup Insertion Deletion Ordered
average worst case average worst case average worst case
Hash table O(1) O(n) O(1) O(n) O(1) O(n) No
Self-balancing binary search tree O(log n) O(log n) O(log n) O(log n) O(log n) O(log n) Yes
unbalanced binary search tree O(log n) O(n) O(log n) O(n) O(log n) O(n) Yes
Sequential container of key-value pairs (e.g. association list) O(n) O(n) O(1) O(1) O(n) O(n) No
Main article: Comparison of programming languages (mapping)
Associative arrays can be implemented in any programming language as a
package and many language systems provide them as part of their
standard library. In some languages, they are not only built into the
standard system, but have special syntax, often using array-like
Built-in syntactic support for associative arrays was introduced by
SNOBOL4, under the name "table".
MUMPS made multi-dimensional
associative arrays, optionally persistent, its key data structure.
SETL supported them as one possible implementation of sets and maps.
Most modern scripting languages, starting with
AWK and including Rexx,
support associative arrays as a primary container type. In many more
languages, they are available as library functions without special
In Smalltalk, Objective-C, .NET, Python, REALbasic, Swift, VBA and
Delphi they are called dictionaries; in Perl, Ruby and
are called hashes; in C++, Java, Go, Clojure, Scala, OCaml, Haskell
they are called maps (see map (C++), unordered_map (C++), and Map); in
Common Lisp and Windows PowerShell, they are called hash tables (since
both typically use this implementation). In PHP, all arrays can be
associative, except that the keys are limited to integers and strings.
Computer programming portal
Key-value database Tuple Function (mathematics) JSON
^ a b c d e f Goodrich, Michael T.; Tamassia, Roberto (2006), "9.1 The
Map Abstract Data Type", Data Structures & Algorithms in Java (4th
ed.), Wiley, pp. 368–371
^ a b c d e Mehlhorn, Kurt; Sanders, Peter (2008), "4 Hash Tables and
Associative Arrays", Algorithms and Data Structures: The Basic Toolbox
(PDF), Springer, pp. 81–98
^ Anderson, Arne (1989). "Optimal Bounds on the Dictionary Problem".
Proc. Symposium on Optimal Algorithms. Springer Verlag:
^ a b c d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.;
Stein, Clifford (2001), "11 Hash Tables", Introduction to Algorithms
Look up associative array in Wiktionary, the free dictionary.
NIST's Dictionary of Algorithms and Data Structures: Associative Array
v t e
List Stack Queue
Double-ended priority queue
Association list Linked list Skip list Unrolled linked list XOR linked list
B-tree Binary search tree
AA tree AVL tree Red–black tree Self-balancing tree Splay tree
Binary heap Binomial heap Fibonacci heap
R* tree R+ tree Hilbert R-tree
Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures
v t e
Arbitrary-precision or bignum Complex Decimal Fixed point Floating point
Double precision Extended precision Half precision Long double Minifloat Octuple precision Quadruple precision Single precision
Algebraic data type
Array Associative array Class Dependent Equality Inductive List Object
Option type Product Record Set Union
Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Top type Type class Unit type Void
Abstract data type Data structure Generic Kind
Parametric polymorphism Primitive data type Protocol
Subtyping Type constructor Type conversion Type system Type theory
See also platform-dependent and independent units of