# Associative array

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Associative_array
> Markdown URL: https://mediated.wiki/source/Associative_array.md
> Source: https://en.wikipedia.org/wiki/Associative_array
> Source revision: 1356537070
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

Data structure holding key/value pairs

For the C++ implementation, see [Associative containers (C++)](/source/Associative_containers_(C%2B%2B)). For the higher-order function, see [Map (higher-order function)](/source/Map_(higher-order_function)). For the relation used in database systems to resolve many-to-many relationships, see [Associative entity](/source/Associative_entity). Not to be confused with [data dictionary](/source/Data_dictionary).

In [computer science](/source/Computer_science), an **associative array**, **key-value store**, **map**, **symbol table**, or **dictionary** is an [abstract data type](/source/Abstract_data_type) that stores a [collection](/source/Collection_(abstract_data_type)) of [key/value pairs](/source/Attribute%E2%80%93value_pair), such that each possible key appears at most once in the collection. In mathematical terms, an associative array is a [function](/source/Function_(mathematics)) with finite [domain](/source/Domain_of_a_function).[1] It supports 'lookup', 'remove', and 'insert' operations.

The **dictionary problem** is the classic problem of designing efficient [data structures](/source/Data_structure) that implement associative arrays.[2] The two major solutions to the dictionary problem are [hash tables](/source/Hash_table) and [search trees](/source/Search_tree).[3][4][5][6] It is sometimes also possible to solve the problem using directly addressed [arrays](/source/Array_data_structure), [binary search trees](/source/Binary_search_tree), or other more specialized structures.

Many programming languages include associative arrays as [primitive data types](/source/Primitive_data_type), while many other languages provide [software libraries](/source/Software_library) that support associative arrays. [Content-addressable memory](/source/Content-addressable_memory) is a form of direct hardware-level support for associative arrays.

Associative arrays have many applications including such fundamental [programming patterns](/source/Software_design_pattern) as [memoization](/source/Memoization)[7] and the [decorator pattern](/source/Decorator_pattern).[8] The name does not come from the [associative property](/source/Associative_property) known in mathematics. Rather, it arises from the association of values with keys. It should not be confused with [associative processors](/source/Flynn's_taxonomy#Associative_processor).

## Operations

In an associative array, the association between [a key and a value](/source/Attribute%E2%80%93value_pair) 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:[3][4][9]

**Insert or put**
- add a new ( k e y , v a l u e ) {\displaystyle (key,value)} 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 ( k e y , v a l u e ) {\displaystyle (key,value)} 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](/source/Exception_handling), 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](/source/Iterator) to loop over all the mappings. For such operations, the order in which the mappings are returned is usually implementation-defined.

A [multimap](/source/Multimap) generalizes an associative array by allowing multiple values to be associated with a single key.[10] A [bidirectional map](/source/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:[9]

- lookup(k, insert(j, v, D)) = if k == j then v else lookup(k, D)

- lookup(k, new()) = fail, where fail is an exception or default value

- remove(k, insert(j, v, D)) = if k == j then remove(k, D) else insert(j, v, remove(k, D))

- remove(k, new()) = new()

where k and j are keys, v is a value, D is an associative array, and new() 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](/source/Python_(programming_language)) or [JSON](/source/JSON), the data structure would be:

{
    "Pride and Prejudice": "Alice",
    "Wuthering Heights": "Alice",
    "Great Expectations": "John"
}

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:

{
    "Pride and Prejudice": "Alice",
    "The Brothers Karamazov": "Pat",
    "Wuthering Heights": "Alice"
}

## Implementation

For dictionaries with very few mappings, it may make sense to implement the dictionary using an [association list](/source/Association_list), which is a [linked list](/source/Linked_list) of mappings. With this implementation, the time to perform the basic dictionary operations is linear in the total number of mappings. However, it is easy to implement and the constant factors in its running time are small.[3][11]

