An associative array (also associative container, map, mapping, hash, dictionary, finite map, lookup table, and in query-processing an index or index file) is an abstract data type composed of a collection of keys and a collection of values, where each key is associated with one value. In Computer science, a lookup table is a Data structure, usually an Array or Associative array, often used to replace a runtime computation with In Computing, an abstract data type ( ADT) is a specification of a set of data and the set of operations that can be performed on the data The operation of finding the value associated with a key is called a lookup or indexing, and this is the most important operation supported by an associative array. The relationship between a key and its value is sometimes called a mapping or binding. For example, if the value associated with the key "bob" is 7, we say that our array maps "bob" to 7. Associative arrays are very closely related to the mathematical concept of a function with a finite domain. The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function In Mathematics, the domain of a given function is the set of " Input " values for which the function is defined As a consequence, a common and important use of associative arrays is in memoization. In Computing, memoization is an optimization technique used primarily to speed up Computer programs by having function calls avoid repeating

From the perspective of a programmer using an associative array, it can be viewed as a generalization of an array: While a regular array maps Integer and/or Enumerated types to arbitrarily typed objects (integers, strings, pointers, and, in an OO sense, objects), an associative array maps arbitrarily typed objects to arbitrarily typed objects. In Computer science an array is a Data structure consisting of a group of elements that are accessed by indexing. The integers (from the Latin integer, literally "untouched" hence "whole" the word entire comes from the same origin but via French In Computer programming, an enumerated type is a Data type (usually user-defined consisting of a set of named constants called enumerators. Object-oriented programming (OOP is a Programming paradigm that uses " objects " and their interactions to design applications and computer programs In its simplest embodiment an object is an allocated region of storage (Implementations of the two data structures, though, are usually considerably different. A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently )

The operations that are usually defined for an associative array are:

• Add: Bind a new key to a new value
• Reassign: Bind an old key to a new value
• Remove: Unbind a key from a value and remove the key from the key set
• Lookup: Find the value (if any) that is bound to a key

Contents 1 Examples 2 Data structures for associative arrays 2.1 Efficient representations 2.2 Association lists 2.3 Specialized representations 2.4 Multimap 3 Language support 4 References 5 External links

Examples

One can think of a telephone book as an example of an associative array, where names are the keys and phone numbers are the values. Using the usual array-like notation, we might write

telephone['ada']='01-1234-56'
telephone['bert']='02-4321-56'

and so on. These entries can be thought of as two records in a database table:

name	telephone
ada	01-1234-56
bert	02-4321-56

Another example would be a dictionary where words are the keys and definitions are the values.

dictionary['toad']='four legged amphibian'
dictionary['cow']='female four-legged domesticated mammalian ruminant'

Since a database equivalent is that of a table containing precisely two fields - key and value, we can use an associative array to store any information which can be held in this form.

capital['england']='london'
capital['france']='paris'

bossof['subeditor']='editor'
bossof['reporter']='subeditor'

salary['editor']=50000
salary['reporter']=30000

Data structures for associative arrays

Associative arrays are usually used when lookup is the most frequent operation. For this reason, implementations are usually designed to allow speedy lookup, at the expense of slower insertion and a larger storage footprint than other data structures (such as association lists). An associative array (also associative container, map, mapping, hash, dictionary, finite map, and in query-processing an

Efficient representations

There are two main efficient data structures used to represent associative arrays, the hash table and the self-balancing binary search tree (such as a red-black tree or an AVL tree). In Computer science, a hash table, or a hash map, is a Data structure that associates keys with values. In Computer science, a self-balancing binary search tree or height-balanced binary search tree is a Binary search tree that attempts to keep its height Skip lists are also an alternative, though relatively new and not as widely used. Invented in 1990 by William Pugh, a skip list is a probabilistic Data structure, based on multiple parallel sorted Linked lists with efficiency B-trees (and variants) can also be used, and are commonly used when the associative array is too large to reside entirely in memory, for instance in a simple database. In Computer science, a B-tree is a Tree data structure that keeps data sorted and allows searches insertions and deletions in logarithmic amortized Relative advantages and disadvantages include:

• Hash tables have faster average lookup and insertion time (O(1)) compared to a balanced binary search tree's O(log n).
• Hash tables have seen extensive use in real-time systems, but trees can be useful in high-security realtime systems where untrusted users may deliberately supply information that triggers worst-case performance in a hash table, although careful design can remove that issue. In Computer science, real-time computing (RTC is the study of hardware and software systems that are subject to a "real-time constraint"—i Hash tables shine in very large arrays, where O(1) performance is important. Skip lists have worst-case operation time of O(n), but average-case of O(log n), with much less insertion and deletion overhead than balanced binary trees.
• Hash tables can have more compact storage for small value types, especially when the values are bits.
• There are simple persistent versions of balanced binary trees, which are especially prominent in functional languages. In Computing, a persistent data structure is a Data structure which always preserves the previous version of itself when it is modified such data structures In Computer science, functional programming is a Programming paradigm that treats Computation as the evaluation of mathematical functions and
• Building a hash table requires a reasonable hash function for the key type, which can be difficult to write well, while balanced binary trees and skip lists only require a total ordering on the keys. A hash function is any well-defined procedure or mathematical function for turning some kind of Data into a relatively small integer, that may In Mathematics and Set theory, a total order, linear order, simple order, or (non-strict ordering is a Binary relation On the other hand, with hash tables the data may be cyclically or partially ordered without any problems. In combinatorial Mathematics, a cyclic order on a set X with n elements is an arrangement of X as on a clock face for an n In Mathematics, especially Order theory, a partially ordered set (or poset) formalizes the intuitive concept of an ordering sequencing or arrangement
• Balanced binary trees and skip lists preserve ordering — allowing one to efficiently iterate over the keys in order or to efficiently locate an association whose key is nearest to a given value. Hash tables do not preserve ordering and therefore cannot perform these operations as efficiently (they require the data to be sorted in a separate step).
• Balanced binary trees can be easily adapted to efficiently assign a single value to a large ordered range of keys, or to count the number of keys in an ordered range. (With n elements in the array and performing the operation on a contiguous range of m keys, a balanced binary tree will take O(log n + m) time while a hash table would need O(n) time as it needs to search the entire table. )
• In cases where the number of elements in the array fluctuates a lot, trees have other benefits over a hash table. A hash table of a given size can only hold some number of keys before it becomes inefficient, and if the size grows too much it must allocate a new backing store, rehash all the keys, and copy the data to the larger table; this takes O(n) time but can be amortised over multiple access, which retains the O(1) property. A balanced search tree will always take O(log n) time for insertion. Once a hash table grows, if the size decreases the keys can be again rehashed and copied to a smaller space. In contrast, the memory demands of a tree grow and shrink in smaller steps with the number of elements currently in the tree, potentially causing more chance of fragmentation of the program's heap. In Computer storage, fragmentation is a phenomenon in which storage space is used inefficiently reducing storage capacity

Association lists

A simple but generally inefficient type of associative array is an association list, often called an alist for short, which simply stores a linked list of key-value pairs. In Computer science, a linked list is one of the fundamental Data structures and can be used to implement other data structures Each lookup does a linear search through the list looking for a key match. In Computer science, linear search is a Search algorithm, also known as sequential search, that is suitable for searching a list of data for a particular

Strong advantages of association lists include:

• No knowledge is needed about the keys, such as an order or a hash function.
• For small associative arrays, common in some applications, association lists can take less time and space than other data structures.
• Insertions are done in constant time by adding the new association to the head of the list.

Specialized representations

If the keys have a specific type, one can often use specialized data structures to gain performance. For example, integer-keyed maps can be implemented using Patricia trees or Judy arrays, and are useful space-saving replacements for sparse arrays. A radix tree, Patricia trie / tree, or crit bit tree is a specialized Set data structure based on the Trie that is used to store a set In Computer science and Software engineering, a Judy array is a complex but very fast Associative array Data structure for storing and looking Because this type of data structure can perform longest-prefix matching, they're particularly useful in applications where a single value is assigned to most of a large range of keys with a common prefix except for a few exceptions, such as in routing tables. In Computer networking a routing table, or Routing Information Base (RIB, is an electronic table (file or database type object that is stored in a

String-keyed maps can avoid extra comparisons during lookups by using tries. In Computer science, a trie, or prefix tree, is an ordered tree Data structure that is used to store an Associative array where

Multimap

Main article: Multimap (data structure)

A variation of the map (associative array) is the multimap, which is the same as map data structures, but allows a key to be mapped to more than one value. A multimap is a generalization of a map or associative array Abstract data type in which more than one value may be associated with and returned for a given key Formally, a multimap can be thought of as a regular associative array that maps unique keys to nonempty multisets of values, although actual implementation may vary. C++'s Standard Template Library provides the "multimap" container for the sorted multimap, SGI's STL provides the "hash_multimap" container, which implements a multimap using a hash table, and some varieties of LPC have built-in multimap support. C++ (" C Plus Plus " ˌsiːˌplʌsˈplʌs is a general-purpose Programming language. The Standard Template Library ( STL) is a software library partially included in the C++ Standard Library. The Standard Template Library ( STL) is a software library partially included in the C++ Standard Library. The LPC programming language is an Object-oriented Programming language derived from C and developed originally by Lars Pensjö to facilitate

Language support

Main article: Comparison of programming languages (mapping)

Associative arrays can be implemented in any programming language as a package and many language systems provide them as part of their standard library. Language support The following is a comparison of associative arrays (also "mapping" "hash" and "dictionary" in various programming languages In some languages, they are not only built into the standard system, but have special syntax, often array-like subscripting.

Built-in syntactic support for associative arrays was introduced by Snobol4, under the name "table". SNOBOL ( String Oriented Symbolic Language) is a Computer Programming language developed between 1962 and 1967 at AT&T Bell Laboratories MUMPS made multi-dimensional associative arrays, optionally persistent, its key data structure. Mumps or epidemic Parotitis is a Viral disease of the Human species SETL supported them as one possible implementation of sets and maps. SETL (SET Language is a very-high level Programming language based on the mathematical Theory of sets. Most modern scripting languages, starting with awk and including Perl, tcl, Javascript, Python, and Ruby, support associative arrays as a primary container type. AWK is a general purpose Programming language that is designed for processing text-based data either in files or data streams and was created at Bell Labs in the 1970s NOTES FOR EDITORS "Perl" is not an acronym (read the "Name" section below Tcl (originally from "Tool Command Language" but nonetheless conventionally rendered as "Tcl" rather than "TCL" pronounced as " tickle " JavaScript is a Scripting language most often used for Client-side web development Python is a general-purpose High-level programming language. Its design philosophy emphasizes programmer productivity and code readability Ruby is a dynamic, reflective, general purpose Object-oriented programming language that combines syntax inspired by Perl with Smalltalk

In many more languages, they are available as library functions without special syntax.

Associative arrays have a variety of names. In Smalltalk, Objective-C and Python they are called dictionaries; in Perl and Ruby they are called hashes; in C++ and Java they are called maps (see std::map and Map) and in Common Lisp and Windows PowerShell they are called hashtables (since both typically use this implementation). Smalltalk is an object-oriented, dynamically typed, reflective programming language. Objective-C is a reflective, object-oriented Programming language which adds Smalltalk -style messaging to C. Python is a general-purpose High-level programming language. Its design philosophy emphasizes programmer productivity and code readability NOTES FOR EDITORS "Perl" is not an acronym (read the "Name" section below Ruby is a dynamic, reflective, general purpose Object-oriented programming language that combines syntax inspired by Perl with Smalltalk C++ (" C Plus Plus " ˌsiːˌplʌsˈplʌs is a general-purpose Programming language. The class std map is a standard C++ container. It is a sorted Associative array, which is a data structure Common Lisp, commonly abbreviated CL, is a dialect of the Lisp Programming language, published in ANSI standard document Information Windows PowerShell is an extensible command-line shell and associated Scripting language from Microsoft In PHP all arrays can be associative, except that the keys are limited to integers and strings and can only be a single level of subscripts. PHP is a computer Scripting language. Originally designed for producing Dynamic web pages it has evolved to include a Command line interface capability

In the scripting language Lua, associative arrays, called tables, are used as the primitive building block for all data structures, even arrays. In Computing, Lua (ˈluːa LOO-ah is a lightweight, reflective, imperative and procedural Programming language, Likewise, in JavaScript, all objects are associative arrays. JavaScript is a Scripting language most often used for Client-side web development In MUMPS, the associative arrays are typically stored as B-trees. In Computer science, a B-tree is a Tree data structure that keeps data sorted and allows searches insertions and deletions in logarithmic amortized

References

External links

• TreeDictionary<K,V> Implementation in C#
• NIST's Dictionary of Algorithms and Data Structures: Associative Array
• NIST's Dictionary of Algorithms and Data Structures: Association List
• SGI STL page on Associative Containers
• SGI STL page on std::map
• SGI STL page on std::hash_map

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic