Associative Array Data Structure
An Associative Array Data Structure is a collection data structure that facilitates the storage, update, and retrieval of key-value pairs with the same key.
- AKA: Key-Value Table, Associative Lookup Container, Map Structure, Dictionary Structure.
- Context:
- It can be implemented as a Hash Table, a Self-Balancing Binary Search Tree, ...
- It can range from being a Locally Associative Dictionary to being a Globally Associative Dictionary.
- …
- Example(s):
- Counter-Example(s):
- See: Lookup Table, Search Tree, Decorator Pattern.
References
2016
- (Wikipedia, 2016) ⇒ http://en.wikipedia.org/wiki/Collection_%28computing%29#Associative_arrays Retrieved:2016-9-17.
- In an associative array (or map, dictionary, lookup table), like in a dictionary, a lookup on a key (like a word) provides a value (like a definition). The value might be a reference to a compound data structure. A hash table is usually an efficient implementation, and thus this data type is often known as a "hash".
- (Wikipedia, 2016) ⇒ https://en.wikipedia.org/wiki/associative_array Retrieved:2016-9-17.
- In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.
Operations associated with this data type allow:
- the addition of a pair to the collection
- the removal of a pair from the collection
- the modification of an existing pair
- the lookup of a value associated with a particular key
- The dictionary problem is a classic computer science problem: the task of designing a data structure that maintains a set of data during 'search', 'delete', and 'insert' operations. The two major solutions to the dictionary problem are a hash table or a search tree. [1]
In some cases it is 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, and they are available in software libraries for many others. 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 memoization and the decorator pattern.[2]
- In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.
- ↑ 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". SIAM J. Comput. 23, 4 (Aug. 1994), 738-761.
http://portal.acm.org/citation.cfm?id=182370
- ↑ , pp. 597–599.
2013
- http://rosettacode.org/wiki/Associative_array
- An associative array is a collection indexed by arbitrary data types, not just small integers. Whereas an array is typically implemented as many same-sized items stored in a contiguous block of memory, an associative array must be implemented via a more complex data structure, such as a hash table, a list, or some other type of map.
The terminology and semantics of these vary among different programming languages. For example in Perl and Ruby they are called “hashes” (from abbreviating “hash table”, the underlying implementation) while in Python, Objective-C, and Smalltalk they are called “dictionaries” (by analogy to the normal English usage of the term: an indexed reference by which keys (words) are associated with values (definitions)). In Lua they are called “tables”. In Java, C++, and Go they are called “maps”.
The semantics differ as well. While all of these allow the programmer to associate some sort of key with some sort of value they can differ considerably in how they evaluate the key and what sorts of values can be stored.
For example in awk and Perl the keys are evaluated (as “scalars” in Perl terminology). Thus the the keys "1" (a string) and 1 (an integer) and 1.0 (a real or floating point number) would all evaluate into equivalent keys. By contrast these would each be distinct in Python. In a Python dictionary any immutable object (strings, integer, floats) and any object/class which implements the __hash__ special method can be used as a key. Values can be references to any objects (including functions, classes, class methods which are all "first class objects" in that language). In Lua, a table is a complex data structure which can be used to implement arrays, objects and associative arrays (integer key values are implicitly treated like indices into a virtual array, those with values that reference functions are methods, those which reference other types of objects are attributes or members).
Associative arrays are used as the underlying data structure for objects in a number of languages. Python objects normally have a visible __dict__ attribute by which its methods and other attributes can be accessed indirectly. PHP objects can be cast into associative arrays, and vice versa, with the keys and values corresponding to property names and values of the object. Perl objects are references of (usually) hashes. And (as described above) Lua objects are implemented as tables (functions and other objects are “first class objects” which an be assigned to keys and passed around as arguments, as with Python). Similarly, in JavaScript the concepts of associative array and object are the same, since JavaScript lacks a separate "associative array" type, and object attributes can be accessed using subscript operator with the attribute name as a string.
- An associative array is a collection indexed by arbitrary data types, not just small integers. Whereas an array is typically implemented as many same-sized items stored in a contiguous block of memory, an associative array must be implemented via a more complex data structure, such as a hash table, a list, or some other type of map.
2010
- (Odersky et al., 2010) ⇒ Martin Odersky, Lex Spoon, and Bill Venners. (2010). “Programming in Scala, 2nd edition.” Artima. ISBN:0981531644
- QUOTE: One common characteristic of these languages, which is relevant for the example above, is that they each support an "associative map" construct in the syntax of the language. Associative maps are very useful because they help keep programs legible and concise. However, sometimes you might not agree with their "one size fits all" philosophy, because you need to control the properties of the maps you use in your program in a more fine-grained way. Scala gives you this fine-grained control if you need it, because maps in Scala are not language syntax. They are library abstractions that you can extend and adapt.
2009
- http://en.wikipedia.org/wiki/Associative_array
- … From the perspective of a computer programmer, an associative array can be viewed as a generalization of an array. While a regular array maps an integer key (index) to a value of arbitrary data type, an associative array's keys can also be arbitrarily typed. In some programming languages, the keys of an associative array do not even need to be of the same type.