Another very simple implementation technique, usable when the keys are restricted to a narrow range, is direct addressing into an array: the value for a given key *k* is stored at the array cell *A*[*k*], or if there is no mapping for *k* then the cell stores a special [sentinel value](/source/Sentinel_value) that indicates the lack of a mapping. This technique is simple and fast, with each dictionary operation taking constant time. However, the space requirement for this structure is the size of the entire keyspace, making it impractical unless the keyspace is small.[5]

The two major approaches for implementing dictionaries are a [hash table](/source/Hash_table) or a [search tree](/source/Search_tree).[3][4][5][6]

### Hash table implementations

Main article: [Hash table](/source/Hash_table)

This graph compares the average number of [CPU cache](/source/CPU_cache) misses required to look up elements in large hash tables (far exceeding size of the cache) with chaining and [linear probing](/source/Linear_probing). Linear probing performs better due to better [locality of reference](/source/Locality_of_reference), though as the table gets full, its performance degrades drastically.

The most common general-purpose implementation of an associative array is a [hash table](/source/Hash_table): an [array](/source/Array_data_structure) combined with a [hash function](/source/Hash_function) that separates each key into a separate "bucket" of the array. The basic idea behind a hash table is that accessing an element of an array via its index is a simple, constant-time operation. Therefore, the average overhead of an operation for a hash table is only the computation of the key's hash, combined with accessing the corresponding bucket within the array. As such, hash tables usually perform in O(1) time, and usually outperform alternative implementations.

Hash tables must be able to handle [collisions](/source/Hash_collision): the mapping by the hash function of two different keys to the same bucket of the array. The two most widespread approaches to this problem are [separate chaining](/source/Separate_chaining) and [open addressing](/source/Open_addressing).[3][4][5][12] In separate chaining, the array does not store the value itself but stores a [pointer](/source/Pointer_(computer_programming)) to another container, usually an [association list](/source/Association_list), that stores all the values matching the hash. By contrast, in open addressing, if a hash collision is found, the table seeks an empty spot in an array to store the value in a deterministic manner, usually by looking at the next immediate position in the array.

Open addressing has a lower [cache miss](/source/Cache_miss) ratio than separate chaining when the table is mostly empty. However, as the table becomes filled with more elements, open addressing's performance degrades exponentially. Additionally, separate chaining uses less memory in most cases, unless the entries are very small (less than four times the size of a pointer).

### Tree implementations

Main article: [Search tree](/source/Search_tree)

#### Self-balancing binary search trees

Another common approach is to implement an associative array with a [self-balancing binary search tree](/source/Self-balancing_binary_search_tree), such as an [AVL tree](/source/AVL_tree) or a [red–black tree](/source/Red%E2%80%93black_tree).[13]

Compared to hash tables, these structures have both strengths and weaknesses. The worst-case performance of self-balancing binary search trees is significantly better than that of a hash table, with a time complexity in [big O notation](/source/Big_O_notation) of O(log *n*). This is in contrast to hash tables, whose worst-case performance involves all elements sharing a single bucket, resulting in O(*n*) time complexity. In addition, and like all binary search trees, self-balancing binary search trees keep their elements in order. Thus, traversing its elements follows a least-to-greatest pattern, whereas traversing a hash table can result in elements being in seemingly random order. Because they are in order, tree-based maps can also satisfy range queries (find all values between two bounds) whereas a hashmap can only find exact values. However, hash tables have a much better average-case time complexity than self-balancing binary search trees of O(1), and their worst-case performance is highly unlikely when a good [hash function](/source/Hash_function) is used.

A self-balancing binary search tree can be used to implement the buckets for a hash table that uses separate chaining. This allows for average-case constant lookup, but assures a worst-case performance of O(log *n*). However, this introduces extra complexity into the implementation and may cause even worse performance for smaller hash tables, where the time spent inserting into and balancing the tree is greater than the time needed to perform a [linear search](/source/Linear_search) on all elements of a linked list or similar data structure.[14][15]

