⏾ Concept Map

Associative Array ○꠹ Entries

↩ 🔵 🔵 🔵

Primary

၊၊||၊|။

Associative Array ○꠹｜Definition｜1st｜20260103213523-00-⌔

Associative array - Wikipedia

Associative array

In computer science, an associative array, key-value store, map, symbol table, or dictionary is an abstract data type that stores a collection of key/value pairs, such that each possible key appears at most once in the collection. In mathematical terms, an associative array is a function with finite domain.1 It supports ‘lookup’, ‘remove’, and ‘insert’ operations.

The dictionary problem is the classic problem of designing efficient data structures that implement associative arrays.2 The two major solutions to the dictionary problem are hash tables and search trees.3456 It is sometimes also possible to solve the problem using directly addressed arrays, binary search trees, or other more specialized structures.

Many programming languages include associative arrays as primitive data types, while many other languages provide 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 programming patterns as memoization7 and the decorator pattern.8 The name does not come from the associative property known in mathematics. Rather, it arises from the association of values with keys. It should not be confused with associative processors.

Printed 2026-06-28.

(echo:: @ ᯤ)

Footnotes

  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. Springer. pp. 122–137. doi:10.1007/3-540-60275-5_61. ISBN 978-3-540-60275-0. ↩

  2. Andersson, Arne (1989). “Optimal Bounds on the Dictionary Problem”. Proc. Symposium on Optimal Algorithms. Lecture Notes in Computer Science. Vol. 401. Springer. pp. 106–114. doi:10.1007/3-540-51859-2_10. ISBN 978-3-540-51859-4. ↩

  3. Goodrich, Michael T.; Tamassia, Roberto (2006), “§9.1 The Map Abstract Data Type”, Data Structures & Algorithms in Java (4th ed.), Wiley, pp. 368–371, ISBN 978-0-471-73884-8, OCLC 61822092 ↩

  4. Mehlhorn, Kurt; Sanders, Peter (2008), “4. Hash Tables and Associative Arrays”, Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 81–98, doi:10.1007/978-3-540-77978-0_4, ISBN 978-3-540-77977-3, OCLC 272306813, archived (PDF) from the original on 2014-08-02 ↩

  5. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), “11. Hash Tables”, Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 221–252, ISBN 0-262-03293-7. ↩

  6. Dietzfelbinger, M.; Karlin, A.; Mehlhorn, K.; Meyer auf der Heide, F.; Rohnert, H.; Tarjan, R.E. (August 1994). “Dynamic Perfect Hashing: Upper and Lower Bounds” (PDF). SIAM J. Comput. 23 (4): 738–761. doi:10.1137/S0097539791194094. Archived from the original (PDF) on 2016-03-04. ↩

  7. Michie, Donald (1968). “‘Memo’ Functions and Machine Learning” (PDF). Nature. 218 (5136): 19–22. Bibcode:1968Natur.218…19M. doi:10.1038/218019a0. S2CID 4265138. ↩

  8. Goodrich & Tamassia (2006), pp. 597–599. ↩

Link to original

Secondary

• • •