FACTOID # 30: If Alaska were its own country, it would be the 26th largest in total area, slightly larger than Iran.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Associative array

An associative array (also map, 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. 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. As a consequence, a common and important use of associative arrays is in memoization. In computer science, a lookup table is a data structure, usually an array or associative array, used to replace a runtime computation with a simpler lookup operation. ... 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 word mapping has several senses: In mathematics and related technical fields, it is some kind of function: see map (mathematics). ... Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A... In mathematics, the domain of a function is the set of all input values to the function. ... Memoization is a technique used to speed up computer programs by storing the results of functions for later reuse, rather than recomputing them. ...


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.) This article or section does not cite its references or sources. ... Object-oriented programming (OOP) is a programming paradigm that uses objects to design applications and computer programs. ... In strictly mathematical branches of computer science the term object is used in a purely mathematical sense to refer to any thing. While this interpretation is useful in the discussion of abstract theory, it is not concrete enough to serve as a primitive datatype in the discussion of more concrete... A binary tree, a simple type of branching linked data structure. ...


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

Contents

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. This article does not cite any references or sources. ...


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). In 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. ...


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: In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ... In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ... A skip list is a probabilistic data structure, based on parallel linked lists, with efficiency comparable to a binary search tree (order O(log n) average time for most operations). ...

  • Hash tables have faster average lookup and insertion time (O(1)), while some kinds of binary search tree have faster worst-case lookup and insertion time (O(log n) instead of O(n)). Hash tables have seen extensive use in realtime 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. 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.
  • 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. On the other hand, with hash tables the data may be cyclically or partially ordered without any problems.
  • 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.
  • 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.

A binary search tree of size 9 and depth 3, with root 8 and leaves 1, 4, 7 and 13. ... In computer science, and moreso in computer programming, overhead is generally considered any combination of excess or indirect computation time, memory, bandwidth, or other resources that are required to be utilized or expended to enable a particular goal. ... 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 are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure. ... Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. ... A hash function [1] is a reproducible method of turning some kind of data into a (relatively) small number that may serve as a digital fingerprint of the data. ... In mathematics, a total order or linear order on a set X is any binary relation on X that is antisymmetric, transitive, and total. ... In mathematics, a cyclic order on a set X with n elements is an arrangement of X as on a clock face, for an n-hour clock. ... In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ...

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. In 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. ... In computer science, a linked list is one of the fundamental data structures used in computer programming. ... In computer science, linear search is a search algorithm, also known as sequential search, that is suitable for searching a set of data for a particular value. ...


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 cons'ing the new association to the head of the list.

CONS, Connection-Oriented Network Service, is one of the two OSI stack network layer protocols, the other being CLNS (Connectionless Network Service). ...

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. In computer science, a Patricia trie (also known as a radix tree) is a simple form of compressed trie which merges single child nodes with their parents. ... In computer science and software engineering, a Judy array is a complex but very fast associative array data structure for storing and looking up values using integer or string keys. ... This article describes routing in computer networks, a method of finding paths from origins to destinations, along which information can be passed. ...


String-keyed maps can avoid extra comparisons during lookups by using tries. A trie for keys to, tea, ten, i, in, and inn. In computer science, a trie, or prefix tree, is an ordered tree data structure that is used to store an associative array where the keys are usually strings. ...


Multimap

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. 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" class for the sorted multimap, and SGI's STL provides the "hash_multimap" class, which implements a multimap using a hash table. A map simpliciter is a data structure which defines a unique correlation of keys to values. ...


Language support

Associative arrays can be implemented in any programming language as a package and many language systems provide them as part of their standard library. In some languages, they are not only built into the standard system, but have special syntax, often array-like subscripting. Image File history File links This is a lossless scalable vector image. ...


