An associative array, also called a map, dictionary, symbol table or key-value store, is an abstract data type that holds a collection of key and value pairs in which each possible key appears at most once. It supports three basic operations, inserting a pair, removing a pair by its key and looking up the value bound to a key, and in mathematical terms it is a function with a finite domain. The classic dictionary problem is how to build efficient data structures that implement it, and the two major solutions are hash tables and search trees, with direct addressing into an array or an association list suitable for narrow key ranges or very small collections. Many programming languages include associative arrays as a primitive type, others provide them in libraries, and content-addressable memory gives direct hardware support. They underlie patterns such as memoization.
Facts
Core PrincipleAn array whose indices are not just integers but may be arbitrary strings, also called a hash, map or dictionary. 1 Connections
In Field
Source Associative array (Wikipedia)
Long-Form Articles
Sources
1. Free On-line Dictionary of Computing (FOLDOC): associative array (FOLDOC)
Free On-line Dictionary of Computing (FOLDOC)Entry textQuote, Entry text
An array where the indices are not just integers but may be arbitrary strings.
Associative array (Wikipedia)
In Field: Algorithms and Complexity Theory, Lead, dictionary problem
The dictionary problem is the classic problem of designing efficient data structures that implement associative arrays.
In Group: Hashing and Probabilistic Structures, Implementation
The two major approaches for implementing dictionaries are a hash table or a search tree.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.