#### Other trees

Associative arrays may also be stored in unbalanced [binary search trees](/source/Binary_search_tree) or in data structures specialized to a particular type of keys such as [radix trees](/source/Radix_tree), [tries](/source/Trie), [Judy arrays](/source/Judy_array), or [van Emde Boas trees](/source/Van_Emde_Boas_tree), though the relative performance of these implementations varies. For instance, Judy trees have been found to perform less efficiently than hash tables, while carefully selected hash tables generally perform more efficiently than adaptive radix trees, with potentially greater restrictions on the data types they can handle.[16] The advantages of these alternative structures come from their ability to handle additional associative array operations, such as finding the mapping whose key is the closest to a queried key when the query is absent in the set of mappings.

### Comparison

Underlying data structure Lookup or Removal Insertion Ordered average worst case average worst case Hash table O(1) O(n) O(1) O(n) No Self-balancing binary search tree O(log n) O(log n) O(log n) O(log n) Yes unbalanced binary search tree O(log n) O(n) O(log n) O(n) Yes Sequential container of key–value pairs (e.g. association list) O(n) O(n) O(1) O(1) No

## Ordered dictionary

The basic definition of a dictionary does not mandate an order. To guarantee a fixed order of enumeration, ordered versions of the associative array are often used. There are two senses of an ordered dictionary:

- The order of enumeration is always deterministic for a given set of keys by sorting. This is the case for tree-based implementations, one representative being the std::map (a tree map) container of C++.[17]

- The order of enumeration is key-independent and is instead based on the order of insertion. This is the case for the "ordered dictionary" in [.NET Framework](/source/.NET_Framework), the LinkedHashMap of [Java](/source/Java_(programming_language)) and [Python](/source/Python_(programming_language)).[18][19][20]

The latter is more common. Such ordered dictionaries can be implemented using an [association list](/source/Association_list), by overlaying a [doubly linked list](/source/Doubly_linked_list) on top of a normal dictionary, or by moving the actual data out of the sparse (unordered) array and into a dense insertion-ordered one.

## Language support

Main article: [Comparison of programming languages (associative array)](/source/Comparison_of_programming_languages_(associative_array))

Associative arrays can be implemented in any programming language as a package and many language systems provide them as part of their standard library. In some languages, they are not only built into the standard system, but have special syntax, often using array-like subscripting.

Built-in syntactic support for associative arrays was introduced in 1969 by [SNOBOL4](/source/SNOBOL), under the name "table".[21] [TMG](/source/TMG_(language)) offered tables with string keys and integer values. [MUMPS](/source/MUMPS) made multi-dimensional associative arrays, optionally persistent, its key data structure. [SETL](/source/SETL) supported them as one possible implementation of sets and maps. Most modern scripting languages, starting with [AWK](/source/AWK)[22] and including [Rexx](/source/Rexx), [Perl](/source/Perl), [PHP](/source/PHP), [Tcl](/source/Tcl_(programming_language)), [JavaScript](/source/JavaScript), [Maple](/source/Maple_(software)), [Python](/source/Python_(programming_language)), [Ruby](/source/Ruby_(programming_language)), [Wolfram Language](/source/Wolfram_Language), [Go](/source/Go_(programming_language)), and [Lua](/source/Lua_(programming_language)), support associative arrays as a primary container type. In many more languages, they are available as library functions without special syntax.

