Comparison Of Programming Languages (associative Arrays)

This comparison of programming languages (associative arrays) compares the features of associative array data structures or array-lookup processing for over 40 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"

The following code loops through an associated array and prints its contents:

for (name in phonebook)

The user can search for elements in an associative array, and delete elements from the array.

The following shows how multi-dimensional associative arrays can be simulated in standard AWK using concatenation and the built-in string-separator variable SUBSEP:

#
END

C

There is no standard implementation of associative arrays in C, but a 3rd-party library, C Hash Table, with BSD license, is available.

Another 3rd-party library, uthash, also creates associative arrays from C structures. A structure represents a value, and one of the structure fields serves 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#

C# uses the collection classes provided by the .NET Framework. The most commonly used associative array type is System.Collections.Generic.Dictionary, which is implemented as a mutable hash table. The relatively new System.Collections.Immutable package, available in .NET Framework versions 4.5 and above, and in all versions of .NET Core, also includes the System.Collections.Immutable.Dictionary type, which is implemented using an AVL tree. The methods that would normally mutate the object in-place instead return a new object that represents the state of the original object after mutation.

Creation

The following demonstrates three means of populating a mutable dictionary:
* the Add method, which adds a key and value and throws an exception if the key already exists in the dictionary;
* assigning to the indexer, which overwrites any existing value, if present; and
* assigning to the backing property of the indexer, for which the indexer is syntactic sugar (not applicable to C#, see F# or VB.NET examples).

var dictionary = new Dictionary();
dictionary.Add("Sally Smart", "555-9999");
dictionary John Doe"= "555-1212";
// Not allowed in C#.
// dictionary.Item("J. Random Hacker") = "553-1337";
dictionary J. Random Hacker"= "553-1337";

The dictionary can also be initialized during construction using a "collection initializer", which compiles to repeated calls to Add.

var dictionary = new Dictionary ;

Access by key

Values are primarily retrieved using the indexer (which throws an exception if the key does not exist) and the TryGetValue method, which has an output parameter for the sought value and a Boolean return-value indicating whether the key was found.

var sallyNumber = dictionary Sally Smart"


var sallyNumber = (dictionary.TryGetValue("Sally Smart", out var result) ? result : "n/a";

In this example, the sallyNumber value will now contain the string "555-9999".

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 KeyValuePair type, although there is no guarantee of order. For a sorted dictionary, the programmer could choose to use a SortedDictionary or use the .Sort LINQ extension method when enumerating.

The following demonstrates enumeration using a foreach loop:

// loop through the collection and display each entry.
foreach (KeyValuePair kvp in dictionary)

C++

C++ has a form of associative array called std::map (see Standard Template Library#Containers). One could create a phone-book map with the following code in C++:

#include

int main()

Or less efficiently, as this creates temporary std::string values:

#include

int main()

With the extension of initialization lists in C++11, entries can be added during a map's construction as shown below:

#include

int main()

You can iterate through the list with the following code (C++03):

std::map::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 C++11:

for(const auto& curr : phone_book)
std::cout << curr.first << " = " << curr.second << std::endl;

Using the structured binding available in C++17:

for (const auto& ame, number: phone_book)

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, which has the algorithmic characteristics of a hash table. This is a common vendor extension to the Standard Template Library (STL) as well, usually called hash_map, available from such implementations as SGI and STLPort.

Cobra

Initializing an empty dictionary and adding items in Cobra:

Alternatively, a dictionary can be initialized with all items during construction:

The dictionary can be enumerated by a for-loop, but there is no guaranteed order:

ColdFusion Markup Language

A structure in ColdFusion Markup Language (CFML) is equivalent to an associative array:

dynamicKeyName = "John Doe";
phoneBook = ;
writeOutput(phoneBook.UnknownComic); // ???
writeDump(phoneBook); // entire struct

D

D offers direct support for associative arrays in the core language; such arrays are implemented as a chaining hash table with binary trees. The equivalent example would be:

int main()

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.

Looping through all properties and associated values, and printing them, can be coded as follows:

foreach (key, value; phone_book)

A property can be removed as follows:

phone_book.remove("Sally Smart");

Delphi

Delphi supports several standard containers, including TDictionary:

uses
SysUtils,
Generics.Collections;

var
PhoneBook: TDictionary;
Entry: TPair;

begin
PhoneBook := TDictionary.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', ntry.Key, Entry.Value);
end.

Pre-2009 Delphi versions do not support associative arrays directly. Such arrays can be simulated using the TStrings class:

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 + ': ' + DataField.ValueFromIndex ;
end;

DataField.Free;
end;

Erlang

Erlang offers many ways to represent mappings; three of the most common in the standard library are keylists, dictionaries, and maps.

Keylists

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 =
,

Accessing an element of the keylist can be done with the lists:keyfind/3 function:

= lists:keyfind("Sally Smith", 1, PhoneBook),
io:format("Phone number: ~s~n", hone.

Dictionaries

Dictionaries are implemented in the dict module 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(
,
.

The dictionary can be accessed using the dict:find/2 function:

= dict:find("Sally Smith", PhoneBook),
io:format("Phone: ~s~n", hone.

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.

Maps

Maps were introduced in OTP 17.0, and combine the strengths of keylists and dictionaries. A map is defined using the syntax #:

PhoneBook = #.

Basic functions to interact with maps are available from the maps module. For example, the maps:find/2 function returns the value associated with a key:

= maps:find("Sally Smith", PhoneBook),
io:format("Phone: ~s~n", hone.

Unlike dictionaries, maps can be pattern matched upon:

# = PhoneBook,
io:format("Phone: ~s~n", hone.

Erlang also provides syntax sugar for functional updates—creating a new map based on an existing one, but with modified values or additional keys:

PhoneBook2 = PhoneBook#

F#

Map<'Key,'Value>

At runtime, F# provides the Collections.Map<'Key,'Value> type, which is an immutable AVL tree.

=Creation

=
The following example calls the Map 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).

let numbers =
"Sally Smart", "555-9999";
"John Doe", "555-1212";
"J. Random Hacker", "555-1337"
, > Map

=Access by key

=
Values can be looked up via one of the Map members, such as its indexer or Item property (which throw an exception if the key does not exist) or the TryFind function, which 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 from the result, or a default value can be set.

let sallyNumber = numbers. Sally Smart"// or
let sallyNumber = numbers.Item("Sally Smart")


let sallyNumber =
match numbers.TryFind("Sally Smart") with
, Some(number) -> number
, None -> "n/a"

In both examples above, the sallyNumber value would contain the string "555-9999".

Dictionary<'TKey,'TValue>

Because F# is a .NET language, it also has access to features of the .NET Framework, including the 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 dict 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 IDictionary<'TKey,'TValue>.

let numbers =
"Sally Smart", "555-9999";
"John Doe", "555-1212";
"J. Random Hacker", "555-1337"
, > dict

When a mutable dictionary is needed, the constructor of can be called directly. See the C# example on this page for additional information.

let numbers = System.Collections.Generic.Dictionary()
numbers.Add("Sally Smart", "555-9999")
numbers. John Doe"<- "555-1212"
numbers.Item("J. Random Hacker") <- "555-1337"

=Access by key

=
IDictionary instances have an indexer that is used in the same way as Map, although the equivalent to TryFind is TryGetValue, which has an output parameter for the sought value and a Boolean return value indicating whether the key was found.

let sallyNumber =
let mutable result = ""
if numbers.TryGetValue("Sally Smart", &result) then result else "n/a"

F# also allows the function to be called as if it had no output parameter and instead returned a tuple containing its regular return value and the value assigned to the output parameter:

let sallyNumber =
match numbers.TryGetValue("Sally Smart") with
, true, number -> number
, _ -> "n/a"

Enumeration

A dictionary or map can be enumerated using Seq.map.

// loop through the collection and display each entry.
numbers , > Seq.map (fun kvp -> printfn "Phone number for %O is %O" kvp.Key kvp.Value)

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.

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: map eytypealuetype

Adding elements one at a time:

phone_book := make(maptringstring) // 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 := maptringstring

Iterating through a map:

// over both keys and values
for key, value := range phone_book

// over just keys
for key := range phone_book

Haskell

The Haskell programming language provides only 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.

The Glasgow Haskell Compiler (GHC), the most commonly used implementation of Haskell, provides two more types of associative containers. Other implementations may 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", which 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 that maps strings to strings might be specified as follows:

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

The method is used to access a key; for example, the value of the expression phoneBook.get("Sally Smart") is "555-9999". This code uses a hash map to store the associative array, by calling the constructor of the class. However, since the code only uses methods common to the interface , a self-balancing binary tree could be used by calling the constructor of the class (which implements the subinterface ), without changing the definition of the phoneBook variable, or the rest of the code, or using other underlying data structures that implement the Map interface.

The hash function in Java, used by HashMap and HashSet, is provided by the method. Since every class in Java inherits from , every object has a hash function. A class can override the default implementation of hashCode() to provide a custom hash function more in accordance with the properties of the object.

The Object class also contains the method, which tests an 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 vice versa, so that hashCode() is based on the same properties (or a subset of the properties) as equals().

A further contract that a hashed data structure 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, require that an ordering be defined on the data type. Either the data type must already have defined its own ordering, by implementing the interface; or a custom 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.

Map and WeakMap

Modern JavaScript handles associative arrays, using the Map and WeakMap 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:

const phoneBook = new Map( ["Sally Smart", "555-9999"
["John Doe", "555-1212"">quot;Sally_Smart",_"555-9999".html" ;"title=" ["Sally Smart", "555-9999""> ["Sally Smart", "555-9999"
["John Doe", "555-1212"
["J. Random Hacker", "553-1337"],
]);

Alternatively, you can initialize an empty map and then add items:

const phoneBook = new Map();
phoneBook.set("Sally Smart", "555-9999");
phoneBook.set("John Doe", "555-1212");
phoneBook.set("J. Random Hacker", "553-1337");

=Access by key

=
Accessing an element of the map can be done with the get method:

const sallyNumber = phoneBook.get("Sally Smart");

In this example, the value sallyNumber 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:

// loop through the collection and display each entry.
for (const ame, numberof phoneBook)

A key can be removed as follows:

phoneBook.delete("Sally Smart");

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 . For example:

const myObject = ;

To prevent the lookup from using the prototype's properties, you can use the Object.setPrototypeOf function:

Object.setPrototypeOf(myObject, null);

As of ECMAScript 5 (ES5), the prototype can also be bypassed by using Object.create(null):

const myObject = Object.create(null);

Object.assign(myObject, );

If the property name is a valid identifier, the quotes can be omitted, e.g.:

const myOtherObject = ;

Lookup is written using property-access notation, either square brackets, which always work, 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 (a for-in loop):

for (const property in myObject)

Or (a for-of loop):

for (const roperty, valueof Object.entries(myObject))

A property can be removed as follows:

delete myObject Sally Smart"

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

myObject // key is "1"; note that myObject

myObject 1"myObject "a", "b" // key is "a,b"
myObject[] // key is "hello world"

In modern JavaScript it's considered bad form to use the Array type as an associative array. Consensus is that the Object type and Map/WeakMap 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.

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

Julia

In Julia, the following operations manage associative arrays.

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

In KornShell 93, and compliant shells (ksh93, bash4...), the following operations can be used with associative arrays.

Definition:

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"">J._Random_Hacker.html" ;"title="J. Random Hacker">J. Random Hacker""555-1337");

Dereference:

$;

Lisp

Lisp programming language">Lisp