In computing, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs. 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 in the collection
- the lookup of a value associated with a particular key in the collection.
The implementation of an associative array can be static or dynamic. In static implementations, the set of keys is fixed when the program is compiled. In contrast, dynamic implementations allow pairs to be added or removed at arbitrary points during execution.
The use of associative arrays may promote time and space efficiency in some applications because they can prevent the need for searching data structures that store records in linear sequences. For example, if given a list of employee records containing name and salary, one can quickly add or remove an employee record by computing an index number based on their name and storing or retrieving that record using that index number as its key. In some situations, one may also use associative arrays where one would otherwise use