In [Smalltalk](/source/Smalltalk), [Objective-C](/source/Objective-C), [.NET](/source/.NET_Framework),[23] [Python](/source/Python_(programming_language)), [REALbasic](/source/REALbasic), [Swift](/source/Swift_(programming_language)), [VBA](/source/Visual_Basic_for_Applications) and [Delphi](/source/Delphi_(programming_language))[24] they are called *dictionaries*; in [Perl](/source/Perl) and [Ruby](/source/Ruby_(programming_language)) they are called *hashes*; in [C++](/source/C%2B%2B), [C#](/source/C_Sharp_(programming_language)), [Java](/source/Java_(programming_language)), [Go](/source/Go_(programming_language)), [Clojure](/source/Clojure), [Scala](/source/Scala_(programming_language)), [OCaml](/source/OCaml), [Haskell](/source/Haskell_(programming_language)) they are called *maps* (see [map (C++)](/source/Map_(C%2B%2B)), [unordered_map (C++)](/source/Unordered_map_(C%2B%2B)), and [Map](https://docs.oracle.com/en/java/javase/24/docs/api/java.base/java/util/Map.html)); in [Common Lisp](/source/Common_Lisp) and [Windows PowerShell](/source/Windows_PowerShell), they are called *hash tables* (since both typically use this implementation); in [Maple](/source/Maple_(software)) and Lua, they are called *tables*. In [PHP](/source/PHP) and [R](/source/R_(programming_language)), all arrays can be associative, except that the keys are limited to integers and strings. In JavaScript (see also [JSON](/source/JSON)), all objects behave as associative arrays with string-valued keys, while the Map and WeakMap types take arbitrary objects as keys. In Lua, they are used as the primitive building block for all data structures. In [Visual FoxPro](/source/Visual_FoxPro), they are called *Collections*. The [D language](/source/D_(programming_language)) also supports associative arrays.[25]

## Permanent storage

Main article: [Key–value store](/source/Key%E2%80%93value_store)

Many programs using associative arrays will need to store that data in a more permanent form, such as a [computer file](/source/Computer_file). A common solution to this problem is a generalized concept known as *archiving* or *[serialization](/source/Serialization)*, which produces a text or binary representation of the original objects that can be written directly to a file. This is most commonly implemented in the underlying object model, like .Net or Cocoa, which includes standard functions that convert the internal data into text. The program can create a complete text representation of any group of objects by calling these methods, which are almost always already implemented in the base associative array class.[26]

For programs that use very large data sets, this sort of individual file storage is not appropriate, and a [database management system](/source/Database_management_system) (DB) is required. Some DB systems natively store associative arrays by serializing the data and then storing that serialized data and the key. Individual arrays can then be loaded or saved from the database using the key to refer to them. These [key–value stores](/source/Key%E2%80%93value_database) have been used for many years and have a history as long as that of the more common [relational database](/source/Relational_database) (RDBs), but a lack of standardization, among other reasons, limited their use to certain niche roles. RDBs were used for these roles in most cases, although saving objects to a RDB can be complicated, a problem known as [object-relational impedance mismatch](/source/Object-relational_impedance_mismatch).

After approximately 2010, the need for high-performance databases suitable for [cloud computing](/source/Cloud_computing) and more closely matching the internal structure of the programs using them led to a renaissance in the key–value store market. These systems can store and retrieve associative arrays in a native fashion, which can greatly improve performance in common web-related workflows.

## See also

- [Computer programming portal](https://en.wikipedia.org/wiki/Portal:Computer_programming)

- [Tuple](/source/Tuple)

- [Function (mathematics)](/source/Function_(mathematics))

## References

1. **[^](#cite_ref-1)** Collins, Graham; Syme, Donald (1995). "A theory of finite maps". *Higher Order Logic Theorem Proving and Its Applications*. Lecture Notes in Computer Science. Vol. 971. pp. 122–137. [doi](/source/Doi_(identifier)):[10.1007/3-540-60275-5_61](https://doi.org/10.1007%2F3-540-60275-5_61). [ISBN](/source/ISBN_(identifier)) [978-3-540-60275-0](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-60275-0).

1. **[^](#cite_ref-2)** Andersson, Arne (1989). "Optimal Bounds on the Dictionary Problem". *Proc. Symposium on Optimal Algorithms*. Lecture Notes in Computer Science. Vol. 401. Springer Verlag. pp. 106–114. [doi](/source/Doi_(identifier)):[10.1007/3-540-51859-2_10](https://doi.org/10.1007%2F3-540-51859-2_10). [ISBN](/source/ISBN_(identifier)) [978-3-540-51859-4](https://en.wikipedia.org/wiki/Special:BookSources/978-3-540-51859-4).

1. ^ [***a***](#cite_ref-gt_3-0) [***b***](#cite_ref-gt_3-1) [***c***](#cite_ref-gt_3-2) [***d***](#cite_ref-gt_3-3) [***e***](#cite_ref-gt_3-4) [Goodrich, Michael T.](/source/Michael_T._Goodrich); [Tamassia, Roberto](/source/Roberto_Tamassia) (2006), "9.1 The Map Abstract Data Type", *Data Structures & Algorithms in Java* (4th ed.), Wiley, pp. 368–371

1. ^ [***a***](#cite_ref-ms_4-0) [***b***](#cite_ref-ms_4-1) [***c***](#cite_ref-ms_4-2) [***d***](#cite_ref-ms_4-3) [Mehlhorn, Kurt](/source/Kurt_Mehlhorn); [Sanders, Peter](/source/Peter_Sanders_(computer_scientist)) (2008), "4 Hash Tables and Associative Arrays", [*Algorithms and Data Structures: The Basic Toolbox*](http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf) (PDF), Springer, pp. 81–98, [archived](https://web.archive.org/web/20140802025330/http://people.mpi-inf.mpg.de/~mehlhorn/ftp/Toolbox/HashTables.pdf) (PDF) from the original on 2014-08-02

1. ^ [***a***](#cite_ref-clrs_5-0) [***b***](#cite_ref-clrs_5-1) [***c***](#cite_ref-clrs_5-2) [***d***](#cite_ref-clrs_5-3) [Cormen, Thomas H.](/source/Thomas_H._Cormen); [Leiserson, Charles E.](/source/Charles_E._Leiserson); [Rivest, Ronald L.](/source/Ron_Rivest); [Stein, Clifford](/source/Clifford_Stein) (2001), "11 Hash Tables", *[Introduction to Algorithms](/source/Introduction_to_Algorithms)* (2nd ed.), [MIT Press](/source/MIT_Press) and [McGraw-Hill](/source/McGraw-Hill), pp. 221–252, [ISBN](/source/ISBN_(identifier)) [0-262-03293-7](https://en.wikipedia.org/wiki/Special:BookSources/0-262-03293-7).

1. ^ [***a***](#cite_ref-dietzfelbinger_6-0) [***b***](#cite_ref-dietzfelbinger_6-1) Dietzfelbinger, M., Karlin, A., Mehlhorn, K., Meyer auf der Heide, F., Rohnert, H., and Tarjan, R. E. 1994. ["Dynamic Perfect Hashing: Upper and Lower Bounds"](http://www.arl.wustl.edu/~sailesh/download_files/Limited_Edition/hash/Dynamic%20Perfect%20Hashing-%20Upper%20and%20Lower%20Bounds.pdf) [Archived](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) 2016-03-04 at the [Wayback Machine](/source/Wayback_Machine). SIAM J. Comput. 23, 4 (Aug. 1994), 738-761. [http://portal.acm.org/citation.cfm?id=182370](http://portal.acm.org/citation.cfm?id=182370) [doi](/source/Doi_(identifier)):[10.1137/S0097539791194094](https://doi.org/10.1137%2FS0097539791194094)

1. **[^](#cite_ref-Michie1968_7-0)** Michie, Donald (1968). ["'Memo' Functions and Machine Learning"](https://www.cs.utexas.edu/users/hunt/research/hash-cons/hash-cons-papers/michie-memo-nature-1968.pdf) (PDF). *[Nature](/source/Nature_(journal))*. **218** (5136): 19–22. [Bibcode](/source/Bibcode_(identifier)):[1968Natur.218...19M](https://ui.adsabs.harvard.edu/abs/1968Natur.218...19M). [doi](/source/Doi_(identifier)):[10.1038/218019a0](https://doi.org/10.1038%2F218019a0). [S2CID](/source/S2CID_(identifier)) [4265138](https://api.semanticscholar.org/CorpusID:4265138).

1. **[^](#cite_ref-decorator_8-0)** [Goodrich & Tamassia (2006)](#CITEREFGoodrichTamassia2006), pp. 597–599.

1. ^ [***a***](#cite_ref-Black_9-0) [***b***](#cite_ref-Black_9-1) Black, Paul E.; Stewart, Rob (2 November 2020). ["dictionary"](https://xlinux.nist.gov/dads/HTML/dictionary.html). *Dictionary of Algorithms and Data Structures*. Retrieved 26 January 2022.

1. **[^](#cite_ref-10)** [Goodrich & Tamassia (2006)](#CITEREFGoodrichTamassia2006), pp. 389–397.

1. **[^](#cite_ref-11)** ["When should I use a hash table instead of an association list?"](http://www.faqs.org/faqs/lisp-faq/part2/section-2.html). lisp-faq/part2. 1996-02-20.

1. **[^](#cite_ref-fklm_12-0)** [Klammer, F.](https://en.wikipedia.org/w/index.php?title=F._Klammer&action=edit&redlink=1); [Mazzolini, L.](https://en.wikipedia.org/w/index.php?title=L._Mazzolini&action=edit&redlink=1) (2006), "Pathfinders for associative maps", *Ext. Abstracts GIS-l 2006*, GIS-I, pp. 71–74.

1. **[^](#cite_ref-13)** Joel Adams and Larry Nyhoff. ["Trees in STL"](http://cs.calvin.edu/books/c++/intro/3e/WebItems/Ch15-Web/STL-Trees.pdf). Quote: "The Standard Template library ... some of its containers -- the set<T>, map<T1, T2>, multiset<T>, and multimap<T1, T2> templates -- are generally built using a special kind of *self-balancing binary search tree* called a *red–black tree*."

1. **[^](#cite_ref-knuth_14-0)** [Knuth, Donald](/source/Donald_Knuth) (1998). *The Art of Computer Programming*. Vol. 3: *Sorting and Searching* (2nd ed.). Addison-Wesley. pp. 513–558. [ISBN](/source/ISBN_(identifier)) [0-201-89685-0](https://en.wikipedia.org/wiki/Special:BookSources/0-201-89685-0).

1. **[^](#cite_ref-15)** Probst, Mark (2010-04-30). ["Linear vs Binary Search"](https://schani.wordpress.com/2010/04/30/linear-vs-binary-search/). Retrieved 2016-11-20.

1. **[^](#cite_ref-16)** Alvarez, Victor; Richter, Stefan; Chen, Xiao; Dittrich, Jens (April 2015). "A comparison of adaptive radix trees and hash tables". *2015 IEEE 31st International Conference on Data Engineering*. Seoul, South Korea: IEEE. pp. 1227–1238. [doi](/source/Doi_(identifier)):[10.1109/ICDE.2015.7113370](https://doi.org/10.1109%2FICDE.2015.7113370). [ISBN](/source/ISBN_(identifier)) [978-1-4799-7964-6](https://en.wikipedia.org/wiki/Special:BookSources/978-1-4799-7964-6). [S2CID](/source/S2CID_(identifier)) [17170456](https://api.semanticscholar.org/CorpusID:17170456).

1. **[^](#cite_ref-17)** ["std::map"](https://en.cppreference.com/w/cpp/container/map). *en.cppreference.com*.

1. **[^](#cite_ref-18)** ["OrderedDictionary Class (System.Collections.Specialized)"](https://docs.microsoft.com/en-us/dotnet/api/system.collections.specialized.ordereddictionary?view=netframework-4.8). *MS Docs*.

1. **[^](#cite_ref-19)** ["LinkedHashMap"](https://docs.oracle.com/en/java/javase/19/docs/api/java.base/java/util/LinkedHashMap.html).

1. **[^](#cite_ref-20)** ["collections — Container datatypes — Python 3.9.0a3 documentation"](https://docs.python.org/3.9/library/collections.html#collections.OrderedDict). *docs.python.org*.

1. **[^](#cite_ref-21)** [Griswold, Ralph E.](/source/Ralph_E._Griswold) (August 1978). "A history of the SNOBOL programming languages". *SIGPLAN Not*. **13** (8): 275–308, See p. 289. [doi](/source/Doi_(identifier)):[10.1145/960118.808393](https://doi.org/10.1145%2F960118.808393). Tables, which provided a kind of associative data structure, had been suggested a number of times, notably by [Doug McIlroy](/source/Doug_McIlroy) and Mike Shapiro. It was Doug's persistence that resulted in their addition to SNOBOL4 in mid 1969, at a very late stage in the development of SNOBOL4 ...

1. **[^](#cite_ref-22)** ["/usr/doc/awk"](https://github.com/dspinellis/unix-history-repo/blob/Research-V7/usr/doc/awk). *Unix History Repository §[Research-V7](/source/Version_7_Unix)*. lines 935–9 – via github. Array elements may be named by non-numeric values, which gives *awk* a capability rather like the associative memory of Snobol tables.

1. **[^](#cite_ref-23)** ["Dictionary<TKey, TValue> Class"](http://msdn.microsoft.com/en-us/library/xfhwa508.aspx). MSDN.

1. **[^](#cite_ref-24)** ["System.Generics.Collections.TDictionary - RAD Studio API Documentation"](http://docwiki.embarcadero.com/Libraries/Tokyo/en/System.Generics.Collections.TDictionary). *docwiki.embarcadero.com*. Retrieved 2017-04-18.

1. **[^](#cite_ref-25)** ["Associative Arrays, the D programming language"](http://dlang.org/hash-map.html). Digital Mars.

1. **[^](#cite_ref-26)** ["Archives and Serializations Programming Guide"](https://developer.apple.com/library/prerelease/ios/documentation/Cocoa/Conceptual/Archiving/Archiving.html#//apple_ref/doc/uid/10000047i), Apple Inc., 2012

## External links

Look up ***[associative array](https://en.wiktionary.org/wiki/associative_array)*** in Wiktionary, the free dictionary.

- [NIST's Dictionary of Algorithms and Data Structures: Associative Array](https://xlinux.nist.gov/dads/HTML/assocarray.html)

v t e Data structures Types Collection Container Abstract Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set Arrays Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix Linked Association list Linked list Skip list Unrolled linked list XOR linked list Trees B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Rope Trie Hash tree Graphs Binary decision diagram Directed acyclic graph Directed acyclic word graph List of data structures

v t e Data types Uninterpreted Bit Byte Trit Tryte Word Bit array Numeric Arbitrary-precision or bignum Complex Decimal Fixed point Block floating point Floating point Reduced precision Minifloat Half precision bfloat16 Single precision Double precision Quadruple precision Octuple precision Extended precision Long double Integer signedness Interval Rational Reference Address physical virtual Pointer Text Character String null-terminated Composite Algebraic data type generalized Array Associative array Class Dependent Equality Inductive Intersection List Object metaobject Option type Product Record or Struct Refinement Set Union tagged Other Any type Boolean Bottom type Collection Enumerated type Exception Function type Opaque data type Recursive data type Semaphore Stream Strongly typed identifier Type class Empty type Unit type Void Related topics Value Abstract data type Boxing Data structure Generic Kind metaclass Parametric polymorphism Primitive data type Interface Subtyping Type constructor Type conversion Type system Type theory Variable

---
Adapted from the Wikipedia article [Associative array](https://en.wikipedia.org/wiki/Associative_array) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Associative_array?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.