Associative Array

An Associative Array is a collection data structure that facilitates the storage, update, and retrieval of Key-Value Pairs.

• AKA: Key-Value Table, Associative Container, Map Structure, Dictionary Structure, Lookup Table.
• Context:
  • It can (typically) be accessed natively from a Programming Language.
  • It can be implemented with:
    • a Hash Table.
    • a Self-Balancing Binary Search Tree.
• Example(s):
  • a Perl Associative Array.
  • a Java Associative Array/Java Map.
  • a Scala Associative Array/Scala Map.
  • a Cassandra Associative Array.
• Counter-Example(s):
  • an Array Data Structure.
• See: Hash Data Structure.

---

---

References

2011

• http://en.wikipedia.org/wiki/Collection_%28computing%29#Associative_arrays
  • An associative array or "lookup table" acts like a dictionary, providing a "value" (like a definition) in response to a lookup on a "key" (like a word). The "value" might be a reference to a compound data structure. A hash table is usually an efficient implementation.
• http://en.wikipedia.org/wiki/Associative_array
  • In computer science, an associative array (also called a map or a 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 pairs to the collection, the removal of pairs from the collection, the modification of the values of existing pairs, and the lookup of the value associated with a particular key.

    The dictionary problem is the task of designing a data structure that implements an associative array. A standard solution to the dictionary problem is a hash table; 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

2009

• http://en.wikipedia.org/wiki/Associative_array
  • ... 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, the keys of an associative array do not even need to be of the same type.

---