Content deleted Content added
Mindmatrix (talk | contribs) update to Raku (programming language) |
m →F#: {{code}} |
||
| (136 intermediate revisions by 33 users not shown) | |||
Line 2:
{{TOC limit|3}}
This '''
==Language support==
Line 8:
The following is a comparison of [[associative array]]s (also "mapping", "hash", and "dictionary") in various programming languages.
===
For example:
<
phonebook["Sally Smart"] = "555-9999"
phonebook["John Doe"] = "555-1212"
phonebook["J. Random Hacker"] = "555-1337"
</syntaxhighlight>
<
for (name in phonebook) {
print name, " ", phonebook[name]
}
</syntaxhighlight>
<
{ # for every input line
multi[$1 SUBSEP $2]++;
Line 42:
}
}
</syntaxhighlight>
===C===
There is no standard implementation of
Another 3rd
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 Inc.|Apple]]'s cross-platform [[Core Foundation]] framework provides several basic data types. In particular, there are reference
===C#===
<!-- Note: Be aware when editing that this section and its subsections are linked to by the F# and Visual Basic .NET sections -->
[[C Sharp (programming language)|C#
====Creation====
The following demonstrates three means of populating a mutable dictionary:
* the <code>Add</code> method, which adds a key and value and throws an [[exception handling|exception]] if the key already exists in the dictionary
* assigning to the indexer, which overwrites any existing value, if present
* assigning to the backing property of the indexer, for which the indexer is [[syntactic sugar]] (not applicable to C#, see [[#F#|F#]] or [[#Visual Basic .NET|VB.NET]] examples)
<syntaxhighlight lang="csharp">
var dictionary = new Dictionary<string, string>();
dictionary["John Doe"] = "555-1212";
// Not allowed in C#.
//
</syntaxhighlight>
The dictionary can also be initialized during construction using a "collection initializer", which compiles to repeated calls to <code>Add</code>.
<syntaxhighlight lang="csharp">
var dictionary = new Dictionary<string, string> {
{ "Sally Smart", "555-9999" },
{ "John Doe", "555-1212" },
{ "J. Random Hacker", "553-1337" }
};
</syntaxhighlight>
===={{anchor|C# access}}Access by key====
Values are primarily retrieved using the indexer (which throws an exception if the key does not exist) and the <code>TryGetValue</code> method, which has an output parameter for the sought value and a Boolean return-value indicating whether the key was found.
<syntaxhighlight lang="csharp">
var sallyNumber = dictionary["Sally Smart"];
</syntaxhighlight>
<syntaxhighlight lang="csharp">
var sallyNumber = (dictionary.TryGetValue("Sally Smart", out var result) ? result : "n/a";
</syntaxhighlight>
In this example, the <code>sallyNumber</code> value will now contain the string <code>"555-9999"</code>.
===={{anchor|C# enumeration}}Enumeration====
A dictionary can be viewed as a sequence of keys, sequence of values, or sequence of pairs of keys and values represented by instances of the <code>KeyValuePair<TKey, TValue></code> type, although there is no guarantee of order. For a sorted dictionary, the programmer could choose to use a <code>SortedDictionary<TKey, TValue></code> or use the <code>.Sort</code> [[Language Integrated Query|LINQ]] extension method when enumerating.
The following demonstrates enumeration using a [[foreach loop]]:
<
// loop through the collection and display each entry.
foreach (KeyValuePair<string,string> kvp in
{
Console.WriteLine("Phone number for {0} is {1}", kvp.Key, kvp.Value);
}
</syntaxhighlight>
===
[[C++
<
#include <map>
#include <string>
Line 119:
phone_book.insert(std::make_pair("J. Random Hacker", "553-1337"));
}
</syntaxhighlight>
Or less efficiently, as
<
#include <map>
#include <string>
Line 132:
phone_book["J. Random Hacker"] = "553-1337";
}
</syntaxhighlight>
With the extension of [[C++11#Initializer lists|initialization lists]] in C++11, entries can be added during a map's construction as shown below:
<
#include <map>
#include <string>
Line 147:
};
}
</syntaxhighlight>
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;
</syntaxhighlight>
The same task in
<
for(const auto& curr : phone_book)
std::cout << curr.first << " = " << curr.second << std::endl;
</syntaxhighlight>
Using the structured binding available in [[C++17]]:
<
for (const auto& [name, number] : phone_book) {
std::cout << name << " = " << number << std::endl;
}
</syntaxhighlight>
In C++, the <code>std::map</code> class is [[Generic programming#Templates in C.2B.2B|templated]] which allows the [[data type]]s of keys and values to be different for different <code>map</code> instances. For a given instance of the <code>map</code> class the keys must be of the same base type. The same must be true for all of the values. Although <code>std::map</code> is typically implemented using a [[self-balancing binary search tree]], C++11 defines a second map called <code>[[std::unordered_map]]</code>, which
===
Initializing an empty dictionary and adding items in [[Cobra (programming language)|Cobra]]:
{{sxhl|2=python|1=<nowiki/>
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:
{{sxhl|2=python|1=<nowiki/>
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:
{{sxhl|2=python|1=<nowiki/>
for key, val in dic
print "[key]'s phone number is [val]"
}}
===ColdFusion Markup Language===
A structure in [[ColdFusion Markup Language]] (CFML) is equivalent to an associative array:
<syntaxhighlight lang=CFS>
dynamicKeyName = "John Doe";
phoneBook = {
Line 187 ⟶ 211:
writeOutput(phoneBook.UnknownComic); // ???
writeDump(phoneBook); // entire struct
</syntaxhighlight>
===D===
[[D programming language|D]] offers direct support for associative arrays in the core language; such arrays are implemented as a chaining hash table with binary trees.<ref>{{Cite web|title=Associative Arrays - D Programming Language|url=https://dlang.org/spec/hash-map.html|access-date=2021-05-07|website=dlang.org}}</ref> The equivalent example would be:
<
int main() {
string[ string ] phone_book;
Line 224:
return 0;
}
</syntaxhighlight>
Keys and values can be any types, but all the keys in an associative array must be of the same type, and the same goes for dependent values.
<
foreach (key, value; phone_book) {
writeln("Number for " ~ key ~ ": " ~ value );
}
</syntaxhighlight>
A property can be removed as follows:
<
phone_book.remove("Sally Smart");
</syntaxhighlight>
===Delphi===
[[Delphi (software)|Delphi]] supports several standard containers, including TDictionary<T>:
<syntaxhighlight lang="delphi">
uses
SysUtils,
Line 263:
Writeln(Format('Number for %s: %s',[Entry.Key, Entry.Value]));
end.
</syntaxhighlight>
<
procedure TForm1.Button1Click(Sender: TObject);
var
Line 290:
DataField.Free;
end;
</syntaxhighlight>
===
[[Erlang (programming language)|Erlang]] offers many
====Keylists====
Keylists are lists of [[tuple]]s, 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 <code>lists</code> module.
<
PhoneBook = [{"Sally
{"John Doe", "555-1212"},
{"J. Random Hacker", "553-1337"}].
</syntaxhighlight>
Accessing an element of the keylist can be done with the <code>lists:keyfind/3</code> function:
<
{_, Phone} = lists:keyfind("Sally
io:format("Phone number: ~s~n", [Phone]).
</syntaxhighlight>
====Dictionaries====
Dictionaries are implemented in the <code>dict</code> module of the standard library. A new dictionary is created using the <code>dict:new/0</code> function and new key/value pairs are stored using the <code>dict:store/3</code> 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).
</syntaxhighlight>
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"}]).
</syntaxhighlight>
The dictionary can be accessed using the <code>dict:find/2</code> function:
<
{ok, Phone} = dict:find("Sally Smith", PhoneBook),
io:format("Phone: ~s~n", [Phone]).
</syntaxhighlight>
In both cases, any Erlang term can be used as the key. Variations include the <code>orddict</code> module, implementing ordered dictionaries, and <code>gb_trees</code>, implementing general balanced trees.
====Maps====
Maps were introduced in OTP 17.0,<ref>{{Cite web|title=Erlang -- maps|url=https://erlang.org/doc/man/maps.html|access-date=2021-03-07|website=erlang.org}}</ref> and combine the strengths of keylists and dictionaries. A map is defined using the syntax <code>#{ K1 => V1, ... Kn => Vn }</code>:
<syntaxhighlight lang="erlang">
PhoneBook = #{"Sally Smith" => "555-9999",
"John Doe" => "555-1212",
"J. Random Hacker" => "553-1337"}.
</syntaxhighlight>
Basic functions to interact with maps are available from the <code>maps</code> module. For example, the <code>maps:find/2</code> function returns the value associated with a key:
<syntaxhighlight lang="erlang">
{ok, Phone} = maps:find("Sally Smith", PhoneBook),
io:format("Phone: ~s~n", [Phone]).
</syntaxhighlight>
Unlike dictionaries, maps can be pattern matched upon:
<syntaxhighlight lang="erlang">
#{"Sally Smith", Phone} = PhoneBook,
io:format("Phone: ~s~n", [Phone]).
</syntaxhighlight>
Erlang also provides syntax sugar for functional updates—creating a new map based on an existing one, but with modified values or additional keys:
<syntaxhighlight lang="erlang">
PhoneBook2 = PhoneBook#{
% the `:=` operator updates the value associated with an existing key
"J. Random Hacker" := "355-7331",
% the `=>` operator adds a new key-value pair, potentially replacing an existing one
"Alice Wonderland" => "555-1865"
}
</syntaxhighlight>
===F#===
===={{code|Map<'Key,'Value>}}====
At runtime, [[F Sharp (programming language)|F#]] provides the <code>Collections.Map<'Key,'Value></code> type, which is an immutable [[AVL tree]].
=====Creation=====
The following example calls the <code>Map</code> constructor, which operates on a list (a semicolon delimited sequence of elements enclosed in square brackets) of tuples (which in F# are comma-delimited sequences of elements).
<syntaxhighlight lang="fsharp">
let numbers =
[
Line 351 ⟶ 388:
"J. Random Hacker", "555-1337"
] |> Map
</syntaxhighlight>
=====
Values can be looked up via one of the <code>Map</code> members, such as its indexer or <code>Item</code> property (which throw an [[Exception handling|exception]] if the key does not exist) or the <code>TryFind</code> function, which returns an [[option type]] with a value of {{code|Some <result>|f#}}, for a successful lookup, or <code>None</code>, for an unsuccessful one. [[Pattern matching]] can then be used to extract the raw value from the result, or a default value can be set.
<syntaxhighlight lang="fsharp">
let sallyNumber = numbers.["Sally Smart"]
// or
let sallyNumber = numbers.Item("Sally Smart")
</syntaxhighlight>
<
let sallyNumber =
match numbers.TryFind("Sally Smart") with
| Some(number) -> number
| None -> "n/a"
</syntaxhighlight>
In both examples above, the <code>sallyNumber</code> value would contain the string <code>"555-9999"</code>.
===={{code|Dictionary<'TKey,'TValue>}}====
Because F# is a .NET language, it also has access to features of the [[.NET Framework]], including the {{code|System.Collections.Generic.Dictionary<'TKey,'TValue>|f#}} type (which is implemented as a [[hash table]]), which is the primary associative array type used in C# and Visual Basic. This type may be preferred when writing code that is intended to operate with other languages on the .NET Framework, or when the performance characteristics of a hash table are preferred over those of an AVL tree.
=====Creation=====
The <code>dict</code> function provides a means of conveniently creating a .NET dictionary that is not intended to be mutated; it accepts a sequence of tuples and returns an immutable object that implements {{code|IDictionary<'TKey,'TValue>|f#}}.
<syntaxhighlight lang="fsharp">
let numbers =
[
Line 383 ⟶ 420:
"J. Random Hacker", "555-1337"
] |> dict
</syntaxhighlight>
When a mutable dictionary is needed, the constructor of
<syntaxhighlight lang="fsharp">
let numbers = System.Collections.Generic.Dictionary<string, string>()
numbers.Add("Sally Smart", "555-9999")
numbers.["John Doe"] <- "555-1212"
numbers.Item("J. Random Hacker") <- "555-1337"
</syntaxhighlight>
=====
<code>IDictionary</code> instances have an indexer that is used in the same way as <code>Map</code>, although the equivalent to <code>TryFind</code> is <code>TryGetValue</code>, which has an output parameter for the sought value and a Boolean return value indicating whether the key was found.
<syntaxhighlight lang="fsharp">
let sallyNumber =
let mutable result = ""
if numbers.TryGetValue("Sally Smart", &result) then result else "n/a"
</syntaxhighlight>
F#
<
let sallyNumber =
match numbers.TryGetValue("Sally Smart") with
| true, number -> number
| _ -> "n/a"
</syntaxhighlight>
====Enumeration====
A dictionary or map can be enumerated using <code>Seq.map</code>.
<syntaxhighlight lang=fsharp>
// loop through the collection and display each entry.
numbers |> Seq.map (fun kvp -> printfn "Phone number for %O is %O" kvp.Key kvp.Value)
</syntaxhighlight>
===
[[Visual FoxPro]] implements mapping with the Collection Class.
<
mapping = NEWOBJECT("Collection")
mapping.Add("Daffodils", "flower2") && Add(object, key) – key must be character
Line 427 ⟶ 465:
object = mapping("flower2") && returns "Daffodils" (retrieve by key)
object = mapping(1) && returns "Daffodils" (retrieve by index)
</syntaxhighlight>
GetKey returns 0 if the key is not found.
===Go===
[[Go (programming language)|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: <code>map[keytype]valuetype</code>
Adding elements one at a time:
<syntaxhighlight lang="go">
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"
</syntaxhighlight>
A map literal:
<syntaxhighlight lang="go">
phone_book := map[string] string {
"Sally Smart": "555-9999",
Line 451 ⟶ 491:
"J. Random Hacker": "553-1337",
}
</syntaxhighlight>
Iterating through a map:
<syntaxhighlight lang="go">
// over both keys and values
for key, value := range phone_book {
Line 464 ⟶ 505:
fmt.Printf("Name: %s\n", key)
}
</syntaxhighlight>
===
The [[Haskell]] programming language
<
m = [("Sally Smart", "555-9999"), ("John Doe", "555-1212"), ("J. Random Hacker", "553-1337")]
main = print (lookup "John Doe" m)
</syntaxhighlight>
output:
Just "555-1212"
Note that the lookup function returns a "Maybe" value, which is "Nothing" if not found, or "Just
The [[Glasgow Haskell Compiler
One is polymorphic functional maps (represented as immutable balanced binary trees):
<
import qualified Data.Map as M
Line 491 ⟶ 532:
main = print (M.lookup "John Doe" m'' :: Maybe String)
</syntaxhighlight>
output:
Just "555-1212"
Line 499 ⟶ 540:
Finally, a polymorphic hash table:
<
import qualified Data.HashTable as H
Line 508 ⟶ 549:
foo <- H.lookup m "John Doe"
print foo
</syntaxhighlight>
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 [[Monad (functional programming)#IO monad|IO monad]].
===
In [[Java (programming language)|Java]] associative arrays are implemented as "maps"
<
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");
</syntaxhighlight>
The {{Javadoc:SE|java/util|Map|get(java.lang.Object)|name=get}} method is used to access a key; for example, the value of the expression <code>phoneBook.get("Sally Smart")</code> is <code>"555-9999"</code>. This code uses a hash map to store the associative array, by calling the constructor of the {{Javadoc:SE|java/util|HashMap}} class. However, since the code only uses methods common to the interface {{Javadoc:SE|java/util|Map}}, a self-balancing binary tree could be used by calling the constructor of the {{Javadoc:SE|java/util|TreeMap}} class (which implements the subinterface {{Javadoc:SE|java/util|SortedMap}}), without changing the definition of the <code>phoneBook</code> variable, or the rest of the code, or using other underlying data structures that implement the <code>Map</code> interface.
The hash function in Java, used by HashMap and HashSet, is provided by the {{Javadoc:SE|java/lang|Object|hashCode()}} method. Since every class in Java [[Inheritance (object-oriented programming)|inherits]] from {{Javadoc:SE|java/lang|Object}}, every object has a hash function. A class can [[Method overriding (programming)|override]] the default implementation of <code>hashCode()</code> to provide a custom hash function more in accordance with the properties of the object.
The <code>Object</code> class also contains the {{Javadoc:SE|name=equals(Object)|java/lang|Object|equals(java.lang.Object)}} method, which tests an object for equality with another object. Hashed data structures in Java rely on objects maintaining the following contract between their <code>hashCode()</code> and <code>equals()</code> methods:
For two objects ''a'' and ''b'',
<syntaxhighlight lang="java">
a.equals(b) == b.equals(a)
if a.equals(b), then a.hashCode() == b.hashCode()
</syntaxhighlight>
In order to maintain this contract, a class that overrides <code>equals()</code> must also override <code>hashCode()</code>, and
A further contract that a hashed data
Analogously, TreeMap, and other sorted data structures,
===
[[JavaScript]] (and its standardized version, [[ECMAScript]]) is a [[Prototype-based programming|prototype-based]] [[Object-oriented programming|object-oriented]] language.
====Map and WeakMap====
Modern JavaScript handles associative arrays, using the <code>Map</code> and <code>WeakMap</code> classes. A map does not contain any keys by default; it only contains what is explicitly put into it. The keys and values can be any type (including functions, objects, or any primitive).
=====Creation=====
A map can be initialized with all items during construction:
<syntaxhighlight lang="javascript">
const phoneBook = new Map([
["Sally Smart", "555-9999"],
["John Doe", "555-1212"],
["J. Random Hacker", "553-1337"],
]);
</syntaxhighlight>
Alternatively, you can initialize an empty map and then add items:
<syntaxhighlight lang="javascript">
const phoneBook = new Map();
phoneBook.set("Sally Smart", "555-9999");
phoneBook.set("John Doe", "555-1212");
phoneBook.set("J. Random Hacker", "553-1337");
</syntaxhighlight>
=====Access by key=====
Accessing an element of the map can be done with the <code>get</code> method:
<syntaxhighlight lang="javascript">
const sallyNumber = phoneBook.get("Sally Smart");
</syntaxhighlight>
In this example, the value <code>sallyNumber</code> will now contain the string "555-9999".
=====Enumeration=====
The keys in a map are ordered. Thus, when iterating through it, a map object returns keys in order of insertion. The following demonstrates enumeration using a for-loop:
<syntaxhighlight lang="javascript">
// loop through the collection and display each entry.
for (const [name, number] of phoneBook) {
console.log(`Phone number for ${name} is ${number}`);
}
</syntaxhighlight>
A key can be removed as follows:
<syntaxhighlight lang="javascript">
phoneBook.delete("Sally Smart");
</syntaxhighlight>
====Object====
An object is similar to a map—both let you set keys to values, retrieve those values, delete keys, and detect whether a value is stored at a key. For this reason (and because there were no built-in alternatives), objects historically have been used as maps.
However, there are important differences that make a map preferable in certain cases. In JavaScript an object is a mapping from property names to values—that is, an associative array with one caveat: the keys of an object must be either a string or a symbol (native objects and primitives implicitly converted to a string keys are allowed). Objects also include one feature unrelated to associative arrays: an object has a prototype, so it contains default keys that could conflict with user-defined keys. So, doing a lookup for a property will point the lookup to the prototype's definition if the object does not define the property.
An object literal is written as <code>{ property1: value1, property2: value2, ... }</code>. For example:
<syntaxhighlight lang="javascript">
const myObject = {
"Sally Smart": "555-9999",
"John Doe": "555-1212",
"J. Random Hacker": "553-1337",
};
</syntaxhighlight>
To prevent the lookup from using the prototype's properties, you can use the <code>Object.setPrototypeOf</code> function:
<syntaxhighlight lang=JavaScript>
Object.setPrototypeOf(myObject, null);
</syntaxhighlight>
As of ECMAScript 5 (ES5), the prototype can also be bypassed by using <code>Object.create(null)</code>:
<syntaxhighlight lang=JavaScript>
const myObject = Object.create(null);
Object.assign(myObject, {
"Sally Smart": "555-9999",
"John Doe": "555-1212",
"J. Random Hacker": "553-1337",
});
</syntaxhighlight>
If the property name is a valid identifier, the quotes can be omitted, e.g.:
<
</syntaxhighlight>
Lookup is written using property
<
myObject["John Doe"]
myOtherObject.foo
</syntaxhighlight>
You can also loop through all enumerable properties and associated values as follows (a for-in loop):
<
for (
}
</syntaxhighlight>
Or (a for-of loop):
<syntaxhighlight lang=JavaScript>
for (const [property, value] of Object.entries(myObject)) {
console.log(`${property} = ${value}`);
}
</syntaxhighlight>
A property can be removed as follows:
<
delete myObject["Sally Smart"];
</syntaxhighlight>
As mentioned before, properties are strings
<
myObject[1]
myObject[[
myObject[{ toString
</syntaxhighlight>
In modern JavaScript it's considered bad form to use the Array type as an associative array. Consensus is that the Object type and <code>Map</code>/<code>WeakMap</code> classes are best for this purpose. The reasoning behind this is that if Array is extended via prototype and Object is kept pristine, for and for-in loops will work as expected on associative 'arrays'. This issue has been brought to the fore by the popularity of JavaScript frameworks that make heavy and sometimes indiscriminate use of prototypes to extend JavaScript's inbuilt types.
See [http://blog.metawrap.com/2006/05/30/june-6th-is-javascript-array-and-object-prototype-awareness-day/ JavaScript Array And Object Prototype Awareness Day] for more information on the issue.
===
In [[Julia (programming language)|Julia]], the following operations manage associative arrays.
Declare dictionary:
<
</syntaxhighlight>
Access element:
<syntaxhighlight lang="julia">
phonebook["Sally Smart"]
</syntaxhighlight>
Add element:
<syntaxhighlight lang="julia">
</syntaxhighlight>
Delete element:
<syntaxhighlight lang="julia">
delete!(phonebook, "Sally Smart")
</syntaxhighlight>
Get keys and values as [[Iterator#Implicit iterators|iterables]]:
<syntaxhighlight lang="julia">
keys(phonebook)
values(phonebook)
</syntaxhighlight>
===KornShell 93, and compliant shells===
In [[Korn Shell|KornShell]] 93, and compliant shells (ksh93, bash4...), the following operations can be used with associative arrays.
<!-- Tested in ksh93 r -->
Definition:
<syntaxhighlight lang="ksh">
typeset -A phonebook; # ksh93; in bash4+, "typeset" is a synonym of the more preferred "declare", which works identically in this case
phonebook=(["Sally Smart"]="555-9999" ["John Doe"]="555-1212" ["[[J. Random Hacker]]"]="555-1337");
</syntaxhighlight>
Dereference:
<
</syntaxhighlight>
===
[[Lisp programming language|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"))
</syntaxhighlight>
The syntax <code>(x . y)</code> is used to indicate a [[cons|<code>cons</code>ed]] pair. Keys and values need not be the same type within an alist. Lisp and [[Scheme (programming language)|Scheme]] provide operators such as <code>assoc</code> to manipulate alists in ways similar to associative arrays.
A set of operations specific to the handling of association lists exists for [[Common Lisp]], each of these working non-destructively.
To add an entry the <code>acons</code> function is employed, creating and returning a new association list. An association list in Common Lisp mimicks a stack, that is, adheres to the last-in-first-out (LIFO) principle, and hence prepends to the list head.
<
(let ((phone-book NIL))
(setf phone-book (acons "Sally Smart" "555-9999" phone-book))
(setf phone-book (acons "John Doe" "555-1212" phone-book))
(setf phone-book (acons "J. Random Hacker" "555-1337" phone-book)))
</syntaxhighlight>
This function can
<
;; The effect of
;; (cons (cons KEY VALUE) ALIST)
Line 673 ⟶ 794:
(let ((phone-book '(("Sally Smart" . "555-9999") ("John Doe" . "555-1212"))))
(cons (cons "J. Random Hacker" "555-1337") phone-book))
</syntaxhighlight>
Of course, the destructive <code>push</code> operation also allows inserting entries into an association list, an entry having to constitute a key-value cons in order to retain the mapping's validity.
<
(push (cons "Dummy" "123-4567") phone-book)
</syntaxhighlight>
Searching for an entry by its key is performed via <code>assoc</code>, which might be configured
<
(assoc "John Doe" phone-book :test #'string=)
</syntaxhighlight>
Two generalizations of <code>assoc</code> exist: <code>assoc-if</code> expects a predicate function
<
;; Find the first entry whose key equals "John Doe".
(assoc-if
Line 701 ⟶ 822:
(member key '("Sally Smart" "John Doe") :test #'string=))
phone-book)
</syntaxhighlight>
The inverse process, the detection of an entry by its value, utilizes <code>rassoc</code>.
<
;; Find the first entry with a value of "555-9999".
;; We test the entry string values with the "string=" predicate.
(rassoc "555-9999" phone-book :test #'string=)
</syntaxhighlight>
The corresponding generalizations <code>rassoc-if</code> and <code>rassoc-if-not</code> exist.
<
;; Finds the first entry whose value is "555-9999".
(rassoc-if
Line 725 ⟶ 846:
(string= value "555-9999"))
phone-book)
</syntaxhighlight>
All of the
<
;; Find an entry with the key "John Doe" and the value "555-1212".
(find (cons "John Doe" "555-1212") phone-book :test #'equal)
</syntaxhighlight>
Deletion, lacking a specific counterpart, is based upon the list facilities, including destructive ones.
<
;; Create and return an alist without any entry whose key equals "John Doe".
(remove-if
Line 742 ⟶ 863:
(string= (car entry) "John Doe"))
phone-book)
</syntaxhighlight>
Iteration is accomplished
<
;; Iterate via "map".
(map NIL
Line 758 ⟶ 879:
(destructuring-bind (key . value) entry
(format T "~&~s => ~s" key value)))
</syntaxhighlight>
<
;; Return a vector of the "phone-book" values.
(map 'vector #'cdr phone-book)
Line 772 ⟶ 893:
(cons (reverse key) (reverse value))))
phone-book)
</syntaxhighlight>
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 (programming language)|Scheme]] they are implemented in [[Scheme Requests for Implementation|SRFI]] 69. Hash tables have greater overhead than alists, but provide much faster access when there are many elements. A further characteristic
Common Lisp hash tables are constructed via the <code>make-hash-table</code> function, whose arguments encompass, among other configurations, a predicate to test the entry key
<
(let ((phone-book (make-hash-table :test #'equal)))
(setf (gethash "Sally Smart" phone-book) "555-9999")
(setf (gethash "John Doe" phone-book) "555-1212")
(setf (gethash "J. Random Hacker" phone-book) "553-1337"))
</syntaxhighlight>
The <code>gethash</code> function permits
<
(gethash "John Doe" phone-book)
</syntaxhighlight>
Additionally,
<
(gethash "Incognito" phone-book 'no-such-key)
</syntaxhighlight>
An invocation of <code>gethash</code> actually returns two values: the value or substitute value for the key and a boolean indicator,
<
(multiple-value-bind (value contains-key) (gethash "Sally Smart" phone-book)
(if contains-key
(format T "~&The associated value is: ~s" value)
(format T "~&The key could not be found.")))
</syntaxhighlight>
Use <code>remhash</code> for deleting the entry associated with a key.
<
(remhash "J. Random Hacker" phone-book)
</syntaxhighlight>
<code>clrhash</code> completely empties the
<
(clrhash phone-book)
</syntaxhighlight>
The dedicated <code>maphash</code> function
<
(maphash
#'(lambda (key value)
(format T "~&~s => ~s" key value))
phone-book)
</syntaxhighlight>
Alternatively, the <code>loop</code> construct makes provisions for iterations,
<
;; Iterate the keys and values of the hash table.
(loop
Line 840 ⟶ 961:
for value being the hash-values of phone-book
do (print value))
</syntaxhighlight>
A further option
<
(with-hash-table-iterator (entry-generator phone-book)
(loop do
Line 851 ⟶ 972:
(format T "~&~s => ~s" key value)
(loop-finish)))))
</syntaxhighlight>
It is easy to construct composite abstract data types in Lisp, using structures
===
[[LPC (programming language)|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 <code>([ key_1 : value_1, key_2 : value_2 ])</code>. Procedural
<
mapping phone_book = ([]);
phone_book["Sally Smart"] = "555-9999";
phone_book["John Doe"] = "555-1212";
phone_book["J. Random Hacker"] = "555-1337";
</syntaxhighlight>
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. <code>if(member(phone_book, "John Smith")) write("John Smith is listed.\n");</code>
Deletion is accomplished using a function called either m_delete() or map_delete(), depending on the driver
LPC drivers of the
<
mapping phone_book = ([:2]);
phone_book["Sally Smart", 0] = "555-9999";
Line 879 ⟶ 1,000:
phone_book["J. Random Hacker", 0] = "555-1337";
phone_book["J. Random Hacker", 1] = "77 Massachusetts Avenue";
</syntaxhighlight>
LPC drivers modern enough to support a foreach() construct
===Lua===
In [[Lua programming language|Lua]], "table" is a fundamental type that can be used either as an array (numerical index, fast) or as an 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 <code>{ value, key = value, [index] = value, ["non id string"] = value }</code>. For example:
<
phone_book = {
["Sally Smart"] = "555-9999",
Line 903 ⟶ 1,025:
-- Table and function (and other types) can also be used as keys
}
</syntaxhighlight>
If the key is a valid identifier (not a
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
</syntaxhighlight>
You can also loop through all keys and associated values with iterators or for
<
simple = { [true] = 1, [false] = 0, [3.14] = math.pi, x = 'x', ["!"] = 42 }
function FormatElement(key, value)
Line 932 ⟶ 1,054:
until k == nil
print""
</syntaxhighlight>
An entry can be removed by setting it to nil:
<
simple.x = nil
</syntaxhighlight>
Likewise, you can overwrite values or add them:
<
simple['%'] = "percent"
simple['!'] = 111
</syntaxhighlight>
===Mathematica and Wolfram Language===
[[Mathematica]] and [[Wolfram Language]] use the Association expression to represent associative arrays.<ref>{{cite web|url=https://reference.wolfram.com/language/ref/Association.html|title=Association (<-...->)—Wolfram Language Documentation|website=reference.wolfram.com}}</ref>
<syntaxhighlight lang="mathematica">
phonebook = <| "Sally Smart" -> "555-9999",
"John Doe" -> "555-1212",
"J. Random Hacker" -> "553-1337" |>;
</syntaxhighlight>
To access:<ref>{{cite web|url=https://reference.wolfram.com/language/ref/Key.html|title=Key—Wolfram Language Documentation|website=reference.wolfram.com}}</ref>
<syntaxhighlight lang="mathematica">
phonebook[[Key["Sally Smart"]]]
</syntaxhighlight>
If the keys are strings, the Key keyword is not necessary, so:
<syntaxhighlight lang="mathematica">
phonebook[["Sally Smart"]]
</syntaxhighlight>
Keys[phonebook]
Values[phonebook]
===
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, global arrays stored on disk which are available concurrently
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
WRITE "Phone Number :",^phonebook("Sally Smart"),!
Line 986 ⟶ 1,114:
FOR S NAME=$ORDER(^phonebook(NAME)) QUIT:NAME="" WRITE NAME," Phone Number :",^phonebook(NAME),!
===
[[Cocoa (API)|Cocoa]] and [[GNUstep]], written in [[Objective-C]], handle associative arrays using <code>NSMutableDictionary</code> (a mutable version of <code>NSDictionary</code>) class cluster. This class allows assignments between any two objects
<
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"];
</syntaxhighlight>
To access assigned objects, this command may be used:
<
id anObject = [aDictionary objectForKey:@"Sally Smart"];
</syntaxhighlight>
All keys or values can be
<
NSEnumerator *keyEnumerator = [aDictionary keyEnumerator];
id key;
Line 1,011 ⟶ 1,139:
// ... process it here ...
}
</syntaxhighlight>
<
for (id key in aDictionary) {
// ... process it here ...
}
</syntaxhighlight>
What is even more practical, structured data graphs may be easily created using [[Cocoa (API)|Cocoa]], especially <code>NSDictionary</code> (<code>NSMutableDictionary</code>). This can be illustrated with this compact example:
<
NSDictionary *aDictionary =
[NSDictionary dictionaryWithObjectsAndKeys:
Line 1,034 ⟶ 1,162:
nil], @"hackers",
nil];
</syntaxhighlight>
<
id anObject = [aDictionary valueForKeyPath:@"students.Sally Smart"];
</syntaxhighlight>
===
The [[OCaml]] programming language provides three different associative containers. The simplest is a list of pairs:
<
# let m = [
"Sally Smart", "555-9999";
Line 1,057 ⟶ 1,185:
# List.assoc "John Doe" m;;
- : string = "555-1212"
</syntaxhighlight>
The second is a polymorphic hash table:
<
# let m = Hashtbl.create 3;;
val m : ('_a, '_b) Hashtbl.t = <abstr>
Line 1,070 ⟶ 1,198:
# Hashtbl.find m "John Doe";;
- : string = "555-1212"
</syntaxhighlight>
The code above uses OCaml's default hash function <code>Hashtbl.hash</code>, which is defined automatically for all types.
Finally, functional maps (represented as immutable balanced binary trees):
<
# module StringMap = Map.Make(String);;
...
Line 1,085 ⟶ 1,213:
# StringMap.find "John Doe" m;;
- : string = "555-1212"
</syntaxhighlight>
Note that in order to use <code>Map</code>, you have to provide the functor <code>Map.Make</code> 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
Lists of pairs and functional maps both provide a purely functional interface.
===
{{
The [[OptimJ]] programming language is an extension of Java 5. As
<
String[String] phoneBook = {
"Sally Smart" -> "555-9999",
"John Doe" -> "555-1212",
"J. Random Hacker" -> "553-1337"
};
Line 1,106 ⟶ 1,234:
// iterate over the values
for (String number : phoneBook) {
System.out.println(number);
}
Line 1,113 ⟶ 1,241:
// 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"
</syntaxhighlight>
Of course, it is possible to define multi-dimensional arrays, to mix
<
</syntaxhighlight>
===
[[Perl 5]] has built-in, language-level support for associative arrays. Modern Perl
A hash variable is marked by a <code>%</code> [[sigil (computer programming)|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 <code>=></code> token, which is
<
my %phone_book = (
'Sally Smart' => '555-9999',
Line 1,139 ⟶ 1,267:
'J. Random Hacker' => '553-1337',
);
</syntaxhighlight>
Accessing a hash element uses the syntax <code>$hash_name{$key}</code> – the key is surrounded by
The list of keys and values can be extracted using the built-in functions <code>keys</code> and <code>values</code>, respectively. So, for example, to print all the keys of a hash:
<
foreach $name (keys %phone_book) {
print $name, "\n";
}
</syntaxhighlight>
One can iterate through (key, value) pairs using the <code>each</code> function:
<
while (($name, $number) = each %phone_book) {
print 'Number for ', $name, ': ', $number, "\n";
}
</syntaxhighlight>
A hash
<
my $phone_book = {
'Sally Smart' => '555-9999',
Line 1,167 ⟶ 1,295:
'J. Random Hacker' => '553-1337',
};
</syntaxhighlight>
Values in a hash reference are accessed using the dereferencing operator:
<
print $phone_book->{'Sally Smart'};
</syntaxhighlight>
When the hash contained in the hash reference needs to be referred to as a whole, as with the <code>keys</code> function, the syntax is as follows:
<
foreach $name (keys %{$phone_book}) {
print 'Number for ', $name, ': ', $phone_book->{$name}, "\n";
}
</syntaxhighlight>
===Perl
[[Raku (programming language)|Perl 6]], renamed as "Raku", also has built-in, language-level support for associative arrays, which are referred to as ''hashes'' or as objects performing the
A hash variable is typically marked by a <code>%</code> [[sigil (computer programming)|sigil]], to visually distinguish it from scalar, array, and other data types, and to define its behaviour towards iteration. A hash literal is a key-value list, with the preferred form using Perl's <code>=></code> token, which makes the key-value association clearer:
<
my %phone-book =
'Sally Smart' => '555-9999',
Line 1,194 ⟶ 1,322:
'J. Random Hacker' => '553-1337',
;
</syntaxhighlight>
Accessing a hash element uses the syntax <code>%hash_name{$key}</code> – the key is surrounded by
The list of keys and values can be extracted using the built-in functions <code>keys</code> and <code>values</code>, respectively. So, for example, to print all the keys of a hash:
<
for %phone-book.keys -> $name {
say $name;
}
</syntaxhighlight>
By default, when iterating
<
for %phone-book -> $entry {
say "Number for $entry.key(): $entry.value()"; # using extended interpolation features
}
</syntaxhighlight>
It
<
for %phone-book.kv -> $name, $number {
say "Number for $name: $number";
}
</syntaxhighlight>
<
sub list-phone-book(%pb) {
for %pb.kv -> $name, $number {
Line 1,231 ⟶ 1,359:
}
list-phone-book(%phone-book);
</syntaxhighlight>
<
# Define a hash whose keys may only be integer numbers ("Int" type).
my %numbersWithNames{Int};
Line 1,244 ⟶ 1,372:
# This will cause an error, as strings as keys are invalid.
%numbersWithNames.push("key" => "two");
</syntaxhighlight>
===
[[PHP]]'s built-in array type is, in reality, an associative array. Even when using numerical indexes, PHP internally stores
An associative array can be declared using the following syntax:
<
$phonebook = array();
$phonebook['Sally Smart'] = '555-9999';
Line 1,278 ⟶ 1,406:
$phonebook['contacts']['John Doe']['number'] = '555-1212';
$phonebook['contacts']['J. Random Hacker']['number'] = '555-1337';
</syntaxhighlight>
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";
}
</syntaxhighlight>
PHP has an
===
[[Pike (programming language)|Pike]] has built-in support for
<
mapping(string:string) phonebook = ([
"Sally Smart":"555-9999",
Line 1,306 ⟶ 1,434:
"J. Random Hacker":"555-1337"
]);
</syntaxhighlight>
Accessing and testing for presence in mappings is done using the indexing operator. So <code>phonebook["Sally Smart"]</code> would return the string <code>"555-9999"</code>, and <code>phonebook["John Smith"]</code> would return 0.
Iterating through a mapping can be done using
<
foreach(phonebook; string key; string value) {
write("%s:%s\n", key, value);
}
</syntaxhighlight>
Or using an iterator object:
<
Mapping.Iterator i = get_iterator(phonebook);
while (i->index()) {
Line 1,326 ⟶ 1,454:
i->next();
}
</syntaxhighlight>
Elements of a mapping can be removed using <code>m_delete</code>, which returns the value of the removed index:
<
string sallys_number = m_delete(phonebook, "Sally Smart");
</syntaxhighlight>
===
In [[PostScript]], associative arrays are called dictionaries. In Level 1 PostScript they must be created explicitly, but Level 2 introduced direct declaration using
<
% Level 1 declaration
3 dict dup begin
Line 1,353 ⟶ 1,481:
% Both methods leave the dictionary on the operand stack
</syntaxhighlight>
Dictionaries can be accessed directly, using <code>get</code>, or implicitly, by placing the dictionary on the dictionary stack using <code>begin</code>:
<syntaxhighlight lang="postscript">
% With the previous two dictionaries still on the operand stack
/red get print % outputs 'rot'
Line 1,363 ⟶ 1,492:
green print % outputs 'vert'
end
</syntaxhighlight>
Dictionary contents can be iterated through using
<
% Level 2 example
<<
Line 1,374 ⟶ 1,503:
/Other 3
>> {exch =print ( is ) print ==} forall
</syntaxhighlight>
Which may output:
<syntaxhighlight lang="postscript">
That is 2
This is 1
Other is 3
</syntaxhighlight>
Dictionaries can be augmented (up to their defined size only in Level 1) or altered using
<
% define a dictionary for easy reuse:
/MyDict <<
Line 1,398 ⟶ 1,529:
% remove something
MyDict /rouge undef
</syntaxhighlight>
=== Prolog ===
Some versions of [[Prolog]] include dictionary ("
===
In [[Python (programming language)|Python]], associative arrays are called
<
phonebook = {
}
</syntaxhighlight>
<
>>> phonebook[
'555-9999'
</syntaxhighlight>
Loop [[iterator#Python|iterating]] through all the keys of the dictionary:
<
>>> for key in phonebook:
... print(key, phonebook[key])
Line 1,430 ⟶ 1,560:
J. Random Hacker 553-1337
John Doe 555-1212
</syntaxhighlight>
Iterating through (key, value) tuples:
<
>>> for key, value in phonebook.items():
... print(key, value)
Line 1,440 ⟶ 1,570:
J. Random Hacker 553-1337
John Doe 555-1212
</syntaxhighlight>
Dictionary keys can be individually deleted using the <code>del</code> statement. The corresponding value can be returned before the key-value pair
<
>>> del phonebook[
>>> val = phonebook.pop(
>>> phonebook.keys() # Only one key left
['J. Random Hacker']
</syntaxhighlight>
Python 2.7 and 3.x also support [https://peps.python.org/pep-0274/ dict comprehensions] (similar to [[list comprehension]]s), a compact syntax for generating a dictionary from any iterator:
<syntaxhighlight lang="python">
>>> 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.items() if
{'J. Random Hacker': '553-1337', 'John Doe': '555-1212'}
</syntaxhighlight>
Strictly speaking, a dictionary is a super-set of an associative array, since neither the keys or values are limited to a single datatype. One could think of a dictionary as an
<
phonebook = {
14:
}
</syntaxhighlight>
The dictionary keys must be of an [[Immutable object|immutable]] data type. In Python, strings are immutable due to their method of implementation.
===
In [[Red (programming language)|Red]] the built-in <code>map!</code><ref>{{cite web|url=https://doc.red-lang.org/en/datatypes/map.html|title=Map! datatype|website=doc.red-lang.org}}</ref> datatype provides an associative array
A map can be written as a literal, such as <code>#(key1 value1 key2 value2 ...)</code>, or can be created using <code>make map! [key1 value1 key2 value2 ...]</code>:
<syntaxhighlight lang="red">
Red [Title:"My map"]
my-map: make map! [
"Sally Smart" "555-9999"
Line 1,484 ⟶ 1,617:
"J. Random Hacker" "553-1337"
]
; Red preserves case for both keys and values, however lookups are case insensitive by default; it is possible to force case sensitivity using the <code>/case</code> refinement for <code>select</code> and <code>put</code>.
; It is of course possible to use <code>word!</code> values as keys, in which case it is generally preferred to use <code>set-word!</code> values when creating the map, but any word type can be used for lookup or creation.
my-other-map: make map! [foo: 42 bar: false]
; Notice that the block is not reduced or evaluated in any way, therefore in the above example the key <code>bar</code> is associated with the <code>word!</code> <code>false</code> rather than the <code>logic!</code> value false; literal syntax can be used if the latter is desired:
my-other-map: make map! [foo: 42 bar: #[false]]
; or keys can be added after creation:
my-other-map: make map! [foo: 42]
my-other-map/bar: false
; Lookup can be written using <code>path!</code> notation or using the <code>select</code> action:
select my-map "Sally Smart"
my-other-map/foo
; You can also loop through all keys and values with <code>foreach</code>:
foreach [key value] my-map [
print [key "is associated to" value]
]
; A key can be removed using <code>remove/key</code>:
remove/key my-map "Sally Smart"
</syntaxhighlight>
===
In [[REXX]], associative arrays are called
<
KEY = 'Sally Smart'
PHONEBOOK.KEY = '555-9999'
Line 1,538 ⟶ 1,659:
KEY = 'J. Random Hacker'
PHONEBOOK.KEY = '553-1337'
</syntaxhighlight>
Stem variables with numeric keys typically start at 1 and go up from there. The 0
<
NAME.1 = 'Sally Smart'
NAME.2 = 'John Doe'
NAME.3 = 'J. Random Hacker'
NAME.0 = 3
</syntaxhighlight>
REXX has no easy way of automatically accessing the keys
keys are stored in a separate associative array, with numeric keys.
===
In [[Ruby programming language|Ruby]] a hash table is used as follows:
<syntaxhighlight lang="rb">
phonebook = {
'Sally Smart' => '555-9999',
'John Doe' => '555-1212',
}
phonebook['John Doe']
</syntaxhighlight>
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}
Line 1,589 ⟶ 1,707:
553-1337
=> {"Sally Smart"=>"555-9999", "John Doe"=>"555-1212", "J. Random Hacker"=>"553-1337"}
</syntaxhighlight>
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.
===Rust===
The [[Rust (programming language)|Rust]] standard library provides a hash map (<code>std::collections::HashMap</code>) and a [[B-tree]] map (<code>std::collections::BTreeMap</code>). They share several methods with the same names, but have different requirements for the types of keys that can be inserted. The <code>HashMap</code> requires keys to implement the <code>Eq</code> ([[equivalence relation]]) and <code>Hash</code> (hashability) traits and it stores entries in an unspecified order, and the <code>BTreeMap</code> requires the <code>Ord</code> ([[total order]]) trait for its keys and it stores entries in an order defined by the key type. The order is reflected by the default iterators.
<syntaxhighlight lang="rust">
use std::collections::HashMap;
let mut phone_book = HashMap::new();
phone_book.insert("Sally Smart", "555-9999");
phone_book.insert("John Doe", "555-1212");
phone_book.insert("J. Random Hacker", "555-1337");
</syntaxhighlight>
The default iterators visit all entries as tuples. The <code>HashMap</code> iterators visit entries in an unspecified order and the <code>BTreeMap</code> iterator visits entries in the order defined by the key type.
<syntaxhighlight lang="rust">
for (name, number) in &phone_book {
println!("{} {}", name, number);
}
</syntaxhighlight>
There is also an iterator for keys:
<syntaxhighlight lang="rust">
for name in phone_book.keys() {
println!("{}", name);
}
</syntaxhighlight>
===S-Lang===
[[S-Lang]] has an associative array type:
<
phonebook = Assoc_Type[];
phonebook["Sally Smart"] = "555-9999"
phonebook["John Doe"] = "555-1212"
phonebook["J. Random Hacker"] = "555-1337"
</syntaxhighlight>
You can also loop through an associated array in a number of ways
<
foreach name (phonebook) {
vmessage ("%s %s", name, phonebook[name]);
}
</syntaxhighlight>
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]);
</syntaxhighlight>
===
[[Scala (programming language)|Scala]] provides an immutable <code>Map</code> class as part of the <code>scala.collection</code> framework:
<
val phonebook = Map("Sally Smart" -> "555-9999",
"John Doe" -> "555-1212",
"J. Random Hacker" -> "553-1337")
</syntaxhighlight>
Scala's [[type inference]] will
<
phonebook.get("Sally Smart")
</syntaxhighlight>
This returns an <code>Option</code> type, Scala's equivalent of
===
In [[Smalltalk]] a
<
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'.
</syntaxhighlight>
To access an entry the message <code>#at:</code> is sent to the dictionary object
<
phonebook at: 'Sally Smart'
</syntaxhighlight>
Which gives:
<
'555-9999'
</syntaxhighlight>
A dictionary hashes, or compares, based on equality and marks both key and value as
[[Garbage collection (computer science)#Strong and weak references|strong references]]. Variants exist in which hash/compare on identity (IdentityDictionary) or keep [[Garbage collection (computer science)#Strong and weak references|weak references]] (WeakKeyDictionary / WeakValueDictionary).
Because every object implements #hash, any object can be used as key (and of course also as value).
===
[[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'
</syntaxhighlight>
===
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]] (SML/NJ) implementation provides a signature (somewhat like an "interface"), <code>ORD_MAP</code>, which defines a common interface for ordered functional (immutable) associative arrays. There are several general
<
- structure StringMap = BinaryMapFn (struct
type ord_key = string
Line 1,700 ⟶ 1,840:
- StringMap.find (m, "John Doe");
val it = SOME "555-1212" : string option
</syntaxhighlight>
SML/NJ also provides a polymorphic hash table:
<
- exception NotFound;
exception NotFound
Line 1,723 ⟶ 1,863:
- HashTable.lookup m "John Doe"; (* raises the exception if not found *)
val it = "555-1212" : string
</syntaxhighlight>
Monomorphic hash tables are also supported, using the <code>HashTableFn</code> functor.
Another Standard ML implementation, [[Moscow ML]], also provides some associative containers. First, it provides polymorphic hash tables in the <code>Polyhash</code> structure. Also, some functional maps from the SML/NJ library above are available as <code>Binarymap</code>, <code>Splaymap</code>, and <code>Intmap</code> structures.
===
There are two [[Tcl]] facilities that support associative
====array====
<syntaxhighlight lang=Tcl>
set {phonebook(Sally Smart)} 555-9999
set john {John Doe}
set phonebook($john) 555-1212
set {phonebook(J. Random Hacker)} 553-1337
</syntaxhighlight>
If there is a
Alternatively, several array elements can be set
<
array set phonebook [list {Sally Smart} 555-9999 {John Doe} 555-1212 {J. Random Hacker} 553-1337]
</syntaxhighlight>
To access one array entry and put it
<
puts $phonebook(Sally\ Smart)
</syntaxhighlight>
Which returns this result:
<
555-9999
</syntaxhighlight>
To retrieve the entire array as a dictionary:
<
array get phonebook
</syntaxhighlight>
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
</syntaxhighlight>
===
<syntaxhighlight lang=Tcl>
set phonebook [dict create {Sally Smart} 555-9999 {John Doe} 555-1212 {J. Random Hacker} 553-1337]
</syntaxhighlight>
To look up an item:
<syntaxhighlight lang=Tcl>
dict get $phonebook {John Doe}
</syntaxhighlight>
To iterate through a dict:
<syntaxhighlight lang=Tcl>
foreach {name number} $phonebook {
puts "name: $name\nnumber: $number"
}
</syntaxhighlight>
=== Visual Basic ===
[[Visual Basic]] can use the Dictionary class from the [[Windows Scripting Host|Microsoft Scripting Runtime]] (which is shipped with Visual Basic 6). There is no standard implementation common to all versions:
<syntaxhighlight lang="vbnet">
' Requires a reference to SCRRUN.DLL in Project Properties
Dim phoneBook As New Dictionary
Line 1,805 ⟶ 1,943:
MsgBox name & " = " & phoneBook(name)
Next
</syntaxhighlight>
===
[[Visual Basic .NET]] uses the collection classes provided by the [[.NET Framework]].
====Creation====
The following code demonstrates the creation and population of a dictionary (see [[#C#|the C# example on this page]] for additional information):
<syntaxhighlight lang=VBNet>
Dim dic As New System.Collections.Generic.Dictionary(Of String, String)
dic.Add("Sally Smart", "555-9999")
dic("John Doe") = "555-1212"
dic.Item("J. Random Hacker") = "553-1337"
</syntaxhighlight>
An
<syntaxhighlight lang=VBNet>
Dim dic As New System.Collections.Dictionary(Of String, String) From {
{"Sally Smart", "555-9999"},
Line 1,827 ⟶ 1,966:
{"J. Random Hacker", "553-1337"}
}
</syntaxhighlight>
====Access by key====
Example demonstrating access (see [[#C# access|C# access]]):
<syntaxhighlight lang=VBNet>
Dim sallyNumber = dic("Sally Smart")
' or
Dim sallyNumber = dic.Item("Sally Smart")
</syntaxhighlight>
<
Dim result As String = Nothing
Dim sallyNumber = If(dic.TryGetValue("Sally Smart", result), result, "n/a")
</syntaxhighlight>
====Enumeration====
Example demonstrating enumeration (see [[#C# enumeration]]):
<syntaxhighlight lang=VBNet>
' loop through the collection and display each entry.
For Each kvp As KeyValuePair(Of String, String) In dic
Console.WriteLine("Phone number for {0} is {1}", kvp.Key, kvp.Value)
Next
</syntaxhighlight>
===
Unlike many other [[command line interpreter]]s, [[Windows PowerShell]] has built-in, language-level support for defining associative arrays
<syntaxhighlight lang=PowerShell>
$phonebook = @{
'Sally Smart' = '555-9999';
Line 1,863 ⟶ 2,000:
'J. Random Hacker' = '553-1337'
}
</syntaxhighlight>
<
$myOtherObject = @{ foo = 42; bar = $false }
</syntaxhighlight>
Entries can be separated by either a semicolon or a newline
<
$myOtherObject = @{ foo = 42
bar = $false ;
zaz = 3
}
</syntaxhighlight>
Keys and values can be any [[.NET Framework|.NET]] object type
<
$now = [DateTime]::Now
$tomorrow = $now.AddDays(1)
Line 1,889 ⟶ 2,026:
(Get-Process calc) = $tomorrow
}
</syntaxhighlight>
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' }
</syntaxhighlight>
New entries can also be added by using the array index operator, the property operator, or the <code>Add()</code> method of the underlying .NET object:
<
$phonebook = @{}
$phonebook['Sally Smart'] = '555-9999'
$phonebook.'John Doe' = '555-1212'
$phonebook.Add('J. Random Hacker', '553-1337')
</syntaxhighlight>
To dereference assigned objects, the array index operator, the property operator, or the parameterized property <code>Item()</code> of the .NET object can be used:
<
$phonebook['Sally Smart']
$phonebook.'John Doe'
$phonebook.Item('J. Random Hacker')
</syntaxhighlight>
You can loop through an associative array as follows:
<
$phonebook.Keys | foreach { "Number for {0}: {1}" -f $_,$phonebook.$_ }
</syntaxhighlight>
An entry can be removed using the <code>Remove()</code> method of the underlying .NET object:
<
$phonebook.Remove('Sally Smart')
</syntaxhighlight>
Hash tables can be added
<
$hash1 = @{ a=1; b=2 }
$hash2 = @{ c=3; d=4 }
$hash3 = $hash1 + $hash2
</syntaxhighlight>
==Data serialization formats support==
Line 1,941 ⟶ 2,078:
Many data serialization formats also support associative arrays (see [[Comparison of data serialization formats#Syntax comparison of human-readable formats|this table]])
===
In [[JSON]], associative arrays are also referred to as objects. Keys can only be strings.
<syntaxhighlight lang=JavaScript>
{
"Sally Smart": "555-9999",
Line 1,949 ⟶ 2,087:
"J. Random Hacker": "555-1337"
}
</syntaxhighlight>
=== TOML ===
[[TOML]] is designed to map directly to a hash map. TOML refers to associative arrays as tables. Tables within TOML can be expressed in either an "unfolded" or an inline approach. Keys can only be strings.<syntaxhighlight lang="toml">[phonebook]
"Sally Smart" = "555-9999"
"John Doe" = "555-1212"
"J. Random Hacker" = "555-1337"</syntaxhighlight><syntaxhighlight lang="toml">
phonebook = { "Sally Smart" = "555-9999", "John Doe" = "555-1212", "J. Random Hacker" = "555-1337" }
</syntaxhighlight>
===YAML===
[[YAML]] associative arrays are also called map elements or key-value pairs. YAML places no restrictions on the types of keys; in particular, they are not restricted to being scalar or string values.
<
Sally Smart: 555-9999
John Doe: 555-1212
J. Random Hacker: 555-1337
</syntaxhighlight>
== References ==
Line 1,966 ⟶ 2,112:
[[Category:Associative arrays|Programming language comparison]]
[[Category:Programming language comparisons|*Mapping]]
[[Category:Articles with example Julia code]]
| |||