Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Associative array
open-in-new
<p>In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, an associative array, map, symbol table, or dictionary is an <a href="/facts/Abstract_data_type/BaVGSHNP">abstract data type</a> that stores a <a href="/facts/Collection_(abstract_data_type)/KdjDzR7v">collection</a> of <a href="/facts/Attribute%E2%80%93value_pair/buweLY96">(key, value) pairs</a>, such that each possible key appears at most once in the collection. In mathematical terms, an associative array is a <a href="/facts/Function_(mathematics)/CdReEKCh">function</a> with <i>finite</i> <a href="/facts/Domain_of_a_function/FQvoeUpX">domain</a>. It supports 'lookup', 'remove', and 'insert' operations. </p><p>The dictionary problem is the classic problem of designing efficient <a href="/facts/Data_structure/yNsNvL1I">data structures</a> that implement associative arrays. The two major solutions to the dictionary problem are <a href="/facts/Hash_table/Ht4ptDPF">hash tables</a> and <a href="/facts/Search_tree/zJIIMEH8">search trees</a>. It is sometimes also possible to solve the problem using directly addressed <a href="/facts/Array_data_structure/BKGvF8AM">arrays</a>, <a href="/facts/Binary_search_tree/gWubNt7b">binary search trees</a>, or other more specialized structures. </p><p>Many programming languages include associative arrays as <a href="/facts/Primitive_data_type/0c898228">primitive data types</a>, while many other languages provide <a href="/facts/Software_library/xRzL3P7q">software libraries</a> that support associative arrays. <a href="/facts/Content-addressable_memory/VteSPHMR">Content-addressable memory</a> is a form of direct hardware-level support for associative arrays. </p><p>Associative arrays have many applications including such fundamental <a href="/facts/Software_design_pattern/mV7r4egw">programming patterns</a> as <a href="/facts/Memoization/u08VhUKm">memoization</a> and the <a href="/facts/Decorator_pattern/Pzove9TP">decorator pattern</a>. </p><p>The name does not come from the <a href="/facts/Associative_property/EQX8lV6r">associative property</a> known in mathematics. Rather, it arises from the association of values with keys. It is not to be confused with <a href="/facts/Flynn%27s_taxonomy/VrmXKDTA">associative processors</a>. </p>