Editing Associative array (section)

==Operations==
In an associative array, the association between [[attribute–value pair|a key and a value]] is often known as a "mapping"; the same word may also be used to refer to the process of creating a new association.

The operations that are usually defined for an associative array are:<ref name="gt">{{citation|contribution=9.1 The Map Abstract Data Type|title=Data Structures & Algorithms in Java|last1=Goodrich|first1=Michael T.|author1-link=Michael T. Goodrich|last2=Tamassia|first2=Roberto|author2-link=Roberto Tamassia|publisher=Wiley|edition=4th|year=2006|pages=368–371}}</ref><ref name="ms">{{citation|contribution=4 Hash Tables and Associative Arrays|title=Algorithms and Data Structures: The Basic Toolbox|first1=Kurt|last1=Mehlhorn|author1-link=Kurt Mehlhorn|first2=Peter|last2=Sanders|author2-link=Peter Sanders (computer scientist)|publisher=Springer|year=2008|pages=81–98 |url=http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf |archive-url=https://web.archive.org/web/20140802025330/http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf |archive-date=2014-08-02 |url-status=live}}</ref><ref name="Black"/>

;Insert or put
: add a new <math>(key, value)</math> pair to the collection, mapping the key to its new value. Any existing mapping is overwritten. The arguments to this operation are the key and the value.
;Remove or delete
: remove a <math>(key, value)</math> pair from the collection, unmapping a given key from its value. The argument to this operation is the key.
;Lookup, find, or get
: find the value (if any) that is bound to a given key. The argument to this operation is the key, and the value is returned from the operation. If no value is found, some lookup functions raise an [[Exception handling|exception]], while others return a default value (such as zero, null, or a specific value passed to the constructor).

Associative arrays may also include other operations such as determining the number of mappings or constructing an [[iterator]] to loop over all the mappings. For such operations, the order in which the mappings are returned is usually implementation-defined.

A [[multimap]] generalizes an associative array by allowing multiple values to be associated with a single key.<ref>{{harvtxt|Goodrich|Tamassia|2006}}, pp. 389–397.</ref> A [[bidirectional map]] is a related abstract data type in which the mappings operate in both directions: each value must be associated with a unique key, and a second lookup operation takes a value as an argument and looks up the key associated with that value.

===Properties===

The operations of the associative array should satisfy various properties:<ref name="Black">{{cite web |last1=Black |first1=Paul E. |last2=Stewart |first2=Rob |title=dictionary |url=https://xlinux.nist.gov/dads/HTML/dictionary.html |website=Dictionary of Algorithms and Data Structures |access-date=26 January 2022 |date=2 November 2020}}</ref>
* <code>lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)</code>
* <code>lookup(k, new()) = fail</code>, where <code>fail</code> is an exception or default value
* <code>remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))</code>
* <code>remove(k, new()) = new()</code>
where <code>k</code> and <code>j</code> are keys, <code>v</code> is a value, <code>D</code> is an associative array, and <code>new()</code> creates a new, empty associative array.

===Example===
Suppose that the set of loans made by a library is represented in a data structure. Each book in a library may be checked out by one patron at a time. However, a single patron may be able to check out multiple books. Therefore, the information about which books are checked out to which patrons may be represented by an associative array, in which the books are the keys and the patrons are the values. Using notation from [[Python (programming language)|Python]] or [[JSON]], the data structure would be:

<syntaxhighlight lang="javascript">{
    "Pride and Prejudice": "Alice",
    "Wuthering Heights": "Alice",
    "Great Expectations": "John"
}</syntaxhighlight>

A lookup operation on the key "Great Expectations" would return "John". If John returns his book, that would cause a deletion operation, and if Pat checks out a book, that would cause an insertion operation, leading to a different state:

<syntaxhighlight lang="javascript">{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}</syntaxhighlight>