Comparison of programming languages (associative array)
This Comparison of programming languages (associative arrays) compares the features of associative array data structures or array-lookup processing for over 39 various computer programming languages.
Language support
The following is a comparison of associative arrays (also "mapping", "hash", and "dictionary") in various programming languages.
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 simulated 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];
}
}
C
There is no standard implementation of an associative array in C, but a 3rd party library with BSD license is available here, archived here, with the source code 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.
Similar to Glib, Apple's cross-platform Core Foundation framework provides several basic data types. In particular, there are reference counted CFDictionary and CFMutableDictionary.
C#
Dictionary<string, string> dic = new Dictionary<string, string>();
dic.Add("Sally Smart", "555-9999");
dic.Add("John Doe", "555-1212");
dic.Add("J. Random Hacker", "553-1337");
// access a phone number and display it in a message box
MessageBox.Show(dic["Sally Smart"]);
The dictionary can also be initialized with all entries during construction. This is called "object initialization".
var dic = new Dictionary<string, string>
{
{"Sally Smart", "555-9999"},
{"John Doe", "555-1212"},
{"J. Random Hacker", "553-1337"}
};
A foreach loop can enumerate through the entire collection. There is no guarantee of order. If order matters the programmer could choose to use a SortedDictionary or use a .Sort linq extension method.
// loop through the collection and display each entry
foreach(KeyValuePair<string,string> kvp in dic)
{
MessageBox.Show(String.Format("Phone number for {0} is {1}", kvp.Key, kvp.Value));
}
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 <map>
#include <string>
#include <utility>
int main() {
std::map<std::string, std::string> phone_book;
phone_book.insert(std::make_pair("Sally Smart", "555-9999"));
phone_book.insert(std::make_pair("John Doe", "555-1212"));
phone_book.insert(std::make_pair("J. Random Hacker", "553-1337"));
}
Or less efficiently as it creates temporary std::string values:
#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";
}
With the extension of initialization lists in C++11, entries can be added during a map's construction as shown below:
#include <map>
#include <string>
int main() {
std::map<std::string, std::string> phone_book {
{"Sally Smart", "555-9999"},
{"John Doe", "555-1212"},
{"J. Random Hacker", "553-1337"}
};
}
You can iterate through the list with the following code (C++03):
std::map<std::string, std::string>::iterator curr, end;
for(curr = phone_book.begin(), end = phone_book.end(); curr != end; ++curr)
std::cout << curr->first << " = " << curr->second << std::endl;
The same task in new C++11:
for(const auto& curr : phone_book)
std::cout << curr.first << " = " << curr.second << std::endl;
In C++, the std::map class is templated which allows the data types of keys and values to be different for different map instances. 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, C++11 defines a second map called std::unordered_map with the algorithmic characteristics of a hash table. This is a common vendor extension to the STL as well, usually called hash_map, being available from such implementations as SGI and STLPort.
CFML
A structure in CFML is equivalent to an associative array:
dynamicKeyName = "John Doe";
phoneBook = {
"Sally Smart" = "555-9999",
"#dynamicKeyName#" = "555-4321",
"J. Random Hacker" = "555-1337",
UnknownComic = "???"
};
writeOutput(phoneBook.UnknownComic); // ???
writeDump(phoneBook); // entire struct
Cobra
Initializing an empty dictionary and adding items:
dic as Dictionary<of String, String> = Dictionary<of String, String>()
dic.add('Sally Smart', '555-9999')
dic.add('John Doe', '555-1212')
dic.add('J. Random Hacker', '553-1337')
assert dic['Sally Smart'] == '555-9999'
Alternatively, a dictionary can be initialized with all items during construction:
dic = {
'Sally Smart':'555-9999',
'John Doe':'555-1212',
'J. Random Hacker':'553-1337'
}
The dictionary can be enumerated by a for-loop, but there is no guaranteed order:
for key, val in dic
print "[key]'s phone number is [val]"
D
D offers direct support for associative arrays in the core language – they are implemented as a chaining hash table with binary trees.[1] The equivalent example would be:
int main() {
string[ string ] 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) {
writeln("Number for " ~ key ~ ": " ~ value );
}
A property can be removed as follows:
phone_book.remove("Sally Smart");
Delphi
Versions of Delphi prior to 2009 do not offer direct support for associative arrays. However, you can simulate associative arrays using TStrings object. Here's an example:
procedure TForm1.Button1Click(Sender: TObject);
var
DataField: TStrings;
i: Integer;
begin
DataField := TStringList.Create;
DataField.Values['Sally Smart'] := '555-9999';
DataField.Values['John Doe'] := '555-1212';
DataField.Values['J. Random Hacker'] := '553-1337';
// access an entry and display it in a message box
ShowMessage(DataField.Values['Sally Smart']);
// loop through the associative array
for i := 0 to DataField.Count - 1 do
begin
ShowMessage('Number for ' + DataField.Names[i] + ': ' + DataField.ValueFromIndex[i]);
end;
DataField.Free;
end;
Delphi 2009 introduced support for generics as well as several standard generic containers, including TDictionary.
uses
SysUtils,
Generics.Collections;
var
PhoneBook: TDictionary<string, string>;
Entry: TPair<string, string>;
begin
PhoneBook := TDictionary<string, string>.Create;
PhoneBook.Add('Sally Smart', '555-9999');
PhoneBook.Add('John Doe', '555-1212');
PhoneBook.Add('J. Random Hacker', '553-1337');
for Entry in PhoneBook do
Writeln(Format('Number for %s: %s',[Entry.Key, Entry.Value]));
end.
Erlang
Erlang offers many approaches to represent mappings, two of the most common in the standard library are keylists and dictionaries.
Keylists are lists of tuples, where the first element of each tuple is a key, and the second is a value. Functions for operating on keylists are provided in the lists module.
PhoneBook = [{"Sally Smart", "555-9999"},
{"John Doe", "555-1212"},
{"J. Random Hacker", "553-1337"}].
Accessing an element of the keylist can be done with the lists:keyfind/3 function:
{_, Phone} = lists:keyfind("Sally Smart", 1, PhoneBook),
io:format("Phone number: ~s~n", [Phone]).
Dictionaries are implemented in the dict of the standard library. A new dictionary is created using the dict:new/0 function and new key/value pairs are stored using the dict:store/3 function:
PhoneBook1 = dict:new(),
PhoneBook2 = dict:store("Sally Smith", "555-9999", Dict1),
PhoneBook3 = dict:store("John Doe", "555-1212", Dict2),
PhoneBook = dict:store("J. Random Hacker", "553-1337", Dict3).
Such a serial initialization would be more idiomatically represented in Erlang with the appropriate function:
PhoneBook = dict:from_list([{"Sally Smith", "555-9999"}, {"John Doe", "555-1212"},
{"J. Random Hacker", "553-1337"}]).
The dictionary can be accessed using the dict:find/2 function:
{ok, Phone} = dict:find("Sally Smith", PhoneBook),
io:format("Phone: ~s~n", [Phone]).
In both cases, any Erlang term can be used as the key. Variations include the orddict module, implementing ordered dictionaries, and gb_trees, implementing general balanced trees.
F#
F# constructs maps from lists, sequences or arrays of tuples, using functions provided by the Map module. F# represents a tuple as two or more elements separated by a comma, and a list as a sequence of elements enclosed in square brackets, separated by semi-colons.
let numbers = [ "Sally Smart", "555-9999";
"John Doe", "555-1212";
"J. Random Hacker", "555-1337" ] |> Map.ofList
Values can be looked up via one of the Map object functions, such as TryFind. This returns an option type with a value of Some, for a successful lookup, or None, for an unsuccessful one. Pattern matching can then be used to extract the raw value, or a default, from the result.
let sallyNumber = match numbers.TryFind("Sally Smart") with
| Some(number) -> number
| None -> "n/a"
In this example, the sallyNumber value will now contain the string "555-9999".
Because F# is a .NET language, it also has access to all of the features of the .NET Framework, including the Dictionary objects and HashTable objects that are used for the same purpose in both C# and Visual Basic. These objects may be preferred when writing code that is intended by be linked to from other languages on the .NET framework.
FoxPro
Visual FoxPro implements mapping with the Collection Class.
mapping = NEWOBJECT("Collection")
mapping.Add("Daffodils", "flower2") && Add(object, key) – key must be character
index = mapping.GetKey("flower2") && returns the index value 1
object = mapping("flower2") && returns "Daffodils" (retrieve by key)
object = mapping(1) && returns "Daffodils" (retrieve by index)
GetKey returns 0 if the key is not found.
See Collection in FoxPro Help for all the details.
Go
Go has built-in, language-level support for associative arrays, called maps. A map's key type may only be a boolean, numeric, string, array, struct, pointer, interface, or channel type. A map type is written like this: map[keytype]valuetype.
Adding elements one at a time:
phone_book := make(map[string] string) // make an empty map
phone_book["Sally Smart"] = "555-9999"
phone_book["John Doe"] = "555-1212"
phone_book["J. Random Hacker"] = "553-1337"
A map literal:
phone_book := map[string] string {
"Sally Smart": "555-9999",
"John Doe": "555-1212",
"J. Random Hacker": "553-1337",
}
Iterating over a map:
// over both keys and values
for key, value := range phone_book {
fmt.Printf("Number for %s: %s\n", key, value)
}
// over just keys
for key := range phone_book {
fmt.Printf("Name: %s\n", key)
}
Haskell
The Haskell programming language's report only provides one kind of associative container: a list of pairs:
m = [("Sally Smart", "555-9999"), ("John Doe", "555-1212"), ("J. Random Hacker", "553-1337")]
main = print (lookup "John Doe" m)
output:
Just "555-1212"
Note that the lookup function returns a "Maybe" value, which is "Nothing" if not found, or "Just result" when found.
GHC, the most commonly used implementation of Haskell, provides two more types of associative containers. Other implementations might also provide these.
One is polymorphic functional maps (represented as immutable balanced binary trees):
import qualified Data.Map as M
m = M.insert "Sally Smart" "555-9999" M.empty
m' = M.insert "John Doe" "555-1212" m
m'' = M.insert "J. Random Hacker" "553-1337" m'
main = print (M.lookup "John Doe" m'' :: Maybe String)
output:
Just "555-1212"
A specialized version for integer keys also exists as Data.IntMap.
Finally, a polymorphic hash table:
import qualified Data.HashTable as H
main = do m <- H.new (==) H.hashString
H.insert m "Sally Smart" "555-9999"
H.insert m "John Doe" "555-1212"
H.insert m "J. Random Hacker" "553-1337"
foo <- H.lookup m "John Doe"
print foo
output:
Just "555-1212"
Lists of pairs and functional maps both provide a purely functional interface, which is more idiomatic in Haskell. In contrast, hash tables provide an imperative interface in the IO monad.
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:
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 above 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 phoneBook 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, used by HashMap and HashSet, 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.
The Object class also contains the method equals(Object) that tests the object for equality with another object. Hashed data structures 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 maybe vice versa, so that hashCode() is based on the same properties (or a subset of the properties) as equals().
A further contract that hashed data structures 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.
Analogously, TreeMap, and other sorted data structures, requires that an ordering be defined on the data type. Either the data type must already have defined its own ordering, by implementing the Comparable interface; or a custom Comparator must be provided at the time the map is constructed. As with HashMap above, the relative ordering of keys in a TreeMap should not change once they have been inserted into the map.
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 and (coerced) integer 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.
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 enumerable 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.
Julia
Declare dictionary:
phonebook = Dict( "Sally Smart" => "555-9999", "John Doe" => "555-1212", "J. Random Hacker" => "555-1337" )
Access element:
phonebook["Sally Smart"]
Add element:
phonebook["New Contact"] = "555-2222"
Delete element:
delete!(phonebook, "Sally Smart")
Get keys and values as iterables:
keys(phonebook) values(phonebook)
KornShell 93 (and compliant shells: ksh93, zsh, bash4...)
Definition:
typeset -A phonebook; # ksh93
declare -A phonebook; # bash4
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").
'(("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.
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.
It is easy to construct composite abstract data types in Lisp, using structures and/or the object-oriented programming features, in conjunction with lists, arrays, and hash tables.
LPC
LPC implements associative arrays as a fundamental type known as either map or mapping, depending on the driver. The keys and values can be of any type. A mapping literal is written as ([ key_1 : value_1, key_2 : value_2 ]). Procedural use looks like:
mapping phone_book = ([]);
phone_book["Sally Smart"] = "555-9999";
phone_book["John Doe"] = "555-1212";
phone_book["J. Random Hacker"] = "555-1337";
Mappings are accessed for reading using the indexing operator in the same way as they are for writing, as shown above. So phone_book["Sally Smart"] would return the string "555-9999", and phone_book["John Smith"] would return 0. Testing for presence is done using the function member(), e.g. if(member(phone_book, "John Smith")) write("John Smith is listed.\n");
Deletion is accomplished using a function called either m_delete() or map_delete(), depending on the driver, used like: m_delete(phone_book, "Sally Smart");
LPC drivers of the "Amylaar" family implement multivalued mappings using a secondary, numeric index. (Drivers of the MudOS family do not support multivalued mappings.) Example syntax:
mapping phone_book = ([:2]);
phone_book["Sally Smart", 0] = "555-9999";
phone_book["Sally Smart", 1] = "99 Sharp Way";
phone_book["John Doe", 0] = "555-1212";
phone_book["John Doe", 1] = "3 Nigma Drive";
phone_book["J. Random Hacker", 0] = "555-1337";
phone_book["J. Random Hacker", 1] = "77 Massachusetts Avenue";
LPC drivers modern enough to support a foreach() construct allow iteration over their mapping types using it.
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 focuses on non-numerical indexes.
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
Mathematica and Wolfram Language
Mathematica uses the Association[2] expression to represent associative arrays.
phonebook = <| "Sally Smart" -> "555-9999",
"John Doe" -> "555-1212",
"J. Random Hacker" -> "553-1337" |>;
To access[3]
phonebook[[Key["Sally Smart"]]]
If the keys are strings, the Key keyword is not necessary, so:
phonebook[["Sally Smart"]]
Keys[phonebook] Values[phonebook]
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 distinguish 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),!
Objective-C (Cocoa/GNUstep)
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 the key object is made before it is 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).
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 keyEnumerator];
id key;
while ((key = [keyEnumerator nextObject]))
{
// ... process it here ...
}
On Mac OS X 10.5+ and iPhone OS, dictionary keys can also be enumerated more concisely using this NSFastEnumeration construct:
for (id key in aDictionary) {
// ... process it here ...
}
What is even more practical, structured data graphs may be easily created using Cocoa, especially NSDictionary (NSMutableDictionary). This can be illustrated with this compact example:
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"];
OCaml
The OCaml programming language provides three different associative containers. The simplest is a list of pairs:
# 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"
The code above uses OCaml's default hash function Hashtbl.hash, which is defined automatically for all types. If you wanted to use your own hash function, you can use the functor interface Hashtbl.Make to create a module, like with Map below.
Finally, functional maps (represented as immutable balanced binary trees):
# module StringMap = Map.Make(String);;
...
# let m = StringMap.add "Sally Smart" "555-9999" StringMap.empty
let m = StringMap.add "John Doe" "555-1212" m
let m = StringMap.add "J. Random Hacker" "553-1337" m;;
val m : string StringMap.t = <abstr>
# StringMap.find "John Doe" m;;
- : string = "555-1212"
Note that in order to use Map, you have to provide the functor Map.Make with a module which defines the key type and the comparison function. The third-party library ExtLib provides a polymorphic version of functional maps, called PMap, where you provide the comparison function when creating the map.
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.
OptimJ
The OptimJ programming language is an extension of Java 5. As java, Optimj provides maps. But, OptimJ also provides true associative arrays: java arrays are indexed with 0-based integers; associative arrays are indexed with any collection of keys.
String[String] phoneBook = {
"Sally Smart" -> "555-9999",
"John Doe" -> "555-1212",
"J. Random Hacker" -> "553-1337"
};
// String[String] is not a java type but an optimj type:
// associative array of strings indexed by strings.
// iterate over the values
for(String number : phoneBook) {
System.out.println(number);
}
// The previous statement prints: "555-9999" "555-1212" "553-1337"
// iterate over the keys
for(String name : phoneBook.keys) {
System.out.println(name + " -> " + phoneBook[name]);
}
// phoneBook[name] access a value by a key (it looks like java array access)
// i.e. phoneBook["John Doe"] returns "555-1212"
Of course, it is possible to define multi-dimensional arrays, to mix java array and associative arrays, to mix maps and associative arrays.
int[String][][double] a;
java.util.Map<String[Object], Integer> b;
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, and the standard Perl module Tie::RefHash enables hashes to be used with reference keys.
A hash variable is marked by a % sigil, to distinguish it from scalar, array and other data types. A hash literal is a key-value list, with the preferred form using Perl's => token, which is mostly semantically identical to the comma and makes the key-value association clearer:
%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 $name, "\n";
}
One can iterate through (key, value) pairs using the each function:
while (($name, $number) = each %phone_book) {
print 'Number for ', $name, ': ', $number, "\n";
}
A hash reference, which is a scalar value that points to a hash, is specified in literal form using curly braces as delimiters, with syntax otherwise similar to specifying a hash literal:
$phone_book = {
'Sally Smart' => '555-9999',
'John Doe' => '555-1212',
'J. Random Hacker' => '553-1337',
};
Values in a hash reference are accessed using the dereferencing operator:
print $phone_book->{'Sally Smart'};
When the hash contained in the hash reference needs to be referred to as a whole, as with the keys function, the syntax is as follows:
foreach $name (keys %{$phone_book}) {
print 'Number for ', $name, ': ', $phone_book->{$name}, "\n";
}
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.[6] This is why one in PHP can have non-consecutive numerically indexed arrays. The keys have to be integer or string (floating point numbers are truncated to integer), while values can be of arbitrary types, including other arrays and objects. The arrays are heterogeneous; a single array can have keys of different types. PHP's associative arrays can be used to represent trees, lists, stacks, queues and other common data structures not built into PHP.
An associative array can be declared using the following syntax:
$phonebook = array();
$phonebook['Sally Smart'] = '555-9999';
$phonebook['John Doe'] = '555-1212';
$phonebook['J. Random Hacker'] = '555-1337';
// or
$phonebook = array(
'Sally Smart' => '555-9999',
'John Doe' => '555-1212',
'J. Random Hacker' => '555-1337',
);
// or, as of PHP 5.4
$phonebook = [
'Sally Smart' => '555-9999',
'John Doe' => '555-1212',
'J. Random Hacker' => '555-1337',
];
// or
$phonebook['contacts']['Sally Smart']['number'] = '555-9999';
$phonebook['contacts']['John Doe']['number'] = '555-1212';
$phonebook['contacts']['J. Random Hacker']['number'] = '555-1337';
PHP can loop through an associative array as follows:
foreach($phonebook as $name => $number) {
echo 'Number for ', $name, ': ', $number, "\n";
}
// For the last array example it is used like this
foreach($phonebook['contacts'] as $name => $num) {
echo 'Name: ', $name, ', number: ', $num['number'], "\n";
}
PHP has an extensive set of functions to operate on arrays.
If you want an associative array that can use objects as keys instead of strings and integers, you can use the SplObjectStorage class from the Standard PHP Library (SPL).
Pike
Pike has built-in support for Associative Arrays, which are referred to as mappings. Mappings are created as follows:
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:%s\n", key, value);
}
Or using an iterator object:
Mapping.Iterator i = get_iterator(phonebook);
while (i->index()) {
write("%s:%s\n", 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");
PostScript
In PostScript, associative arrays are called dictionaries. In Level 1 PostScript they must be created explicitly, but Level 2 introduced direct declaration using the double-brace syntax:
% Level 1 declaration
3 dict dup begin
/red (rouge) def
/green (vert) def
/blue (bleu) def
end
% Level 2 declaration
<<
/red (rot)
/green (gruen)
/blue (blau)
>>
% Both methods leave the dictionary on the operand stack
Dictionaries can be accessed directly using get or implicitly by placing the dictionary on the dictionary stack using begin:
% With the previous two dictionaries still on the operand stack
/red get print % outputs 'rot'
begin
green print % outputs 'vert'
end
Dictionary contents can be iterated through using forall, though not in any particular order:
% Level 2 example
<<
/This 1
/That 2
/Other 3
>> {exch =print ( is ) print ==} forall
May well output:
That is 2
This is 1
Other is 3
Dictionaries can be augmented (up to their defined size only in Level 1) or altered using put, and entries can be removed using undef:
% define a dictionary for easy reuse:
/MyDict <<
/rouge (red)
/vert (gruen)
>> def
% add to it
MyDict /bleu (blue) put
% change it
MyDict /vert (green) put
% remove something
MyDict /rouge undef
Prolog
Some versions of Prolog include "dicts".[7]
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 an entry in Python simply use the array indexing operator. For example,
>>> phonebook['Sally Smart']
'555-9999'
An example loop iterating through all the keys of the dictionary:
>>> for key in phonebook:
... print key, phonebook[key]
Sally Smart 555-9999
J. Random Hacker 553-1337
John Doe 555-1212
Iterating through (key, value) tuples:
>>> for key, value in phonebook.iteritems():
... print key, value
Sally Smart 555-9999
J. Random Hacker 553-1337
John Doe 555-1212
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')
>>> phonebook.keys() # Only one key left
['J. Random Hacker']
Python 2.7 and 3.x also supports dictionary comprehensions, a compact syntax for generating a dictionary from any iterator:
>>> square_dict = {i: i*i for i in range(5)}
>>> square_dict
{0: 0, 1: 1, 2: 4, 3: 9, 4: 16}
>>> {key: value for key, value in phonebook.iteritems() if 'J' in key}
{'J. Random Hacker': '553-1337', 'John Doe': '555-1212'}
REXX
In REXX, associative arrays are called Stem variables or Compound variables.
KEY = 'Sally Smart'
PHONEBOOK.KEY = '555-9999'
KEY = 'John Doe'
PHONEBOOK.KEY = '555-1212'
KEY = 'J. Random 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.
Ruby
In Ruby a hash is used as follows:
irb(main):001:0> phonebook = {
irb(main):002:1* 'Sally Smart' => '555-9999',
irb(main):003:1* 'John Doe' => '555-1212',
irb(main):004:1* 'J. Random Hacker' => '553-1337'
irb(main):005:1> }
=> {"Sally Smart"=>"555-9999", "John Doe"=>"555-1212", "J. Random Hacker"=>"553-1337"}
irb(main):006:0> phonebook['John Doe']
=> "555-1212"
Ruby supports hash looping and iteration with the following syntax:
irb(main):007:0> ### iterate over keys and values
irb(main):008:0* phonebook.each {|key, value| puts key + " => " + value}
Sally Smart => 555-9999
John Doe => 555-1212
J. Random Hacker => 553-1337
=> {"Sally Smart"=>"555-9999", "John Doe"=>"555-1212", "J. Random Hacker"=>"553-1337"}
irb(main):009:0> ### iterate keys only
irb(main):010:0* phonebook.each_key {|key| puts key}
Sally Smart
John Doe
J. Random Hacker
=> {"Sally Smart"=>"555-9999", "John Doe"=>"555-1212", "J. Random Hacker"=>"553-1337"}
irb(main):011:0> ### iterate values only
irb(main):012:0* phonebook.each_value {|value| puts value}
555-9999
555-1212
553-1337
=> {"Sally Smart"=>"555-9999", "John Doe"=>"555-1212", "J. Random Hacker"=>"553-1337"}
Ruby also supports many other useful operations on hashes, such as merging hashes, selecting or rejecting elements that meet some criteria, inverting (swapping the keys and values), and flattening a hash into an array.
S-Lang
S-Lang has an associative array type.
For example:
phonebook = Assoc_Type[];
phonebook["Sally Smart"] = "555-9999"
phonebook["John Doe"] = "555-1212"
phonebook["J. Random Hacker"] = "555-1337"
You can also loop through an associated array in a number of ways. Here is one
foreach name (phonebook) {
vmessage ("%s %s", name, phonebook[name]);
}
To print a sorted-list, it is better to take advantage of S-lang's strong support for standard arrays:
keys = assoc_get_keys(phonebook);
i = array_sort(keys);
vals = assoc_get_values(phonebook);
array_map (Void_Type, &vmessage, "%s %s", keys[i], vals[i]);
Scala
Scala provides an immutable Map class as part of the scala.collection framework:
val phonebook = Map("Sally Smart" -> "555-9999",
"John Doe" -> "555-1212",
"J. Random Hacker" -> "553-1337")
Scala's type inference will work out that this is a Map[String, String]. To access the array:
phonebook.get("Sally Smart")
This returns an Option type, Scala's equivalent of a the Maybe monad in Haskell.
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'
Dictionary hashes/compares based on equality and holds strong references to both key and value. Variants exist which hash/compare on identity (IdentityDictionary) or keep weak references (WeakKeyDictionary / WeakValueDictionary). Because every object implements #hash, any object can be used as key (and of course also as value).
SNOBOL
SNOBOL is one of the first (if not the first) programming languages to use associative arrays. Associative arrays in SNOBOL are called Tables.
PHONEBOOK = TABLE()
PHONEBOOK['Sally Smart'] = '555-9999'
PHONEBOOK['John Doe'] = '555-1212'
PHONEBOOK['J. Random Hacker'] = '553-1337'
Standard ML
The SML'97 standard of the Standard ML programming language does not provide any associative containers. However, various implementations of Standard ML do provide associative containers.
The library of the popular Standard ML of New Jersey implementation provides a signature (somewhat like an "interface"), ORD_MAP, which defines a common interface for ordered functional (immutable) associative arrays. There are several general functors, BinaryMapFn, ListMapFn, RedBlackMapFn, and SplayMapFn, that allow you to create the corresponding type of ordered map (the types are a self-balancing binary search tree, sorted association list, red-black tree, and splay tree, respectively) using a user-provided structure to describe the key type and comparator. The functor returns a structure that follows the ORD_MAP interface. In addition, there are two pre-defined modules for associative arrays with integer keys: IntBinaryMap and IntListMap.
- structure StringMap = BinaryMapFn (struct
type ord_key = string
val compare = String.compare
end);
structure StringMap : ORD_MAP
- val m = StringMap.insert (StringMap.empty, "Sally Smart", "555-9999")
val m = StringMap.insert (m, "John Doe", "555-1212")
val m = StringMap.insert (m, "J. Random Hacker", "553-1337");
val m =
T
{cnt=3,key="John Doe",
left=T {cnt=1,key="J. Random Hacker",left=E,right=E,value="553-1337"},
right=T {cnt=1,key="Sally Smart",left=E,right=E,value="555-9999"},
value="555-1212"} : string StringMap.map
- StringMap.find (m, "John Doe");
val it = SOME "555-1212" : string option
SML/NJ also provides a polymorphic hash table:
- exception NotFound;
exception NotFound
- val m : (string, string) HashTable.hash_table = HashTable.mkTable (HashString.hashString, op=) (3, NotFound);
val m =
HT
{eq_pred=fn,hash_fn=fn,n_items=ref 0,not_found=NotFound(-),
table=ref [|NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,NIL,...|]}
: (string,string) HashTable.hash_table
- HashTable.insert m ("Sally Smart", "555-9999");
val it = () : unit
- HashTable.insert m ("John Doe", "555-1212");
val it = () : unit
- HashTable.insert m ("J. Random Hacker", "553-1337");
val it = () : unit
HashTable.find m "John Doe"; (* returns NONE if not found *)
val it = SOME "555-1212" : string option
- HashTable.lookup m "John Doe"; (* raises the exception if not found *)
val it = "555-1212" : string
Monomorphic hash tables are also supported using the HashTableFn functor.
Another Standard ML implementation, Moscow ML, also provides some associative containers. First, it provides polymorphic hash tables in the Polyhash structure. Also, some functional maps from the SML/NJ library above are available as Binarymap, Splaymap, and Intmap structures.
Tcl
There are two Tcl facilities that support associative array semantics. An array is a collection of variables. A dict is a full implementation of associative arrays.
dict
set phonebook [dict create {Sally Smart} 555-9999 {John Doe} 555-1212 {J. Random Hacker} 553-1337]
To lookup an item:
dict get $phonebook {John Doe}
To iterate through a dict:
foreach {name number} $phonebook {
puts "name: $name\nnumber: $number"
}
array
set {phonebook(Sally Smart)} 555-9999
set john {John Doe}
set phonebook($john) 555-1212
set {phonebook(J. Random Hacker)} 553-1337
If there is a literal space character in the variable name, it must be grouped using either curly brackets (no substitution performed) or double quotes (substitution is performed).
Alternatively, several array elements can be set in a single command by providing their mappings as a list (words containing whitespace are braced):
array set phonebook [list {Sally Smart} 555-9999 {John Doe} 555-1212 {J. Random Hacker} 553-1337]
To access one array entry and put it on standard output
puts $phonebook(Sally\ Smart)
The result is here
555-9999
To retrieve the entire array as a dictionary:
array get phonebook
The result can be (order of keys is unspecified, not because the dictionary is unordered, but because the array is):
{Sally Smart} 555-9999 {J. Random Hacker} 553-1337 {John Doe} 555-1212
Visual 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
MessageBox.Show(entry.Key & " = " & entry.Value)
Next
Windows PowerShell
Unlike many other command line interpreters, PowerShell has built-in, language-level support for defining associative arrays.
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 }
Entries can be separated by either a semicolon or a newline, e.g.:
$myOtherObject = @{ foo = 42
bar = $false ;
zaz = 3
}
Keys and values can be any .NET object type, e.g.:
$now = [DateTime]::Now
$tomorrow = $now.AddDays(1)
$ProcessDeletionSchedule = @{
(Get-Process notepad) = $now
(Get-Process calc) = $tomorrow
}
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:
$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 underlying .NET object:
$phonebook.Remove('Sally Smart')
Hash tables can be added, e.g.:
$hash1 = @{ a=1; b=2 }
$hash2 = @{ c=3; d=4 }
$hash3 = $hash1 + $hash2
Data serialization formats support
Many data serialization formats also support associative arrays (see this table)
JSON
In JSON, associative arrays are called objects. Keys can only be strings.
{
"Sally Smart": "555-9999",
"John Doe": "555-1212",
"J. Random Hacker": "555-1337"
}
YAML
Sally Smart: 555-9999
John Doe: 555-1212
J. Random Hacker: 555-1337
References
- ↑ "Associative Arrays". Retrieved 2011-02-01.
- ↑ https://reference.wolfram.com/language/ref/Association.html
- ↑ https://reference.wolfram.com/language/ref/Key.html
- ↑ https://reference.wolfram.com/language/ref/Keys.html
- ↑ https://reference.wolfram.com/language/ref/Values.html
- ↑ About the implementation of Arrays in PHP
- ↑ "Dicts: structures with named arguments".