|
|
Associative ArrayIn computing, an associative array, also known as a map, lookup table, or dictionary, is an abstract data type very closely related to the mathematical concept of a function with a finite domain. Conceptually, an associative array is composed of a collection of keys and a collection of values, and each key is associated with one value. 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. 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 integers to arbitrarily typed objects (integers, strings, pointers, and, in an OO sense, objects), an associative array maps arbitrarily typed objects to arbitrarily typed objects. (Implementations of the two data structures, though, may be considerably different.) 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 it from the key set
- Lookup: Find the value (if any) that is bound to a key
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. Another example would be a dictionary where words are the keys and definitions are the values. A database is a sort of generalized associative array. 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). Efficient representations There are two main efficient data structures used to represent associative arrays, the hash table and the self-balancing binary search tree. Skip lists are also an alternative, though relatively new and not as widely used. Relative advantages and disadvantages include: - Hash tables have faster average lookup and insertion time (O(1)), while balanced binary trees have faster worst-case lookup and insertion time (O(log n) instead of O(n)). These make trees more useful in real-time and interactive systems, and in high-security systems where untrusted users may deliberately supply information that triggers worst-case performance in a hash table. Hash tables are more useful for very large arrays, where O(1) performance is important. Skip lists have worst-case operation time of O(n), but average-case of O(logn), with much less insertion and deletion overhead than balanced binary trees.
- Hash tables 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.
- Building a hash table requires a good hash function for the key type, which can be difficult to write, while balanced binary trees and skip lists only require a total ordering on the keys.
- Balanced binary trees and skip lists preserve ordering -- allowing one to efficiently iterate over the keys in order. Hash tables do not preserve ordering.
- 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.
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. Each lookup does a linear search through the list looking for a key match. 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 consing 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. 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. String-keyed maps can avoid extra comparisons during lookups by using tries. Language support Associative arrays are known by many names in different programming languages. In Smalltalk and Python they are called dictionaries; in Perl and Ruby they are called hashes; in Java they are called Maps http://java.sun.com/j2se/1.4.2/docs/api/java/util/Map.html and in Common Lisp they are called hash tables. "Hash table" is also the name of the most common data structure used to store an associative array. In the scripting language Lua, associative arrays, called tables, are used as the primitive building block for all data structures, even arrays. Likewise, in JavaScript, all objects are associative arrays. Associative arrays can be implemented in any programming language, and one or more implementations of them is typically found either built into the language or the standard library distributed with it (C is a noticeable exception, as neither the language nor the standard library directly provide one. It is not difficult to write one in C, though). Smalltalk In Smalltalk a dictionary is used: phonebook := Dictionary new. phonebook at: 'Sally Smart' put: '555-9999'. phonebook at: 'John Doe' put: '555-1212'. phonebook at: 'J. Random Hacker' put: '553-1337'. To access an entry the message #at: is sent to the dictionary object. phonebook at: 'Sally Smart' gives '555-9999' TCL In Tcl every array is an associative array. set "phonebook(Sally Smart)" 555-9999 set "phonebook(John Doe)" 555-1212 set "phonebook(J. Random Hacker)" 553-1337 The first argument of the set command has to be enclosed by double quotes, as it contains a space. In Tcl, space is used to separate arguments. To access an entry and put it on standard output puts "$phonebook(Sally Smart)" The result is here 555-9999 Python In Python, associative arrays are called dictionaries. Dictionary literals are marked with curly braces: phonebook = {'Sally Smart':'555-9999', 'John Doe':'555-1212', 'J. Random Hacker':'553-1337'} To access a entry in python simply use the array indexing operator. For example the statement phonebookSmart' would return '555-9999'. C++ C++ also has a form of associative array called std::map. One could create a map with the same information as above using C++ with the following code: #include int main() { std::map phone_book; phone_bookSmart" = "555-9999"; phone_bookDoe" = "555-1212"; phone_bookRandom Hacker" = "553-1337"; return 0; } In C++, std::map allows keys and values to be different data types, but all of the keys in a particular map must be of the same base type. The same must be true for all of the values. Although std::map is typically implemented using a self-balancing binary search tree, the SGI STL also provides a std::hash_map which has the algorithmic benefits of a hash table. D D offers direct support for associative arrays in the core language. The equivalent example would be: Keys and values can be any types, but all the keys in an associative array must be of the same type, and the same for values. Lisp In Lisp and Scheme, association lists are commonly used, as in the following S-expression: '(("Sally Smart" . "555-9999") ("John Doe" . "555-1212") ("J. Random Hacker" . "553-1337")) The syntax (x . y) is used to indicate a pair. Keys and values need not be the same type within an alist. Lisp and Scheme provide operations to manipulate alists in ways similar to associative arrays. Common Lisp also supports a hash table data type. Hash tables have greater overhead than alists, but provide much faster access when there are many elements. Perl One of Perl's distinguishing features is its built-in, language-level support for associative arrays. Modern Perl vernacular refers to associative arrays as hashes; the term associative array is found in older documentation, but is considered somewhat archaic. Perl hashes are flat in that they can only use scalars as keys or values, but values may be references to arrays or other hashes. A hash variable is preceded by a % symbol, to distinguish it from scalar, array and other data types. A hash can be initialized from a key-value list: %phone_book = ( "Sally Smart", "555-9999", "John Doe", "555-1212", "J. Random Hacker","553-1337" ); Perl offers the => syntax, semantically equivalent to the comma, to make the key-value association more visible: %phone_book = ( "Sally Smart" => "555-9999", "John Doe" => "555-1212", "J. Random Hacker => "553-1337" ); Accessing a hash element uses the syntax $hash_name{$key} - the key is surrounded by curly braces and the hash name is prefixed by a $, indicating that the hash element itself is a scalar value, even though it is part of a hash. The value of $phone_book{"John Doe"} is "555-1212". The % sign is only used when referring to the hash as a whole, such as when asking for keys %phone_book. JavaScript JavaScript (and its standardized version: ECMAScript) is a prototype based object-oriented language. Objects can be dynamically extended with new properties. An object is a mapping from property names to values, that is an associative array. The only distinguishing factor is that objects have a prototype link to the object they inherit from. Doing a lookup for a property will forward the lookup to the prototype if the object does not define the property itself. An object literal is written as { property : value, ... }. Example: var myObject = { "Sally Smart" : "555-9999", "John Doe" : "555-1212", "J. Random Hacker" : "553-1337" }; If the property name is a valid identifier, the quotes can be omitted, e.g.: var myOtherObject = { foo : 42, bar : false } Lookup is written using property access notation, either square brackets, which always works, or dot notation, which only works for identifier keys: myObjectDoe" myOtherObject.foo The ECMAScript standard doesn't say how objects should be implemented. Some implementations are efficient, probably a hash map, while others seem to use a linear time lookup (for instance, Microsoft JScript in Internet Explorer). External links
|  | crawford county, michigan
clare county, michigan
chippewa county, michigan
cheboygan county, michigan
charlevoix county, michigan
cass county, michigan
calhoun county, michigan
branch county, michigan
berrien county, michigan
benzie county, michigan
bay county, michigan
| barry county, michigan
baraga county, michigan
arenac county, michigan
antrim county, michigan
alpena county, michigan
allegan county, michigan
alger county, michigan
alcona county, michigan
steve taylor
thepalace.com
tigrignan language
| amharic language
hubert selby jr.
fran ulmer
lullaby
symbolism (arts)
spiny lobster
izhevsk
elisa
doo wop
cherenkov effect
panasonic
| pragmatism
matsushita electric industrial co., ltd.
lev vygotsky
yuv
economic and social commission for asia and the pacific
phi kappa psi
hannah arendt
frantz fanon
fleming and john
sixpence none the richer
ani hyuntikwalaski
|
|
|