Built-in syntactic support for associative arrays was introduced by Snobol4, under the name "table". MUMPS made multi-dimensional associative arrays, optionally persistent, its key data structure. SETL supported them as one possible implementation of sets and maps. Most modern scripting languages, starting with awk and including Perl, tcl, Javascript, Python, and Ruby, support associative arrays as their primary array type. SNOBOL (StriNg Oriented symBOlic Language) is a computer programming language that was developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky. ... SETL is a very-high level programming language based on the mathematical theory of sets. ... AWK is a general purpose computer language that is designed for processing text based data, either in files or data streams. ... Wikibooks has a book on the topic of Perl Programming Perl is a dynamic programming language created by Larry Wall and first released in 1987. ... Tcl (originally from Tool Command Language, but nonetheless conventionally rendered as Tcl rather than TCL; and pronounced tickle) is a scripting language created by John Ousterhout. ... JavaScript is a scripting language most often used for client-side web development. ... Python is a high-level programming language first released by Guido van Rossum in 1991. ... Ruby is a reflective, dynamic, object-oriented programming language. ...


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 Map) and in Common Lisp and Windows PowerShell they are called hashtables (since both typically uses this implementation). 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. Smalltalk is a dynamically typed object oriented programming language designed at Xerox PARC by Alan Kay, Dan Ingalls, Ted Kaehler, Adele Goldberg, and others during the 1970s. ... Objective-C, often referred to as ObjC or more seldomly as Objective C or Obj-C, is an object oriented programming language implemented as an extension to C. It is used primarily on Mac OS X and GNUstep, two environments based on the OpenStep standard, and is the primary language... Python is a high-level programming language first released by Guido van Rossum in 1991. ... Wikibooks has a book on the topic of Perl Programming Perl is a dynamic programming language created by Larry Wall and first released in 1987. ... Ruby is a reflective, object-oriented programming language. ... C++ (pronounced see plus plus, IPA: ) is a general-purpose, high-level programming language with low-level facilities. ... Java is a programming language originally developed by Sun Microsystems and released in 1995. ... Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ... Windows PowerShell, previously Microsoft Shell or MSH (codenamed Monad) is an extensible command line interface (CLI) shell and scripting language product developed by Microsoft. ... PHP is a reflective programming language originally designed for producing dynamic web pages. ...


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. In MUMPS, the associative arrays are typically stored as B-trees. The Lua (pronounced LOO-ah, or in IPA) programming language is a lightweight, reflective, imperative and procedural language, designed as a scripting language with extensible semantics as a primary goal. ... JavaScript is a scripting language most often used for client-side web development. ... B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ...


Awk

Awk has built-in, language-level support for associative arrays. AWK is a general purpose computer language that is designed for processing text based data, either in files or data streams. ...


For example:

 phonebook["[[Sally Smart]]"] = "555-9999" phonebook["[[John Doe]]"] = "555-1212" phonebook["[[J. Random Hacker]]"] = "555-1337" 

You can also loop through an associated array as follows:

 for (name in phonebook) { print name, " ", phonebook[name] } 

You can also check if an element is in the associative array, and delete elements from an associative array.


