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.
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 the key from the key set

★ 'Lookup': Find the value (if any) that is bound to a key

Contents

Examples

Data structures for associative arrays

Efficient representations

Association lists

Specialized representations

Multimap

Language support

Awk

C

ColdFusion

Basic

C#

C++

Cocoa/GNUstep (Objective-C)

D

Delphi

Java

JavaScript

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

Lisp

Lua

MUMPS

OCaml

Perl

PHP

Pike

Python

['J. Random Hacker'] # Only one key left

Ruby

Smalltalk

SNOBOL

TCL

Windows PowerShell

External links

References

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 the hash 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 (rather than writing) 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). The programmer using the structure is, however, unaware of the details of the implementation when she uses it.

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

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 cons'ing 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.

Multimap

Main articles: 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. 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.

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.
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.
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 ) and in Common Lisp and Windows PowerShell they are called ''hashtables'' (since both typically use 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.
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.

Awk

Awk has built-in, language-level support for associative arrays.
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().
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.

ColdFusion

You can use a ColdFusion structure to perform as an associative array. Here is a sample in ColdFusion:


phoneBook = StructNew();
phoneBook["Sally Smart"] = "555-9999";
phoneBook["John Doe"] = "555-1212";
phoneBook["J. Random Hacker"] = "555-1337";
sName = "A Person";
phoneBook[sName] = "555-4321";
phoneBook.UnknownComic = "???";


#phoneBook["UnknownComic"]#

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):

' 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:

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#

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


Dictionary dic = new Dictionary();
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:

#include