Editing Associative array (section)

{{Short description|Data structure that associates keys with values}}
{{Redirect-distinguish|Dictionary (data structure)|data dictionary}}
{{Redirect|Associative container|their C++ implementation|associative containers (C++)}}
{{Redirect|Map (computer science)|the higher-order function|Map (higher-order function)}}
{{Redirect|Associative table|the relation used in database systems to resolve many-to-many relationship|Associative entity}}
In [[computer science]], an '''associative array''', '''key-value store''', '''map''', '''symbol table''', or '''dictionary''' is an [[abstract data type]] that stores a [[collection (abstract data type)|collection]] of [[attribute–value pair|(key, value) pairs]], such that each possible key appears at most once in the collection. In mathematical terms, an associative array is a [[Function (mathematics)|function]] with ''finite'' [[Domain of a function|domain]].<ref>{{cite book |last1=Collins |first1=Graham |last2=Syme |first2=Donald |chapter=A theory of finite maps |title=Higher Order Logic Theorem Proving and Its Applications |series=Lecture Notes in Computer Science |date=1995 |volume=971 |pages=122–137 |doi=10.1007/3-540-60275-5_61|isbn=978-3-540-60275-0 }}</ref> It supports 'lookup', 'remove', and 'insert' operations. 

The '''dictionary problem''' is the classic problem of designing efficient [[data structure]]s that implement associative arrays.<ref>{{cite book|chapter=Optimal Bounds on the Dictionary Problem|last=Andersson|first=Arne|title= Proc. Symposium on Optimal Algorithms|series=Lecture Notes in Computer Science|date=1989|volume=401|pages=106–114|publisher=Springer Verlag|doi=10.1007/3-540-51859-2_10|isbn=978-3-540-51859-4}}</ref>
The two major solutions to the dictionary problem are [[hash table]]s and [[search tree]]s.<ref name="gt"/><ref name="ms"/><ref name="clrs">{{citation | last1 = Cormen | first1 = Thomas H. | author1-link=Thomas H. Cormen | author2-link = Charles E. Leiserson|last2=Leiserson|first2=Charles E.|author3-link=Ron Rivest|last3=Rivest|first3=Ronald L.|author4-link=Clifford Stein|last4=Stein|first4=Clifford | title = [[Introduction to Algorithms]] | edition = 2nd | year = 2001 | publisher = [[MIT Press]] and [[McGraw-Hill]] | isbn=0-262-03293-7 | chapter = 11 Hash Tables | pages = 221–252}}.</ref><ref name="dietzfelbinger">Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994.
[http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf "Dynamic Perfect Hashing: Upper and Lower Bounds"] {{Webarchive|url=https://web.archive.org/web/20160304094014/http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf |date=2016-03-04 }}.
SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.
http://portal.acm.org/citation.cfm?id=182370
{{doi|10.1137/S0097539791194094}}</ref>
It is sometimes also possible to solve the problem using directly addressed [[Array data structure|array]]s, [[binary search tree]]s, or other more specialized structures.

Many programming languages include associative arrays as [[primitive data type]]s, while many other languages provide [[software library|software libraries]] that support associative arrays. [[Content-addressable memory]] is a form of direct hardware-level support for associative arrays.

Associative arrays have many applications including such fundamental [[software design pattern|programming pattern]]s as [[memoization]]<!--NOT a misspelling--><ref name="Michie1968">{{cite journal |last=Michie |first=Donald |url=https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash-cons-papers/michie-memo-nature-1968.pdf |title='Memo' Functions and Machine Learning |journal=[[Nature (journal)|Nature]] |volume=218 |issue= 5136|pages=19–22 |year=1968 |doi=10.1038/218019a0 |bibcode=1968Natur.218...19M |s2cid=4265138 }}</ref> and the [[decorator pattern]].<ref name="decorator">{{harvtxt|Goodrich|Tamassia|2006}}, pp. 597–599.</ref>

The name does not come from the [[associative property]] known in mathematics. Rather, it arises from the association of values with keys. It is not to be confused with [[Flynn's taxonomy#Associative processor|associative processors]].