Multi-dimensional associative arrays can be implemented in standard Awk using concatenation and e.g. SUBSEP:

 { # for every input line multi[$1 SUBSEP $2]++; } # END { for (x in multi) { split(x, arr, SUBSEP); print arr[1], arr[2], multi[x]; } } 

Thompson AWK [1] provides built-in multi-dimensional associative arrays:

 { # for every input line multi[$1][$2]++; } # END { for (x in multi) for (y in multi[x]) print x, y, multi[x][y]; } 

C

There is no standard implementation of an associative array in C, but a 3rd party library with BSD license is available here. POSIX 1003.1-2001 describes the functions hcreate(), hdestroy() and hsearch(). POSIX or Portable Operating System Interface[1] is the collective name of a family of related standards specified by the IEEE to define the application programming interface (API) for software compatible with variants of the Unix operating system. ...


Another 3rd party library, uthash, also creates associative arrays from C structures. A structure represents a value, and one of the structure fields acts as the key.


Finally, the Glib library also supports associative arrays, along with many other advanced data types and is the recommended implementation of the GNU Project. GLib is a cross-platform utility library. ...


ColdFusion

You can use a ColdFusion structure to perform as an associative array. Here is a sample in ColdFusion: This article or section does not adequately cite its references or sources. ...

 <cfscript> phoneBook = StructNew(); phoneBook["Sally Smart"] = "555-9999"; phoneBook["John Doe"] = "555-1212"; phoneBook["J. Random Hacker"] = "553-1337"; sName = "A Person"; phoneBook[sName] = "765-4321"; phoneBook.UnknownComic = "???"; </cfscript> 
 <!-- will output 3 question marks below: --> <cfoutput> #phoneBook["UnknownComic"]# </cfoutput> 

Basic

There is no standard implementation common to all dialects. Visual Basic can use the Dictionary class from the Microsoft Scripting Runtime (which is shipped with Visual Basic 6): Visual Basic (VB) is an event driven programming language and associated development environment from Microsoft for its COM programming model. ... The Microsoft Windows Scripting Host is distributed and installed by default on Windows 98, Windows 2000, Windows Me, Windows XP and Windows Server 2003. ...

 ' Requires a reference to SCRRUN.DLL in Project Properties Dim phoneBook As New Dictionary phoneBook.Add "Sally Smart", "555-9999" phoneBook.Item("John Doe") = "555-1212" phoneBook("J. Random Hacker") = "553-1337" For Each name In phoneBook MsgBox name & " = " & phoneBook(name) Next 

Visual Basic .NET relies on the collection classes provided by .NET Framework: Visual Basic . ... The Microsoft . ...

 Dim phoneBook As New System.Collections.Generic.Dictionary(Of String, String) phoneBook("Sally Smart") "555-9999" phoneBook("John Doe") = "555-1212" phoneBook("J. Random Hacker") = "553-1337" For Each entry As KeyValuePair(Of String, String) In phoneBook MsgBox(entry.Key & " = " & entry.Value) Next 

C#

C# The title given to this article is incorrect due to technical limitations. ...

 Hashtable ht = new Hashtable(); ht.Add("testKey", "AssociatedData"); MessageBox.Show((string) ht["testKey"]); 

C# The title given to this article is incorrect due to technical limitations. ...

 Dictionary<int, string> dic = new Dictionary<int, string>(); dic.Add(7, "Bond"); MessageBox.Show(dic[7]); 

In the above sample the Hashtable class is only capable of associating a String key with a value of Object type. Because in .NET all types (save pointers) ultimately derive from Object anything can be put into a Hashtable, even data of different types. This could lead to errors if consuming code expects data to be of a singular type. In the above code casting is required to convert the Object variables back to their original type. Additionally, casting value-types (structures such as integers) to Object to put into the Hashtable and casting them back requires boxing/unboxing which incurs both a slight performance penalty and pollutes the heap with garbage. This changes in C# 2.0 with generic hashtables called dictionaries. There are significant performance and reliability gains to these strongly typed collections because they do not require boxing/unboxing or explicit type casts and introduce compile-time type checks.


C++

C++ also has a form of associative array called std::map (see Standard Template Library#Containers). One could create a map with the same information as above using C++ with the following code: C++ (pronounced see plus plus, IPA: ) is a general-purpose, high-level programming language with low-level facilities. ... The Standard Template Library (STL) is a software library included in the C++ Standard Library. ...

 #include <map> #include <string> int main() { std::map<std::string, std::string> phone_book; phone_book["Sally Smart"] = "555-9999"; phone_book["John Doe"] = "555-1212"; phone_book["J. Random Hacker"] = "553-1337"; return 0; } 

You can iterate through the list with the following code:

 std::map<string, string>::iterator curr,end; for( curr = phone_book.begin(), end = phone_book.end(); curr != end; curr++ ) cout << curr->first + " = " + curr->second << endl; 

In C++, the std::map class is templated which allows keys and values to be different data types. For a given instance of the map class the keys 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. Generic programming is a style of computer programming where algorithms are written in an extended grammar and are made adaptable by specifying variable parts that are then somehow instantiated later by the compiler with respect to the base grammar. ... A data type is a constraint placed upon the interpretation of data in a type system in computer programming. ... In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...


Cocoa/GNUstep (Objective-C)

Cocoa (API) and GNUstep handle associative arrays using NSMutableDictionary (a mutable version of NSDictionary) class cluster. This class allows assignments between any two objects to be made. A copy of key object is made before it is being inserted into NSMutableDictionary, therefore the keys must conform to the NSCopying protocol. When being inserted to a dictionary, the value object receives a retain message to increase its reference count. The value object will receive the release message when it will be deleted from the dictionary (both explicitly or by adding to the dictionary a different object with the same key). A Cocoa application being developed using Xcode. ... GNUstep is a free software implementation of NeXTs OpenStep Objective-C libraries (called frameworks), widget toolkit, and application development tools not only for Unix-like operating systems, but also for Microsoft Windows. ...

 NSMutableDictionary *aDictionary = [[NSMutableDictionary alloc] init]; [aDictionary setObject:@"555-9999" forKey:@"Sally Smart"]; [aDictionary setObject:@"555-1212" forKey:@"John Doe"]; [aDictionary setObject:@"553-1337" forKey:@"Random Hacker"]; 

To access assigned objects this command may be used:

 id anObject = [aDictionary objectForKey:@"Sally Smart"]; 

All keys or values can be simply enumerated using NSEnumerator

 NSEnumerator *keyEnumerator = [[aDictionary allKeys] objectEnumerator]; id key; while (( key = [keyEnumerator nextObject] )) { // ... process it here ... } 

What is even more practical, structured data graphs may be easily created using Cocoa (API), especially NSDictionary (NSMutableDictionary). This can be ilustrated with this compact example: A Cocoa application being developed using Xcode. ...

 NSDictionary *aDictionary = [NSDictionary dictionaryWithObjectsAndKeys: [NSDictionary dictionaryWithObjectsAndKeys: @"555-9999", @"Sally Smart", @"555-1212", @"John Doe", nil], @"students", [NSDictionary dictionaryWithObjectsAndKeys: @"553-1337", @"Random Hacker", nil], @"hackers", nil]; 

And relevant fields can be quickly accessed using key paths:

 id anObject = [aDictionary valueForKeyPath:@"students.Sally Smart"]; 

D

D offers direct support for associative arrays in the core language - they are implemented as trees[citation needed]. The equivalent example would be: D is an object-oriented, imperative system programming language designed by Walter Bright of Digital Mars as a re-engineering of C/C++. He has done this by re-designing many C++ features, and borrowing ideas from other programming languages. ...

 int main() { char[][char[]] phone_book; phone_book["Sally Smart"] = "555-9999"; phone_book["John Doe"] = "555-1212"; phone_book["J. Random Hacker"] = "553-1337"; return 0; } 

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.


You can also loop through all properties and associated values, i.e. as follows:

 foreach (key, value; phone_book) { writefln("Number for $name: $numbern", key, value); } 

A property can be removed as follows:

 phone_book.remove("Sally Smart"); 

Java

In Java associative arrays are implemented as "maps"; they are part of the Java Collections Framework. Since J2SE 5.0 and the introduction of generics into Java, collections can have a type specified; for example, an associative array mapping strings to strings might be specified as follows: Java is a programming language originally developed by Sun Microsystems and released in 1995. ... Java 2 Platform, Standard Edition or J2SE is a collection of java Application Programming Interfaces targeting Java platform applications running on a workstation. ... Generic programming is a style of computer programming where algorithms are written in an extended grammar and are made adaptable by specifying variable parts that are then somehow instantiated later by the compiler with respect to the base grammar. ...

 Map<String, String> phoneBook = new HashMap<String, String>(); phoneBook.put("Sally Smart", "555-9999"); phoneBook.put("John Doe", "555-1212"); phoneBook.put("J. Random Hacker", "555-1337"); 

The get method is used to access a key; for example, the value of the expression phoneBook.get("Sally Smart") is "555-9999".


This code uses a hash map to store the associative array, by calling the constructor of the HashMap class; however, since the code only uses methods common to the interface Map, one could also use a self-balancing binary tree by calling the constructor of the TreeMap class (which implements the subinterface SortedMap, without changing the definition of the phone_book variable or the rest of the code, or use a number of other underlying data structures that implement the Map interface.


The hash function in Java is provided by the method Object.hashCode(). Since every class in Java inherits from Object, every object has a hash function. A class can override the default implementation of hashCode() to provide a custom hash function based on the properties of the object. This article or section does not cite any references or sources. ... Method overriding, in object oriented programming, is a language feature that allows a subclass to provide a specific implementation of a method that is already provided by one of its superclasses. ...


The Object class also contains the method equals(Object) that tests the object for equality with another object. Maps in Java rely on objects maintaining the following contract between their hashCode() and equals() methods:

For two objects a and b
  • a.equals(b) == b.equals(a)
  • if a.equals(b) then a.hashCode() == b.hashCode()

In order to maintain this contract, a class that overrides equals() must also override hashCode(), and vice versa, so that hashCode() is based on the same properties (or a subset of the properties) as equals().


A further contract that the map has with the object is that the results of the hashCode() and equals() methods will not change once the object has been inserted into the map. For this reason, it is generally a good practice to base the hash function on immutable properties of the object. In computing, immutable refers to: the immutable design pattern in programming an immutable object in object-oriented programming This is a disambiguation page &#8212; a navigational aid which lists other pages that might otherwise share the same title. ...


JavaScript

JavaScript (and its standardized version: ECMAScript) is a prototype-based object-oriented language. In JavaScript an object is a mapping from property names to values -- that is, an associative array with one caveat: since property names are strings, only string keys are allowed. Other than that difference, objects also include one feature unrelated to associative arrays: 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. ECMAScript is a scripting programming language, standardized by Ecma International in the ECMA-262 specification. ... Prototype-based programming is a style of object-oriented programming in which classes are not present, and behaviour reuse (known as inheritance in class-based languages) is accomplished through a process of cloning existing objects which serve as prototypes. ... Object-oriented programming (OOP) is a programming paradigm that uses objects to design applications and computer programs. ...


An object literal is written as { property1 : value1, property2 : value2, ... }. For 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:

 myObject["John Doe"] myOtherObject.foo 

You can also loop through all properties and associated values as follows:

 for(var property in myObject) { var value = myObject[property]; alert("myObject[" + property + "] = " + value); } 

A property can be removed as follows:

 delete myObject["Sally Smart"]; 

As mentioned before, properties are strings. However, since every native object and primitive can be implicitly converted to a string, you can do:

 myObject[1] // key is "1"; note that myObject[1] === myObject['1'] myObject[['a','b']] // key is "a,b" myObject[{toString:function(){return 'hello world';}}] // key is "hello world" 

Any object, including built-in objects such as Array, can be dynamically extended with new properties. For example:

 Array.prototype.removeAllObjects = function () { /* ... */ } 

In modern JavaScript it's considered bad form to use the Array type as an associative array. Consensus is that the Object type is best for this purpose. The reasoning behind this is that if Array is extended via prototype and Object is kept pristine, 'for(in)' loops will work as expected on associative 'arrays'. This issue has been drawn into focus by the popularity of JavaScript frameworks that make heavy and sometimes indiscriminate use of prototype to extend JavaScript's inbuilt types.


See JavaScript Array And Object Prototype Awareness Day for more information on the issue.


KornShell 93 (and compliant shells: ksh93, zsh, ...)

Note: The latest version of bash, 3.2, doesn't support associative arrays properly yet.

Definition: This article is about the UNIX shell named Bash. ...

 typeset -A phonebook; phonebook=(["Sally Smart"]="555-9999" ["John Doe"]="555-1212" ["J. Random Hacker"]="555-1337"); 

Dereference:

 ${phonebook["John Doe"]}; 

Lisp

Lisp was originally conceived as a "LISt Processing" language, and one of its most important data types is the linked list, which can be treated as an association list ("alist"). Lisp is a family of computer programming languages with a long history and a distinctive fully-parenthesized syntax. ...

 '(("Sally Smart" . "555-9999") ("John Doe" . "555-1212") ("J. Random Hacker" . "553-1337")) 

The syntax (x . y) is used to indicate a consed pair. Keys and values need not be the same type within an alist. Lisp and Scheme provide operators such as assoc to manipulate alists in ways similar to associative arrays. CONS, Connection-Oriented Network Service, is one of the two OSI stack network layer protocols, the other being CLNS (Connectionless Network Service). ...


Because of their linear nature, alists are used for relatively small sets of data. Common Lisp also supports a hash table data type, and for Scheme they are implemented in SRFI 69. Hash tables have greater overhead than alists, but provide much faster access when there are many elements. Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, standardised by ANSI X3. ... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ... Scheme is a multi-paradigm programming language. ... The introduction to this article provides insufficient context for those unfamiliar with the subject matter. ...


It is easy to construct composite abstract data types in Lisp, using the object-oriented programming features in conjunction with lists, arrays, and hash tables.


Lua

In Lua, table is a fundamental type that can be used either as array (numerical index, fast) or as associative array. The keys and values can be of any type, except nil. The following with focus on non-numerical indexes. The Lua (pronounced LOO-ah, or in IPA) programming language is a lightweight, reflective, imperative and procedural language, designed as a scripting language with extensible semantics as a primary goal. ...


A table literal is written as { value, key = value, [index] = value, ["non id string"] = value }. For example:

 phone_book = { ["Sally Smart"] = "555-9999", ["John Doe"] = "555-1212", ["J. Random Hacker"] = "553-1337", -- Trailing comma is OK } 
 aTable = { -- Table as value subTable = { 5, 7.5, k = true }, -- key is "subTable" -- Function as value ['John Doe'] = function (age) if age < 18 then return "Young" else return "Old!" end end, -- Table and function (and other types) can also be used as keys } 

If the key is a valid identifier (not a keyword), the quotes can be omitted. They are case sensitive.


Lookup is written using either square brackets, which always works, or dot notation, which only works for identifier keys:

 print(aTable["John Doe"](45)) x = aTable.subTable.k 

You can also loop through all keys and associated values with iterators or for loops:

 simple = { [true] = 1, [false] = 0, [3.14] = math.pi, x = 'x', ["!"] = 42 } function FormatElement(key, value) return "[" .. tostring(key) .. "] = " .. value .. ", " end -- Iterate on all keys table.foreach(simple, function (k, v) io.write(FormatElement(k, v)) end) print"" for k, v in pairs(simple) do io.write(FormatElement(k, v)) end print"" k= nil repeat k, v = next(simple, k) if k ~= nil then io.write(FormatElement(k, v)) end until k == nil print"" 

An entry can be removed by setting it to nil:

 simple.x = nil 

Likewise, you can overwrite values or add them:

 simple['%'] = "percent" simple['!'] = 111 

MUMPS

In MUMPS every array is an associative array. The built-in, language-level, direct support for associative arrays applies to private, process-specific arrays stored in memory called "locals" as well as to the permanent, shared arrays stored on disk which are available concurrently by multiple jobs. The name for globals is preceded by the circumflex "^" to distinquish it from local variable names.

 SET ^phonebook("Sally Smart")="555-9999" ;; storing permanent data SET phonebook("John Doe")="555-1212" ;; storing temporary data SET phonebook("J. Random Hacker")="553-1337" ;;storing temporary data MERGE ^phonebook=phonebook ;;copying temporary data into permanent data 

To access the value of an element, simply requires using the name with the subscript:

 WRITE "Phone Number :",^phonebook("Sally Smart"),! 

You can also loop through an associated array as follows:

 SET NAME="" FOR S NAME=$ORDER(^phonebook(NAME)) QUIT:NAME="" WRITE NAME," Phone Number :",^phonebook(NAME),! 

OCaml

The OCaml programming language provides three different associative containers. The simplest is a list of pairs: Objective Caml (OCaml) is a general-purpose programming language descended from the ML family, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. ...

 # let m = ["Sally Smart", "555-9999"; "John Doe", "555-1212"; "J. Random Hacker", "553-1337"];; val m : (string * string) list = [("Sally Smart", "555-9999"); ("John Doe", "555-1212"); ("J. Random Hacker", "553-1337")] # List.assoc "John Doe" m;; - : string = "555-1212" 

The second is a polymorphic hash table:

 # let m = Hashtbl.create 3;; val m : ('_a, '_b) Hashtbl.t = <abstr> # Hashtbl.add m "Sally Smart" "555-9999"; Hashtbl.add m "John Doe" "555-1212"; Hashtbl.add m "J. Random Hacker" "553-1337";; - : unit = () # Hashtbl.find m "John Doe";; - : string = "555-1212" 

Finally, functional maps (represented as immutable balanced binary trees):

 # include (Map.Make(String));; ... # let m = add "Sally Smart" "555-9999" empty let m = add "John Doe" "555-1212" m let m = add "J. Random Hacker" "553-1337" m;; val m : string t = <abstr> # find "John Doe" m;; - : string = "555-1212" 

Lists of pairs and functional maps both provide a purely functional interface. In contrast, hash tables provide an imperative interface. For many operations, hash tables are significantly faster than lists of pairs and functional maps.


Perl

Perl has 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: keys are strings and values are scalars. However, values may be references to arrays or other hashes. Wikibooks has a book on the topic of Perl Programming Perl is a dynamic programming language created by Larry Wall and first released in 1987. ... This article discusses a general notion of reference in computing. ...


A hash variable is marked by a % sigil, to distinguish it from scalar, array and other data types. A hash can be initialized from a key-value list: In computer programming, a sigil is a symbol attached to a variable name, showing the variables datatype. ...

 %phone_book = ("Sally Smart", "555-9999", "John Doe", "555-1212", "J. Random Hacker", "553-1337"); 

Perl offers the => syntax, semantically (almost) 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 % sigil is only used when referring to the hash as a whole, such as when asking for keys %phone_book.


The list of keys and values can be extracted using the built-in functions keys and values, respectively. So, for example, to print all the keys of a hash:

 foreach $name (keys %phone_book) { print "$namen"; } 

One can iterate through (key, value) pairs using the each function:

 while (($name, $number) = each %phone_book) { print "Number for $name: $numbern"; } 

PHP

PHP's built-in array type is in reality an associative array. Even when using numerical indexes, PHP internally stores it as an associative array.[1]This is why one in PHP can have non-consecutive numerically indexed arrays. PHP is a reflective programming language originally designed for producing dynamic web pages. ...


An associative array can be formed in one of two ways:

 $phonebook = array (); $phonebook['Sally Smart'] = '555-9999'; $phonebook['John Doe'] = '555-1212'; $phonebook['J. Random Hacker'] = '555-1337'; 
 $phonebook = array ( 'Sally Smart' => '555-9999', 'John Doe' => '555-1212', 'J. Random Hacker' => '555-1337', // trailing comma is OK ); 

You can also loop through an associative array as follows:

 foreach ($phonebook as $name => $number) { echo "Number for $name: $numbern"; } 

PHP has an extensive set of functions to operate on arrays.


Pike

Pike has built-in support for Associative Arrays, which are referred to as mappings. Mappings are created as follows: Pike is an interpreted, general-purpose, high-level, cross-platform, dynamic programming language, with a syntax similar to that of C. Unlike many other dynamic languages, Pike is both statically and dynamically typed, and requires explicit type definitions. ...

 mapping(string:string) phonebook = ([ "Sally Smart":"555-9999", "John Doe":"555-1212", "J. Random Hacker":"555-1337" ]); 

Accessing and testing for presence in mappings is done using the indexing operator. So phonebook["Sally Smart"] would return the string "555-9999", and phonebook["John Smith"] would return 0.


Iterating through a mapping can be done using either foreach:

 foreach(phonebook; string key; string value) { write("%s:%sn", key, value); } 

Or using an iterator object:

 Mapping.Iterator i = get_iterator(phonebook); while (i->index()) { write("%s:%sn", i->index(), i->value()); i->next(); } 

Elements of a mapping can be removed using m_delete, which returns the value of the removed index:

 string sallys_number = m_delete(phonebook, "Sally Smart"); 

Python

In Python, associative arrays are called dictionaries. Dictionary literals are marked with curly braces: Python is a high-level programming language first released by Guido van Rossum in 1991. ... The syntax of the Python programming language is the set of rules that defines how a Python program will be written and interpreted (by both the runtime system and by human readers). ...

 phonebook = {'Sally Smart' : '555-9999', 'John Doe' : '555-1212', 'J. Random Hacker' : '553-1337'} 

To access an entry in Python simply use the array indexing operator. For example, the expression phonebook['Sally Smart'] would return '555-9999'.


An example loop iterating through all the keys of the dictionary: In computer science, an iterator is an object which allows a programmer to traverse through all the elements of a collection, regardless of its specific implementation. ...

 for key in phonebook: print key, phonebook[key] 

Iterating through (key, value) tuples:

 for key, value in phonebook.iteritems(): print key, value 

Dictionaries can also be constructed with the dict builtin, which takes a key-value list:

 dict((key, value) for key, value in phonebook.items() if 'J' in key) 

Dictionary keys can be individually deleted using the del statement. The corresponding value can be returned before the key-value pair are deleted using the pop method of dict types;

 del phonebook['John Doe'] val = phonebook.pop('Sally Smart') assert phonebook.keys() == ['J. Random Hacker'] # Only one key left 

REXX

In REXX, associative arrays are called Stem variables or Compound variables. REXX (REstructured eXtended eXecutor) is an interpreted programming language which was developed at IBM. It is a structured high-level programming language which was designed to be both easy to learn and easy to read. ...

 KEY = 'Sally Smart' PHONEBOOK.KEY = '555-9999' KEY = 'John Doe' PHONEBOOK.KEY = '555-1212' KEY = 'J. Ramdon Hacker' PHONEBOOK.KEY = '553-1337' 

Stem variables with numeric keys typically start at 1 and go up from there. The 0 key stem variable is used (by convention) as the count of items in the whole stem.

 NAME.1 = 'Sally Smart' NAME.2 = 'John Doe' NAME.3 = 'J. Random Hacker' NAME.0 = 3 

REXX has no easy way of automatically accessing the keys for a stem variable and typically the keys are stored in a separate associative array with numeric keys. REXX (REstructured eXtended eXecutor) is an interpreted programming language which was developed at IBM. It is a structured high-level programming language which was designed to be both easy to learn and easy to read. ...


Ruby

In Ruby a Hash is used as follows: Ruby is a reflective, object-oriented programming language. ...

 phonebook = { 'Sally Smart' => '555-9999', 'John Doe' => '555-1212', 'J. Random Hacker' => '553-1337' } 

phonebook['John Doe'] produces '555-1212'


To iterate over the hash, use something like the following:

 phonebook.each {|key, value| puts key + " => " + value} 

Additionally, each key may be shown individually:

 phonebook.each_key {|key| puts key} 

Each value may, of course, also be shown:

 phonebook.each_value {|value| puts value} 

Smalltalk

In Smalltalk a dictionary is used: For other uses, see Small Talk (disambiguation). ...

 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' 

SNOBOL

SNOBOL is one of the first (if not the first) programming languages to use associative arrays. Associative arrays in SNOBOL are called Tables. SNOBOL (StriNg Oriented symBOlic Language) is a computer programming language developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky. ... SNOBOL (StriNg Oriented symBOlic Language) is a computer programming language developed between 1962 and 1967 at AT&T Bell Laboratories by David J. Farber, Ralph E. Griswold and Ivan P. Polonsky. ...

 PHONEBOOK = TABLE() PHONEBOOK['Sally Smart'] = '555-9999' PHONEBOOK['John Doe'] = '555-1212' PHONEBOOK['J. Random Hacker'] = '553-1337' 

TCL

In Tcl every array is an associative array. Tcl (originally from Tool Command Language, but nonetheless conventionally rendered as Tcl rather than TCL; and pronounced tickle) is a scripting language created by John Ousterhout. ...

 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. Alternatively, array setting can be grouped into a single command (keys braced because they contain whitespace):

 array set phonebook { {Sally Smart} 555-9999 {John Doe} 555-1212 {J. Random Hacker} 553-1337 } 

To access an entry and put it on standard output

 puts "$phonebook(Sally Smart)" 

The result is here

 555-9999 

Windows PowerShell

Unlike many other command line interpreters, PowerShell has built-in, language-level support for defining associative arrays. It has been suggested that this article or section be merged into Command line interface. ... Windows PowerShell, previously Microsoft Shell or MSH (codenamed Monad) is an extensible command line interface (CLI) shell and scripting language product developed by Microsoft. ...


For example:

 $phonebook = @{ 'Sally Smart' = '555-9999'; 'John Doe' = '555-1212'; 'J. Random Hacker' = '553-1337' } 

Like in JavaScript, if the property name is a valid identifier, the quotes can be omitted, e.g.:

 $myOtherObject = @{ foo = 42; bar = $false } 

It is also possible to create an empty associative array and add single entries or even other associative arrays to it later on.

 $phonebook = @{} $phonebook += @{ 'Sally Smart' = '555-9999' } $phonebook += @{ 'John Doe' = '555-1212'; 'J. Random Hacker' = '553-1337' } 

New entries can also be added by using the array index operator, the property operator or the Add() method of the underlying .NET object: The Microsoft . ...

 $phonebook = @{} $phonebook['Sally Smart'] = '555-9999' $phonebook.'John Doe' = '555-1212' $phonebook.Add('J. Random Hacker', '553-1337') 

To dereference assigned objects the array index operator, the property operator or the parameterized property Item() of the .NET object can be used:

 $phonebook['Sally Smart'] $phonebook.'John Doe' $phonebook.Item('J. Random Hacker') 

You can loop through an associative array as follows:

 $phonebook.Keys | foreach { "Number for {0}: {1}" -f $_,$phonebook.$_ } 

An entry can be removed using the Remove() method of the the underlying .NET object:

 $phonebook.Remove('Sally Smart') 

External links

References

  1. ^ About the implementation of Arrays in PHP

  Results from FactBites:
 
Associative array - Wikinfo (2968 words)
In computing, an associative array, also known as a map or table, is an abstract data type very closely related to the mathematical concept of a function.
Conceptually, an associative array is composed of a collection of keys and a collection of values, and each key is associated with one value.
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.
Associative array - Wikipedia, the free encyclopedia (3167 words)
An associative array (also map, 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.
Associative arrays are very closely related to the mathematical concept of a function with a finite domain.
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 notable exception, as neither the language nor the standard library directly provide one).
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m