Associative array

In computing, an associative array, also known as a map or table, is an abstract data type very closely related to the mathematical concepts of functions and relations. They are also commonly found in Lisp under the name alists, which is short for association lists. In Smalltalk and Python they are called Dictionaries, in Java Hashmaps, in Perl Hashes and in ECMAScript any array may be as well an associative array. They can be implemented in any programming language, and one or more implementations of them is typically found either built into the language or the standard library distributed with it (C is a noticable exception, as neither the language nor the standard library directly provide one. It is not difficult to write one in C, though).

Conceptually speaking, an associative array is composed of a set of keys and a set of values and creates a relationship between these sets. An associative array does not strictly require the keys or values to be unique, thus not making them sets in the mathematical sense. However generally the keys are unique. The relationship between a key and its value is sometimes called a mapping or binding.

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

• Bind a new key to a new value (adding it to the associative array)
• Bind an old key to a new value
• Unbind a key to a value (removing it entirely from the associative array)
• Find or look up the value (if any) that is bound to a key

The most important of these operations is look up.

One can think of a telephone book as an example of an associative array, where names are the keys and phone numbers are the values. Another example would be a dictionary where words are the keys and definitions are the values. A database is a sort of generalized associative array.

In LISP, an alist is simply a list of pairs of keys and values, such as the following:

 '(("Sally Smart" . "555-9999")
   ("John Doe" . "555-1212")
   ("J. Random Hacker" . "553-1337"))

The syntax (x . y) is used to indicate a pair. Keys and values need not be the same type within an alist in LISP.

In Smalltalk a dictionary is used:

  phonebook := Dictionary new.
  phonebook at: 'Sally Smart'      put:  '555-9999'.
  phonebook at: 'John Doe'         put:  '555-1212'.
  phonebook at: 'J. Random Hacker' put:  '553-1337'.

To access an entry the message #at: is sent to the dictionary object.

  phonebook at: 'Sally Smart'

gives

  '555-9999'

C++ also has a form of associative array which it calls "std::map". One could create a map with the same information as above using C++ with the following code:

 #include <map>
 #include <string>

 int main()
 {
    std::map<std::string, std::string> phone_book;
    phone_book["Sally Smart"] = "555-9999";
    phone_book["John Doe"] = "555-1212";
    phone_book["J. Random Hacker"] = "553-1337";
    return 0;
 }

In C++, std::map allows keys and values to be different data types, but all of the keys in a particular map must be of the same base type. The same must be true for all of the values.

Associative arrays can be implemented in many different ways, but the most time efficient implementation is generally a hash table. LISP, uses lists of pairs, while C++, typically uses a binary search tree of pairs where the tree is sorted by the key. However, C++ also optionally provides a std::hash_map which uses a hash table.