Associative array

related topics
{math, number, function}
{system, computer, user}
{rate, high, increase}
{work, book, publish}
{specie, animal, plant}

An associative array (also associative container, map, mapping, dictionary, finite map, and in query-processing an index or index file) is an abstract data type composed of a collection of unique keys and a collection of values, where each key is associated with one value (or set of values). The operation of finding the value associated with a key is called a lookup or indexing, and this is the most important operation supported by an associative array. The relationship between a key and its value is sometimes called a mapping or binding. For example, if the value associated with the key "bob" is 7, we say that our array maps "bob" to 7. Associative arrays are very closely related to the mathematical concept of a function with a finite domain. As a consequence, a common and important use of associative arrays is in memoization.

From the perspective of a computer programmer, an associative array can be viewed as a generalization of an array. While a regular array maps an integer key (index) to a value of arbitrary data type, an associative array's keys can also be arbitrarily typed. In some programming languages, such as Python, the keys of an associative array do not even need to be of the same type.

Content-addressable memory (CAM) systems use a special type of computer memory to improve the performance of lookups in associative arrays and are used in specialized applications. Several supercomputers from the 1970s implemented CAM directly in hardware, and were known as associative computers.

Contents

Operations

The operations that are usually defined for an associative array are:

  • Add: Bind a new key to a new value
  • Reassign: Bind an old key to a new value
  • Remove: Unbind a key from a value and remove the key from the key set
  • Lookup: Find the value (if any) that is bound to a key

Full article ▸

related documents
Document Type Definition
Algebraically closed field
LL parser
Expander graph
Stokes' theorem
Optimization (mathematics)
Banach space
Integer factorization
Parameter
Universal quantification
Henri Lebesgue
A* search algorithm
Topology
Topological vector space
B-spline
Haskell (programming language)
Line integral
Free group
Even and odd permutations
Normal space
Cauchy's integral formula
Sheffer stroke
Minimum spanning tree
Partially ordered set
Morphism
Ordered pair
Yoneda lemma
Weak topology
Stone–Weierstrass theorem
Positive-definite matrix