Associative array/Creation: Difference between revisions
→{{header|langur}}
Langurmonkey (talk | contribs) |
|||
(43 intermediate revisions by 20 users not shown) | |||
Line 1:
{{task|Basic language learning}}
;Task:
The goal is to create an [[associative array]] (also known as a dictionary, map, or hash).
Line 14:
=={{header|11l}}==
<
V value2 = dict[‘key2’]</
=={{header|8th}}==
8th has 'maps' as built-in data types, and can use JSON to describe them:
<syntaxhighlight lang="forth">
{ "one" : 1, "two" : "bad" }
</syntaxhighlight>
Alternatively, they can be created in code:
<syntaxhighlight lang="forth">
m:new "one" 1 m:! "two" "bad" m:!
</syntaxhighlight>
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits <br> or android 64 bits with application Termux }}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B or android 64 bits */
/* program hashmap64.s */
Line 425:
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ActionScript}}==
Because ActionScript does not have associative arrays in the normal sense, Object objects are used instead and keys are simply properties on those objects.
<
trace(map['key1']); // outputs "value1"
Line 437:
// More keys and values can then be added
map['key3'] = "value3";
trace(map['key3']); // outputs "value3"</
''Note: The Object only supports String keys. To use an object as a key, try the flash.utils.Dictionary class.''
=={{header|Ada}}==
{{works with|GNAT|GPL 2007}}
<
with Ada.Strings.Unbounded; use Ada.Strings.Unbounded;
with Ada.Text_IO;
Line 474:
Value := Color_Map.Element(To_Unbounded_String("Yellow"));
Ada.Text_IO.Put_Line("Yellow:" & Integer'Image(Value));
end Associative_Array;</
=={{header|Aikido}}==
Aikido provides a native <em>map</em> for associative arrays. You can create them using a map literal and you can insert and remove items on the fly.
<
var names = {} // empty map
names["foo"] = "bar"
Line 498:
</syntaxhighlight>
=={{header|Aime}}==
Aime records are heterogenous associative arrays. No creation procedure is required, declaration is fine.
<syntaxhighlight lang
<
r_put(r, "C", 2.5); # a real value
r_put(r, "B", "associative"); # a string value</
=={{header|ALGOL 68}}==
Line 514:
{{works with|ALGOL 68G|Any - tested with release [http://sourceforge.net/projects/algol68/files/algol68g/algol68g-1.18.0/algol68g-1.18.0-9h.tiny.el5.centos.fc11.i386.rpm/download 1.18.0-9h.tiny]}}
{{wont work with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release [http://sourceforge.net/projects/algol68/files/algol68toc/algol68toc-1.8.8d/algol68toc-1.8-8d.fc9.i386.rpm/download 1.8-8d] - due to extensive use of FORMATted transput}}
<
MODE COLOR = BITS;
Line 583:
printf(($g$,"values: ", comma sep, value OF color map items, $l$))
)</
{{out}}
<pre>
Line 600:
Creating a new empty map of String to String:
<
Map<String, String> strMap = new Map<String, String>();
strMap.put('a', 'aval');
Line 608:
System.assertEquals( 'bval', strMap.get('b') );
// String keys are case-sensitive
System.assert( !strMap.containsKey('A') );</
Creating a new map of String to String with values initialized:
<
'a' => 'aval',
'b' => 'bval'
Line 617:
System.assert( strMap.containsKey('a') );
System.assertEquals( 'bval', strMap.get('b') );</
=={{header|APL}}==
{{works with|Dyalog APL}}
<
X←⎕NS ⍬
Line 642:
sales.revenue
4109.6
</syntaxhighlight>
{{works with|GNU APL}}
<
⍝ Assign some names
X.this←'that'
Line 672:
sales.revenue
4109.6
</syntaxhighlight>
=={{header|App Inventor}}==
Line 681:
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi <br> or android 32 bits with application Termux}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI or android 32 bits */
/* program hashmap.s */
Line 1,054:
.include "../affichage.inc"
</syntaxhighlight>
=={{header|Arturo}}==
<
d: #[
name: "john"
Line 1,064:
]
print d</
{{out}}
<pre>[name:john surname:doe age:34]</pre>
=={{header|ATS}}==
ATS, like many languages, does not have high level stuff such as maps built into the language itself, so library support or one's own code is what one needs.
In the following, ''persistence'' means that past values of the map are retained, if they continue to have references to them. This property sometimes is called ''immutability'', but I feel that term implies too much.
=== Persistent association lists ===
The following implementation includes set, get, and delete, and also "generators", which are like iterators except they are closures rather than regular objects.
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
#define ATS_DYNLOADFLAG 0
#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(* Interface *)
(* You can put the interface in a .sats file. You will have to remove
the word "extern". *)
typedef alist_t (key_t : t@ype+,
data_t : t@ype+,
size : int) =
list (@(key_t, data_t), size)
typedef alist_t (key_t : t@ype+,
data_t : t@ype+) =
[size : int]
alist_t (key_t, data_t, size)
extern prfun
lemma_alist_t_param :
{size : int} {key_t : t@ype} {data_t : t@ype}
alist_t (key_t, data_t, size) -<prf> [0 <= size] void
extern fun {key_t : t@ype} (* Implement key equality with this. *)
alist_t$key_eq : (key_t, key_t) -<> bool
(* alist_t_nil: create an empty association list. *)
extern fun
alist_t_nil :
{key_t : t@ype} {data_t : t@ype}
() -<> alist_t (key_t, data_t, 0)
(* alist_t_set: add an association, deleting old associations with an
equal key. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
alist_t_set {size : int}
(alst : alist_t (key_t, data_t, size),
key : key_t,
data : data_t) :<>
[sz : int | 1 <= sz]
alist_t (key_t, data_t, sz)
(* alist_t_get: find an association and return its data, if
present. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
alist_t_get {size : int}
(alst : alist_t (key_t, data_t, size),
key : key_t) :<>
Option data_t
(* alist_t_delete: delete all associations with key. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
alist_t_delete {size : int}
(alst : alist_t (key_t, data_t, size),
key : key_t ) :<>
[sz : int | 0 <= sz]
alist_t (key_t, data_t, sz)
(* alist_t_make_pairs_generator: make a closure that returns
the association pairs, one by one. This is a form of iterator.
Analogous generators can be made for the keys or data values
alone. *)
extern fun {key_t : t@ype}
{data_t : t@ype}
alist_t_make_pairs_generator
{size : int}
(alst : alist_t (key_t, data_t, size)) :<!wrt>
() -<cloref,!refwrt> Option @(key_t, data_t)
(*------------------------------------------------------------------*)
(* Implementation *)
#define NIL list_nil ()
#define :: list_cons
primplement
lemma_alist_t_param alst =
lemma_list_param alst
implement
alist_t_nil () =
NIL
implement {key_t} {data_t}
alist_t_set (alst, key, data) =
@(key, data) :: alist_t_delete (alst, key)
implement {key_t} {data_t}
alist_t_get (alst, key) =
let
fun
loop {n : nat}
.<n>. (* <-- proof of termination *)
(lst : alist_t (key_t, data_t, n)) :<>
Option data_t =
case+ lst of
| NIL => None ()
| head :: tail =>
if alist_t$key_eq (key, head.0) then
Some (head.1)
else
loop tail
prval _ = lemma_alist_t_param alst
in
loop alst
end
implement {key_t} {data_t}
alist_t_delete (alst, key) =
let
fun
delete {n : nat}
.<n>. (* <-- proof of termination *)
(lst : alist_t (key_t, data_t, n)) :<>
[m : nat] alist_t (key_t, data_t, m) =
(* This implementation is *not* tail recursive, but has the
minor advantage of preserving the order of entries without
doing a lot of work. *)
case+ lst of
| NIL => lst
| head :: tail =>
if alist_t$key_eq (key, head.0) then
delete tail
else
head :: delete tail
prval _ = lemma_alist_t_param alst
in
delete alst
end
implement {key_t} {data_t}
alist_t_make_pairs_generator alst =
let
typedef alist_t = [sz : int] alist_t (key_t, data_t, sz)
val alst_ref = ref alst
(* Cast the ref to a pointer so it can be enclosed in the
closure. *)
val alst_ptr = $UNSAFE.castvwtp0{ptr} alst_ref
in
lam () =>
let
val alst_ref = $UNSAFE.castvwtp0{ref alist_t} alst_ptr
in
case+ !alst_ref of
| NIL => None ()
| head :: tail =>
begin
!alst_ref := tail;
(* For a keys generator, change the following line to
"Some (head.0)"; for a data values generator, change
it to "Some (head.1)". *)
Some head
end
end
end
(*------------------------------------------------------------------*)
(* Demonstration program *)
implement
alist_t$key_eq<string> (s, t) =
s = t
typedef s2i_alist_t = alist_t (string, int)
fn
s2i_alist_t_set (map : s2i_alist_t,
key : string,
data : int) :<> s2i_alist_t =
alist_t_set<string><int> (map, key, data)
fn
s2i_alist_t_set_ref (map : &s2i_alist_t >> _,
key : string,
data : int) :<!wrt> void =
(* Update a reference to a persistent alist. *)
map := s2i_alist_t_set (map, key, data)
fn
s2i_alist_t_get (map : s2i_alist_t,
key : string) :<> Option int =
alist_t_get<string><int> (map, key)
extern fun {} (* {} = a template without template parameters *)
s2i_alist_t_get_dflt$dflt :<> () -> int
fn {} (* {} = a template without template parameters *)
s2i_alist_t_get_dflt (map : s2i_alist_t,
key : string) : int =
case+ s2i_alist_t_get (map, key) of
| Some x => x
| None () => s2i_alist_t_get_dflt$dflt<> ()
overload [] with s2i_alist_t_set_ref
overload [] with s2i_alist_t_get_dflt
implement
main0 () =
let
implement s2i_alist_t_get_dflt$dflt<> () = 0
var map = alist_t_nil ()
var gen : () -<cloref1> @(string, int)
var pair : Option @(string, int)
in
map["one"] := 1;
map["two"] := 2;
map["three"] := 3;
println! ("map[\"one\"] = ", map["one"]);
println! ("map[\"two\"] = ", map["two"]);
println! ("map[\"three\"] = ", map["three"]);
println! ("map[\"four\"] = ", map["four"]);
gen := alist_t_make_pairs_generator<string><int> map;
for (pair := gen (); option_is_some pair; pair := gen ())
println! (pair)
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O2 -DATS_MEMALLOC_GCBDW association_lists-postiats.dats -lgc && ./a.out
map["one"] = 1
map["two"] = 2
map["three"] = 3
map["four"] = 0
Some((three, 3))
Some((two, 2))
Some((one, 1))</pre>
=== Persistent hashmaps based on AVL trees ===
{{trans|Scheme}}
{{libheader|xxHash}}
The following implementation includes set and get, and also "generators", which are like iterators except they are closures rather than regular objects. A delete function could easily be added.
To run this demonstration you need the [http://www.xxhash.net xxHash] C library. I have written an implementation of SpookyHash in ATS, but using a C library is fine, and requires less ATS code.
Because the hash table is an AVL tree, performance will tend to be logarithmic. This assumes a good hash function, of course. With a bad hash function, performance may be linear.
<syntaxhighlight lang="ats">(*------------------------------------------------------------------*)
#define ATS_DYNLOADFLAG 0
#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
(* String hashing using XXH3_64bits from the xxHash suite. *)
#define ATS_EXTERN_PREFIX "hashmaps_postiats_"
%{^ /* Embedded C code. */
#include <xxhash.h>
ATSinline() atstype_uint64
hashmaps_postiats_mem_hash (atstype_ptr data, atstype_size len)
{
return (atstype_uint64) XXH3_64bits (data, len);
}
%}
extern fn mem_hash : (ptr, size_t) -<> uint64 = "mac#%"
fn
string_hash (s : string) :<> uint64 =
let
val len = string_length s
in
mem_hash ($UNSAFE.cast{ptr} s, len)
end
(*------------------------------------------------------------------*)
(* A trimmed down version of the AVL trees from the AVL Tree task. *)
datatype bal_t =
| bal_minus1
| bal_zero
| bal_plus1
datatype avl_t (key_t : t@ype+,
data_t : t@ype+,
size : int) =
| avl_t_nil (key_t, data_t, 0)
| {size_L, size_R : nat}
avl_t_cons (key_t, data_t, size_L + size_R + 1) of
(key_t, data_t, bal_t,
avl_t (key_t, data_t, size_L),
avl_t (key_t, data_t, size_R))
typedef avl_t (key_t : t@ype+,
data_t : t@ype+) =
[size : int] avl_t (key_t, data_t, size)
extern fun {key_t : t@ype}
avl_t$compare (u : key_t, v : key_t) :<> int
#define NIL avl_t_nil ()
#define CONS avl_t_cons
#define LNIL list_nil ()
#define :: list_cons
#define F false
#define T true
typedef fixbal_t = bool
prfn
lemma_avl_t_param {key_t : t@ype} {data_t : t@ype} {size : int}
(avl : avl_t (key_t, data_t, size)) :<prf>
[0 <= size] void =
case+ avl of NIL => () | CONS _ => ()
fn {}
minus_neg_bal (bal : bal_t) :<> bal_t =
case+ bal of
| bal_minus1 () => bal_plus1
| _ => bal_zero ()
fn {}
minus_pos_bal (bal : bal_t) :<> bal_t =
case+ bal of
| bal_plus1 () => bal_minus1
| _ => bal_zero ()
fn
avl_t_is_empty {key_t : t@ype} {data_t : t@ype} {size : int}
(avl : avl_t (key_t, data_t, size)) :<>
[b : bool | b == (size == 0)] bool b =
case+ avl of
| NIL => T
| CONS _ => F
fn
avl_t_isnot_empty {key_t : t@ype} {data_t : t@ype} {size : int}
(avl : avl_t (key_t, data_t, size)) :<>
[b : bool | b == (size <> 0)] bool b =
~avl_t_is_empty avl
fn {key_t : t@ype} {data_t : t@ype}
avl_t_search_ref {size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t,
data : &data_t? >> opt (data_t, found),
found : &bool? >> bool found) :<!wrt>
#[found : bool] void =
let
fun
search (p : avl_t (key_t, data_t),
data : &data_t? >> opt (data_t, found),
found : &bool? >> bool found) :<!wrt,!ntm>
#[found : bool] void =
case+ p of
| NIL =>
{
prval _ = opt_none {data_t} data
val _ = found := F
}
| CONS (k, d, _, left, right) =>
begin
case+ avl_t$compare<key_t> (key, k) of
| cmp when cmp < 0 => search (left, data, found)
| cmp when cmp > 0 => search (right, data, found)
| _ =>
{
val _ = data := d
prval _ = opt_some {data_t} data
val _ = found := T
}
end
in
$effmask_ntm search (avl, data, found)
end
fn {key_t : t@ype} {data_t : t@ype}
avl_t_search_opt {size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t) :<>
Option (data_t) =
let
var data : data_t?
var found : bool?
val _ = $effmask_wrt avl_t_search_ref (avl, key, data, found)
in
if found then
let
prval _ = opt_unsome data
in
Some {data_t} data
end
else
let
prval _ = opt_unnone data
in
None {data_t} ()
end
end
fn {key_t : t@ype} {data_t : t@ype}
avl_t_insert_or_replace {size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t,
data : data_t) :<>
[sz : pos] (avl_t (key_t, data_t, sz), bool) =
let
fun
search {size : nat}
(p : avl_t (key_t, data_t, size),
fixbal : fixbal_t,
found : bool) :<!ntm>
[sz : pos]
(avl_t (key_t, data_t, sz), fixbal_t, bool) =
case+ p of
| NIL => (CONS (key, data, bal_zero, NIL, NIL), T, F)
| CONS (k, d, bal, left, right) =>
case+ avl_t$compare<key_t> (key, k) of
| cmp when cmp < 0 =>
let
val (p1, fixbal, found) = search (left, fixbal, found)
in
case+ (fixbal, bal) of
| (F, _) => (CONS (k, d, bal, p1, right), F, found)
| (T, bal_plus1 ()) =>
(CONS (k, d, bal_zero (), p1, right), F, found)
| (T, bal_zero ()) =>
(CONS (k, d, bal_minus1 (), p1, right), fixbal, found)
| (T, bal_minus1 ()) =>
let
val+ CONS (k1, d1, bal1, left1, right1) = p1
in
case+ bal1 of
| bal_minus1 () =>
let
val q = CONS (k, d, bal_zero (), right1, right)
val q1 = CONS (k1, d1, bal_zero (), left1, q)
in
(q1, F, found)
end
| _ =>
let
val p2 = right1
val- CONS (k2, d2, bal2, left2, right2) = p2
val q = CONS (k, d, minus_neg_bal bal2,
right2, right)
val q1 = CONS (k1, d1, minus_pos_bal bal2,
left1, left2)
val q2 = CONS (k2, d2, bal_zero (), q1, q)
in
(q2, F, found)
end
end
end
| cmp when cmp > 0 =>
let
val (p1, fixbal, found) = search (right, fixbal, found)
in
case+ (fixbal, bal) of
| (F, _) => (CONS (k, d, bal, left, p1), F, found)
| (T, bal_minus1 ()) =>
(CONS (k, d, bal_zero (), left, p1), F, found)
| (T, bal_zero ()) =>
(CONS (k, d, bal_plus1 (), left, p1), fixbal, found)
| (T, bal_plus1 ()) =>
let
val+ CONS (k1, d1, bal1, left1, right1) = p1
in
case+ bal1 of
| bal_plus1 () =>
let
val q = CONS (k, d, bal_zero (), left, left1)
val q1 = CONS (k1, d1, bal_zero (), q, right1)
in
(q1, F, found)
end
| _ =>
let
val p2 = left1
val- CONS (k2, d2, bal2, left2, right2) = p2
val q = CONS (k, d, minus_pos_bal bal2,
left, left2)
val q1 = CONS (k1, d1, minus_neg_bal bal2,
right2, right1)
val q2 = CONS (k2, d2, bal_zero (), q, q1)
in
(q2, F, found)
end
end
end
| _ => (CONS (key, data, bal, left, right), F, T)
in
if avl_t_is_empty avl then
(CONS (key, data, bal_zero, NIL, NIL), F)
else
let
prval _ = lemma_avl_t_param avl
val (avl, _, found) = $effmask_ntm search (avl, F, F)
in
(avl, found)
end
end
fn {key_t : t@ype} {data_t : t@ype}
avl_t_insert {size : int}
(avl : avl_t (key_t, data_t, size),
key : key_t,
data : data_t) :<>
[sz : pos] avl_t (key_t, data_t, sz) =
(avl_t_insert_or_replace<key_t><data_t> (avl, key, data)).0
fun {key_t : t@ype} {data_t : t@ype}
push_all_the_way_left (stack : List (avl_t (key_t, data_t)),
p : avl_t (key_t, data_t)) :
List0 (avl_t (key_t, data_t)) =
let
prval _ = lemma_list_param stack
in
case+ p of
| NIL => stack
| CONS (_, _, _, left, _) =>
push_all_the_way_left (p :: stack, left)
end
fun {key_t : t@ype} {data_t : t@ype}
update_generator_stack (stack : List (avl_t (key_t, data_t)),
right : avl_t (key_t, data_t)) :
List0 (avl_t (key_t, data_t)) =
let
prval _ = lemma_list_param stack
in
if avl_t_is_empty right then
stack
else
push_all_the_way_left<key_t><data_t> (stack, right)
end
fn {key_t : t@ype} {data_t : t@ype}
avl_t_make_data_generator {size : int}
(avl : avl_t (key_t, data_t, size)) :
() -<cloref1> Option data_t =
let
typedef avl_t = avl_t (key_t, data_t)
val stack = push_all_the_way_left<key_t><data_t> (LNIL, avl)
val stack_ref = ref stack
(* Cast stack_ref to its (otherwise untyped) pointer, so it can be
enclosed within ‘generate’. *)
val p_stack_ref = $UNSAFE.castvwtp0{ptr} stack_ref
fun
generate () :<cloref1> Option data_t =
let
(* Restore the type information for stack_ref. *)
val stack_ref =
$UNSAFE.castvwtp0{ref (List avl_t)} p_stack_ref
var stack : List0 avl_t = !stack_ref
var retval : Option data_t
in
begin
case+ stack of
| LNIL => retval := None ()
| p :: tail =>
let
val- CONS (_, d, _, left, right) = p
in
retval := Some d;
stack :=
update_generator_stack<key_t><data_t> (tail, right)
end
end;
!stack_ref := stack;
retval
end
in
generate
end
(*------------------------------------------------------------------*)
(* Hashmaps implemented with AVL trees and association lists. *)
(* The interface - - - - - - - - - - - - - - - - - - - - - - - - - *)
typedef hashmap_t (key_t : t@ype+,
data_t : t@ype+) =
avl_t (uint64, List1 @(key_t, data_t))
(* For simplicity, let us support only 64-bit hashes. *)
extern fun {key_t : t@ype} (* Implement a hash function with this. *)
hashmap_t$hashfunc : key_t -<> uint64
extern fun {key_t : t@ype} (* Implement key equality with this. *)
hashmap_t$key_eq : (key_t, key_t) -<> bool
extern fun
hashmap_t_nil :
{key_t : t@ype} {data_t : t@ype}
() -<> hashmap_t (key_t, data_t)
extern fun {key_t : t@ype}
{data_t : t@ype}
hashmap_t_set (map : hashmap_t (key_t, data_t),
key : key_t,
data : data_t) :<>
hashmap_t (key_t, data_t)
extern fun {key_t : t@ype}
{data_t : t@ype}
hashmap_t_get (map : hashmap_t (key_t, data_t),
key : key_t) :<>
Option data_t
(*
Notes:
* Generators for hashmap_t produce their output in unspecified
order.
* Generators for keys and data values can be made by analogy to
the following generator for pairs, or can be written in terms
of the generator for pairs. (The former approach seems better;
it might copy less data.)
*)
extern fun {key_t : t@ype}
{data_t : t@ype}
hashmap_t_make_pairs_generator (map : hashmap_t (key_t, data_t)) :
() -<cloref1> Option @(key_t, data_t)
(* The implementation - - - - - - - - - - - - - - - - - - - - - - - *)
implement
avl_t$compare<uint64> (u, v) =
if u < v then
~1
else if v < u then
1
else
0
implement
hashmap_t_nil () =
avl_t_nil ()
fun {key_t : t@ype}
{data_t : t@ype}
remove_association {n : nat} .<n>.
(lst : list (@(key_t, data_t), n),
key : key_t) :<>
List0 @(key_t, data_t) =
(* This implementation uses linear stack space, and so presumes the
list is not extremely long. It preserves the order of the list,
although doing so is not necessary for persistence. (You might
wish to think about that, taking into account that the
order of traversal through a hashmap usually is considered
"unspecified".) *)
case+ lst of
| list_nil () => lst
| list_cons (head, tail) =>
if hashmap_t$key_eq<key_t> (key, head.0) then
tail (* Assume there is only one match. *)
else
list_cons (head, remove_association (tail, key))
fun {key_t : t@ype}
{data_t : t@ype}
find_association {n : nat} .<n>.
(lst : list (@(key_t, data_t), n),
key : key_t) :<>
List0 @(key_t, data_t) =
(* This implementation is tail recursive. It will not build up the
stack. *)
case+ lst of
| list_nil () => lst
| list_cons (head, tail) =>
if hashmap_t$key_eq<key_t> (key, head.0) then
lst
else
find_association (tail, key)
implement {key_t} {data_t}
hashmap_t_set (map, key, data) =
let
typedef lst_t = List1 @(key_t, data_t) (* Association list. *)
val hash = hashmap_t$hashfunc<key_t> key
val lst_opt = avl_t_search_opt<uint64><lst_t> (map, hash)
val lst =
begin
case+ lst_opt of
| Some lst =>
(* There is already an association list for this hash value.
Remove any association already in it. *)
remove_association<key_t><data_t> (lst, key)
| None () =>
(* Start a new association list. *)
list_nil ()
end : List0 @(key_t, data_t)
val lst = list_cons (@(key, data), lst)
in
avl_t_insert<uint64><lst_t> (map, hash, lst)
end
implement {key_t} {data_t}
hashmap_t_get (map, key) =
let
typedef lst_t = List1 @(key_t, data_t) (* Association list. *)
val hash = hashmap_t$hashfunc<key_t> key
val lst_opt = avl_t_search_opt<uint64><lst_t> (map, hash)
in
case+ lst_opt of
| None () => None{data_t} ()
| Some lst =>
begin
case+ find_association<key_t><data_t> (lst, key) of
| list_nil () => None{data_t} ()
| list_cons (@(_, data), _) => Some{data_t} data
end
end
implement {key_t} {data_t}
hashmap_t_make_pairs_generator (map) =
let
typedef pair_t = @(key_t, data_t)
typedef lst_t = List1 pair_t
typedef lst_t_0 = List0 pair_t
val avl_gen = avl_t_make_data_generator<uint64><lst_t> (map)
val current_alist_ref : ref lst_t_0 = ref (list_nil ())
val current_alist_ptr =
$UNSAFE.castvwtp0{ptr} current_alist_ref
in
lam () =>
let
val current_alist_ref =
$UNSAFE.castvwtp0{ref lst_t_0} current_alist_ptr
in
case+ !current_alist_ref of
| list_nil () =>
begin
case+ avl_gen () of
| None () => None ()
| Some lst =>
begin
case+ lst of
| list_cons (head, tail) =>
begin
!current_alist_ref := tail;
Some head
end
end
end
| list_cons (head, tail) =>
begin
!current_alist_ref := tail;
Some head
end
end
end
(*------------------------------------------------------------------*)
implement
hashmap_t$hashfunc<string> (s) =
string_hash s
implement
hashmap_t$key_eq<string> (s, t) =
s = t
typedef s2i_hashmap_t = hashmap_t (string, int)
fn
s2i_hashmap_t_set (map : s2i_hashmap_t,
key : string,
data : int) :<> s2i_hashmap_t =
hashmap_t_set<string><int> (map, key, data)
fn
s2i_hashmap_t_set_ref (map : &s2i_hashmap_t >> _,
key : string,
data : int) :<!wrt> void =
(* Update a reference to a persistent hashmap. *)
map := s2i_hashmap_t_set (map, key, data)
fn
s2i_hashmap_t_get (map : s2i_hashmap_t,
key : string) :<> Option int =
hashmap_t_get<string><int> (map, key)
extern fun {} (* {} = a template without template parameters *)
s2i_hashmap_t_get_dflt$dflt :<> () -> int
fn {} (* {} = a template without template parameters *)
s2i_hashmap_t_get_dflt (map : s2i_hashmap_t,
key : string) : int =
case+ s2i_hashmap_t_get (map, key) of
| Some x => x
| None () => s2i_hashmap_t_get_dflt$dflt<> ()
overload [] with s2i_hashmap_t_set_ref
overload [] with s2i_hashmap_t_get_dflt
implement
main0 () =
let
implement s2i_hashmap_t_get_dflt$dflt<> () = 0
var map = hashmap_t_nil ()
var gen : () -<cloref1> @(string, int)
var pair : Option @(string, int)
in
map["one"] := 1;
map["two"] := 2;
map["three"] := 3;
println! ("map[\"one\"] = ", map["one"]);
println! ("map[\"two\"] = ", map["two"]);
println! ("map[\"three\"] = ", map["three"]);
println! ("map[\"four\"] = ", map["four"]);
gen := hashmap_t_make_pairs_generator<string><int> map;
for (pair := gen (); option_is_some pair; pair := gen ())
println! (pair)
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>$ patscc -O2 -DATS_MEMALLOC_GCBDW hashmaps-postiats.dats -lxxhash -lgc && ./a.out
map["one"] = 1
map["two"] = 2
map["three"] = 3
map["four"] = 0
Some((two, 2))
Some((one, 1))
Some((three, 3))</pre>
=={{header|AutoHotkey}}==
=== True arrays ===
[[AutoHotkey_L]] has [http://ahkscript.org/docs/Objects.htm Objects] which function as associative arrays.
<
MsgBox % associative_array.key1
. "`n" associative_array["Key with spaces and non-alphanumeric characters !*+"]</
=== Legacy versions ===
[[AutoHotkey_Basic]] does not have typical arrays.
However, variable names can be concatenated, simulating associative arrays.
<
arrayX2 = second
arrayX3 = foo
arrayX4 = bar
Loop, 4
Msgbox % arrayX%A_Index%</
=={{header|AutoIt}}==
See '''[https://msdn.microsoft.com/en-us/library/x4k5wbx4.aspx here]''' in the MSDN the reference for the Dictionary object that can be used in VBA. The following example shows how to create a dictionary, add/remove keys, change a key or a value, and check the existence of a key.
<
; All the required functions are below the examples.
Line 1,215 ⟶ 2,059:
;; End AA Functions.
</syntaxhighlight>
=={{header|AWK}}==
Arrays in AWK are indeed associative arrays.
<
a["red"] = 0xff0000
a["green"] = 0x00ff00
Line 1,234 ⟶ 2,078:
print ( "red" in a ) # print 0
print ( "blue" in a ) # print 1
}</
=={{header|Babel}}==
<
(("foo" 13)
("bar" 42)
("baz" 77)) ls2map !</
=={{header|
==={{header|BaCon}}===
<syntaxhighlight lang="qbasic">DECLARE associative ASSOC STRING
associative("abc") = "first three"
associative("xyz") = "last three"
PRINT associative("xyz")</
{{out}}
Line 1,258 ⟶ 2,103:
String keys, with ASSOC to a given data type. Sizing is dynamic.
==={{header|BASIC256}}===
<
dim values$[1]
dim keys$[1]
Line 1,364 ⟶ 2,209:
next n
return ""
end function</
{{out}}
<pre>a apple
Line 1,374 ⟶ 2,219:
e endive
c carrot</pre>
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic"> REM Store some values with their keys:
PROCputdict(mydict$, "FF0000", "red")
PROCputdict(mydict$, "00FF00", "green")
PROCputdict(mydict$, "0000FF", "blue")
REM Retrieve some values using their keys:
PRINT FNgetdict(mydict$, "green")
PRINT FNgetdict(mydict$, "red")
END
DEF PROCputdict(RETURN dict$, value$, key$)
IF dict$ = "" dict$ = CHR$(0)
dict$ += key$ + CHR$(1) + value$ + CHR$(0)
ENDPROC
DEF FNgetdict(dict$, key$)
LOCAL I%, J%
I% = INSTR(dict$, CHR$(0) + key$ + CHR$(1))
IF I% = 0 THEN = "" ELSE I% += LEN(key$) + 2
J% = INSTR(dict$, CHR$(0), I%)
= MID$(dict$, I%, J% - I%)</syntaxhighlight>
=={{header|Batch File}}==
This is cheating, I'm sure of it.
<
@echo off
setlocal ENABLEDELAYEDEXPANSION
Line 1,402 ⟶ 2,270:
echo %1 = %2
goto :eof
</syntaxhighlight>
{{out}}
Line 1,413 ⟶ 2,281:
"sicko&mumps" = 7
"sicko&bromodrosis" = 8</pre>
=={{header|Bracmat}}==
The hash is the only built-in Bracmat class. It is best used for e.g. a large dictionary, when manipulation of a very long list of key/value pairs with pattern matching would become too CPU-intensive. The same key can be stored with different values, as the example shows. If that is not desirable, the key (and its value) should be removed first.
<
& (myhash..insert)$(title."Some title")
& (myhash..insert)$(formula.a+b+x^7)
Line 1,448 ⟶ 2,293:
& (myhash..remove)$formula
& (myhash..insert)$(formula.x^2+y^2)
& out$(myhash..find)$formula;</
{{out}}
<pre>(fruit.melons bananas) (fruit.apples oranges kiwis)
Line 1,454 ⟶ 2,299:
=={{header|Brat}}==
<
h[:a] = 1 #Assign value
Line 1,461 ⟶ 2,306:
h2 = [a: 1, b: [1 2 3], 10 : "ten"] #Initialized hash
h2[:b][2] #Returns 3</
=={{header|C}}==
Line 1,468 ⟶ 2,313:
=={{header|C sharp|C#}}==
'''Platform:''' [[.NET]] 1.x
<
map["key1"] = "foo";</
'''Platform:''' [[.NET]] 2.0
<
map[ "key1" ] = "foo";</
{{works with|C sharp|C#|3.0+}}
<
=={{header|C++}}==
The C++ standard defines std::map as a means of creating an association between a key of one arbitrary type and a value of another arbitrary type. This requires the inclusion of the standard header '''map'''.
<syntaxhighlight lang
===Creation===
To create a simple map whose key is of type A and whose value is of type B, one would define the variable like so:
<
If one wanted to us a key type of '''int''' and a value of '''double''', you would define it like so:
<
===Insertion===
Line 1,495 ⟶ 2,340:
====Operator[]====
The first method is using the [] operator.
<
Of course, you can use a variable (or any [[rvalue]] of the correct type) for the key or value parameters:
<
double myValue = 3.14;
exampleMap[myKey] = myValue;</
====insert()====
The second approach is a little more complicated. We have to use the '''pair<>''' template:
<
or by using '''make_pair''' to avoid repeating key/value types:
<
===Lookup===
Line 1,511 ⟶ 2,356:
====operator[]====
We use it as an rvalue, supplying the correct key:
<
If the value doesn't already exist, a default-constructed object of the value's type will be inserted using the key you specified, and that default value will be returned.
====find()====
Alternatively, you can look up a value by using find(), storing its return value in an [[iterator]], and comparing the iterator against the map's end() [[sentinal value]]:
<
std::map<int, double>::iterator myIterator = exampleMap.find(myKey);
if(exampleMap.end() != myIterator)
Line 1,522 ⟶ 2,367:
// Return the value for that key.
myValue = myIterator->second;
}</
The need for the '''->second''' code is because our iterator points to a '''pair<>()''', and our value is the second member of that pair.
Line 1,530 ⟶ 2,375:
===Example===
This simple program creates a map, assigns a value to that map, retrieves a value from that map, and prints the value to STDOUT.
<
#include <iostreams>
Line 1,555 ⟶ 2,400:
// main() must return 0 on success.
return 0;
}</
=={{header|Ceylon}}==
<
ArrayList,
Line 1,593 ⟶ 2,438:
}
}</
=={{header|Chapel}}==
Line 1,600 ⟶ 2,445:
The creation of the domain is independent from the creation of the array, and in fact the same domain can be used for multiple arrays, creating associative arrays with identical sets of keys. When the domain is changed, all arrays that use it will be reallocated.
<syntaxhighlight lang="text">// arr is an array of string to int. any type can be used in both places.
var keys: domain(string);
var arr: [keys] int;
Line 1,628 ⟶ 2,473:
writeln("arr2 keys: ", arr2.domain);
writeln("arr2 values: ", arr2);</
{{out}}
Line 1,639 ⟶ 2,484:
=={{header|Clojure}}==
<
:key2 "value2"
:key3 "value3"}</
=={{header|ColdFusion}}==
<
<cfset myHash.key1 = "foo">
<cfset myHash["key2"] = "bar">
<cfset myHash.put("key3","java-style")></
In ColdFusion, a map is literally a java.util.HashMap, thus the above 3rd method is possible.
=={{header|Common Lisp}}==
<
;; or for implementation identity for other types!
;; Use #'equalp if you want case-insensitive keying on strings.
Line 1,664 ⟶ 2,509:
;; alist is written like this:
(defparameter *legs* '((cow . 4) (flamingo . 2) (centipede . 100)))
;; you can use assoc to do lookups and cons new elements onto it to make it longer.</
=={{header|Component Pascal}}==
BlackBox Componente Builder<br/>
Using a handmade collections module with the following interface<br/>
<
DEFINITION Collections;
Line 1,737 ⟶ 2,582:
END Collections.
</syntaxhighlight>
The program:
<
MODULE BbtAssociativeArrays;
IMPORT StdLog, Collections, Boxes;
Line 1,762 ⟶ 2,607:
END BbtAssociativeArrays.
</syntaxhighlight>
Execute:^Q BbtAssociativeArrays.Do<br/>
{{out}}
Line 1,770 ⟶ 2,615:
=={{header|Crystal}}==
<
# hash literals that don't perfectly match the intended hash type must be given an explicit type specification
# the following would fail without `of String => String|Int32`
hash2 : Hash(String, String|Int32) = {"foo" => "bar"} of String => String|Int32</
=={{header|D}}==
<
auto hash = ["foo":42, "bar":100];
assert("foo" in hash);
}</
=={{header|Dao}}==
<
h = { -> } # empty hash map, future inserted keys will not be ordered
m = { 'foo' => 42, 'bar' => 100 } # with ordered keys
h = { 'foo' -> 42, 'bar' -> 100 } # with unordered keys</
=={{header|Dart}}==
<
main() {
var rosettaCode = { // Type is inferred to be Map<String, String>
Line 1,826 ⟶ 2,671:
}
</syntaxhighlight>
{{out}}
<pre>
Line 1,843 ⟶ 2,688:
=={{header|Delphi}}==
<
{$APPTYPE CONSOLE}
Line 1,861 ⟶ 2,706:
lDictionary.Free;
end;
end.</
=={{header|Diego}}==
Diego has in-built <code>hash</code> and <code>dict</code> (short for 'dictionary') objects which function as associative arrays. The only exception is that <code>hash</code> can only accept uuid datatypes for keys. Diego also has <code>hash_</code> verb and <code>_hash</code> posit, used to hash an object/command.
To create a dictionary associative array:
<syntaxhighlight lang="diego">use_namespace(rosettacode)_me();
add_dict(tanzanianBanknoteObverseDipiction)_keys(500,1000,2000,5000,10000)_values(Karume,Nyerere,lion,black rhinoceros,elephant);
reset_ns[];</syntaxhighlight>
To create a hash associative array:
<syntaxhighlight lang="diego">use_namespace(rosettacode)_me();
add_hash(tanzanianBanknoteReverseDipiction)_values(
University of Dar es Salaam\, Central Hall Building,
Ikulu\, Dar es Salaam,
Ngome Kongwe\, Zanzibar,
Geita Cyanid Leaching Plant,
Bank of Tanzania Headquarters\, Dar es Salaam
);
reset_ns[];</syntaxhighlight>
=={{header|Dyalect}}==
Line 1,867 ⟶ 2,735:
Dyalect has a <code>Tuple</code> data type which allows to add labels to values:
<
print(t.Keys().ToArray())</
{{out}}
<pre>
=={{header|E}}==
<
["one" => 1, "two" => 2] # immutable, 2 mappings
[].asMap().diverge() # mutable, empty
["one" => 2].diverge(String, float64) # mutable, initial contents,
# typed (coerces to float)</
=={{header|EasyLang}}==
<syntaxhighlight>
# use array of array for this
proc hashGet ind$ . ar$[][] item$ .
for i to len ar$[][]
if ar$[i][1] = ind$
item$ = ar$[i][2]
return
.
.
item$ = ""
.
proc hashSet ind$ val$ . ar$[][] .
for i to len ar$[][]
if ar$[i][1] = ind$
ar$[i][2] = val$
return
.
.
.
clothing$[][] = [ [ "type" "t-shirt" ] [ "color" "red" ] ]
clothing$[][] &= [ "size" "xl" ]
#
hashSet "color" "green" clothing$[][]
hashGet "color" clothing$[][] col$
print col$
</syntaxhighlight>
=={{header|EchoLisp}}==
<
(lib 'hash) ;; needs hash.lib
(define H (make-hash)) ;; new hash table
Line 1,901 ⟶ 2,796:
(hash-count H)
→ 3
</syntaxhighlight>
=={{header|Ecstasy}}==
Defining the Map:
<syntaxhighlight lang="java">Map<String, Int> map = new HashMap();
map["foo"] = 5; // or: map.put("foo", 5)
map["bar"] = 10;
map["baz"] = 15;
map["foo"] = 6; // replaces previous value of 5</syntaxhighlight>
Literal map notation:
<syntaxhighlight lang="java">Map<String, Int> map = ["foo"=6, "bar"=10, "baz"=15];</syntaxhighlight>
Retrieving a value:
<syntaxhighlight lang="java">Int? mightBeNull = map["foo"];
Int neverNull = map.getOrDefault("foo", 0);
if (Int n := map.get("foo")) {
// if "foo" is in the map, then the variable "n" is set to its value
} else {
// if "foo" is not in the map, then the variable "n" is not defined
}</syntaxhighlight>
Iterate over keys:
<syntaxhighlight lang="java">for (String key : map) {
// the variable "key" is defined here
}</syntaxhighlight>
Iterate over values:
<syntaxhighlight lang="java">for (Int value : map.values) {
// the variable "value" is defined here
}</syntaxhighlight>
Iterate over key, value pairs:
<syntaxhighlight lang="java">for ((String key, Int value) : map) {
// the variables "key" and "value" are defined here
}</syntaxhighlight>
=={{header|Elena}}==
ELENA 5.0:
<
public program()
Line 1,916 ⟶ 2,841:
map["key3"]:= "foo3";
map["key4"]:= "foo4";
}</
=== Strong typed dictionary ===
<
public program()
Line 1,930 ⟶ 2,855:
map["key3"]:= "foo3";
map["key4"]:= "foo4";
}</
=={{header|Elixir}}==
===Map literals===
An empty map:
<syntaxhighlight lang="elixir">
%{}
</syntaxhighlight>
A map with key-value pairs of different types:
<syntaxhighlight lang="elixir">
%{"one" => :two, 3 => "four"}
</syntaxhighlight>
Maps with atoms as keys:
<syntaxhighlight lang="elixir">
%{a: 1, b: 2}
# equivalent to
%{:a => 1, :b => 2}
</syntaxhighlight>
===Programmatic map creation===
{{trans|Erlang}}
<
def test_create do
IO.puts "< create Map.new >"
Line 1,950 ⟶ 2,897:
end
RC.test_create</
{{out}}
Line 1,964 ⟶ 2,911:
=={{header|Emacs Lisp}}==
<
(puthash 'key 'value my-table)</
<code>make-hash-table</code> compares keys with <code>eql</code> by default. This suits symbols and numbers (including floating point). For string keys an <code>equal</code> test can be used,
<
(puthash "key" 123 my-table)</
<code>define-hash-table-test</code> can create other key comparison types.
=={{header|EMal}}==
<syntaxhighlight lang="emal">
Map empty = Map(int, text) # creates an empty map
writeLine(empty)
var longFruit = Map(int, text).of(1, "banana") # creates a map with the pair 1 => "banana"
longFruit[2] = "melon" # associates a key of 2 with "melon"
longFruit.insert(3, "avocado")
writeLine(longFruit) # prints the map
var shortFruit = int%text[4 => "kiwi", 5 => "apple"] # map creation using arrow notation
writeLine(shortFruit[5]) # retrieves the value with a key of 5 and prints it out
writeLine(shortFruit.length) # prints the number of entries
writeLine(shortFruit) # prints the map
writeLine(text%text["Italy" => "Rome", "France" => "Paris", "Germany" => "Berlin", "Spain" => "Madrid"])
</syntaxhighlight>
{{out}}
<pre>
[]
[1:banana,2:melon,3:avocado]
apple
2
[4:kiwi,5:apple]
[Italy:Rome,France:Paris,Germany:Berlin,Spain:Madrid]
</pre>
=={{header|Erlang}}==
Erlang offers several associative array type data structures, this example uses the dictionary data structure.
<
-module(assoc).
-compile([export_all]).
Line 1,991 ⟶ 2,963:
io:format("~p: ~b~n",[K,dict:fetch(K,D)])
end, dict:fetch_keys(D)).
</syntaxhighlight>
{{out}}
Line 2,003 ⟶ 2,975:
=={{header|F Sharp|F#}}==
.NET 3.5 Generic Dictionary (mutable)
<
let dic = System.Collections.Generic.Dictionary<string,string>() ;;
dic.Add("key","val") ;
dic.["key"] <- "new val" ;
</syntaxhighlight>
Functional dictionary (immutable)
<
let d = [("key","val");("other key","other val")] |> Map.ofList
let newd = d.Add("new key","new val")
Line 2,017 ⟶ 2,989:
| Some(v) -> printfn "%s" v
| None -> printfn "not found"
</syntaxhighlight>
=={{header|Factor}}==
Associative mappings follow the associative protocol. See [http://docs.factorcode.org/content/article-assocs-protocol.html the docs].
Here's an example using a hashtable that can be run in the listener :
<
{ [ "one" swap at . ]
[ 2 swap value-at . ]
[ "three" swap at . ]
[ [ 3 "three" ] dip set-at ]
[ "three" swap at . ] } cleave</
=={{header|Fantom}}==
Line 2,033 ⟶ 3,005:
Associative arrays are called 'maps' in Fantom:
<
class Main
{
Line 2,051 ⟶ 3,023:
}
}
</syntaxhighlight>
=={{header|Forth}}==
Line 2,058 ⟶ 3,030:
The Forth dictionary is normally only used for function and symbol definitions, but you can also define separate ''wordlists'' for holding functions or data. There is no special syntax in the language for this, but you can define your own. All of Forth's defining words are available for adding things to the wordlist, but CREATE is most generic.
<
search-wordlist if
>body @
Line 2,078 ⟶ 3,050:
s" alpha" bar get . \ 5
8 s" Alpha" bar put \ Forth dictionaries are normally case-insensitive
s" alpha" bar get . \ 8</
This is not necessarily a good option in all Forths, as the dictionary may be implemented as a simple linked list (normally not a problem because the dictionary is only used for compiling and interactive interpretation). [[GNU Forth]] and many other hosted Forths use hash tables for the dictionary, so this is a fine choice. If you need case-sensitive keys, GNU Forth has <tt>table</tt> and <tt>table-find</tt>, replacing <tt>wordlist</tt> and <tt>search-wordlist</tt>, respectively.
Line 2,086 ⟶ 3,058:
Hashtable for mapping strings to integer
<
\ Create a hash table 'table' in the dictionary with a starting size of 10
Line 2,104 ⟶ 3,076:
[ELSE]
.( Entry not present.) cr
[THEN]</
{{works with|4tH|3.64}}
Similar functionality is available in 4tH. A binary search is applied to search values, hence hashtables can be quite compact.
<syntaxhighlight lang="text">include lib/hash.4th
include lib/hashkey.4th
\ Create a hash table 'table' with a starting size of 10
['] fnv1a is hash \ set hash method
10 constant /htable \ determine the size
/htable array htable \ allocate the table
latest /htable hashtable \ turn it into a hashtable
\ Insert entries
5 s" foo" htable put
10 s" bar" htable put
15 s" baz" htable put
\ Get entry from the table
s" bar" htable get error? if
.( Entry not present.) cr drop
else
.( Value: ) . cr
then
</syntaxhighlight>
=={{header|FreeBASIC}}==
Uses unions to store the keys and associated values, and FreeBASIC's ability to resize arrays makes adding new entries easy.
<
enum datatype
Line 2,176 ⟶ 3,175:
print Dictionary(0).value.value.strng
print Dictionary(1).key.value.integ</
{{out}}
<pre>
Line 2,185 ⟶ 3,184:
=={{header|Free Pascal}}==
FPC 3.2.0.+. Similar to Delphi.
<
{$IFDEF FPC}{$MODE DELPHI}{$ENDIF}
{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}
Line 2,201 ⟶ 3,200:
lDictionary.Free;
end;
end.</
FPC 2.4+. Using FGL instead of rtl-generics:
<
{$IFDEF WINDOWS}{$APPTYPE CONSOLE}{$ENDIF}
{$MODE DELPHI}
Line 2,219 ⟶ 3,218:
lDictionary.Free;
end;
end.</
=={{header|Futhark}}==
<
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
void local fn DoIt
CFDictionaryRef dict1 = fn DictionaryWithObjects( @"Alpha", @"A", @"Bravo", @"B", @"Charlie", @"C", @"Delta", @"D", NULL )
CFDictionaryRef dict2 = @{@"A":@"Alpha", @"B":@"Bravo", @"C":@"Charlie", @"D":@"Delta"}
CFMutableDictionaryRef dict3 = fn MutableDictionaryWithCapacity(0)
MutableDictionarySetObjectForKey( dict3, @"Alpha", @"A" )
MutableDictionarySetObjectForKey( dict3, @"Bravo", @"B" )
MutableDictionarySetObjectForKey( dict3, @"Charlie", @"C" )
MutableDictionarySetObjectForKey( dict3, @"Delta", @"D" )
CFMutableDictionaryRef dict4 = fn MutableDictionaryWithDictionary( @{@"A":@"Alpha", @"B":@"Bravo", @"C":@"Charlie", @"D":@"Delta"} )
print fn DictionaryObjectForKey( dict1, @"A" )
print dict1[@"B"]
print dict2[@"C"]
print dict3[@"D"]
print dict4
end fn
fn DoIt
HandleEvents
</syntaxhighlight>
{{out}}
<pre>
Alpha
Bravo
Charlie
Delta
{
A = Alpha;
B = Bravo;
C = Charlie;
D = Delta;
}
</pre>
=={{header|Gambas}}==
Line 2,229 ⟶ 3,270:
=={{header|Go}}==
Allowable key types are those with == and != operators. This includes is boolean, numeric, string, pointer, channel, and interface types. It also includes structs and arrays containing only these types. Disallowed as map keys are all slice, function, and map types.
<
var x map[string]int
Line 2,251 ⟶ 3,292:
x = map[string]int{
"foo": 2, "bar": 42, "baz": -1,
}</
=={{header|Gosu}}==
As an OOP language with generics Gosu can use any variety of Map classes. In addition Gosu provides associative array syntax for all objects.
<
var emptyMap = new HashMap<String, Integer>()
Line 2,289 ⟶ 3,330:
var scott = new Person()
scott["name"] = "Scott"
scott["age"] = 29</
=={{header|Groovy}}==
Create an empty map and add values
<
map[7] = 7
map['foo'] = 'foovalue'
Line 2,302 ⟶ 3,343:
assert 'foovalue' == map.foo
assert 'barvalue' == map['bar']
assert 'moovalue' == map.get('moo')</
Create a pre-populated map and verify values
<
assert 7 == map[7]
assert 'foovalue' == map.foo
assert 'barvalue' == map['bar']
assert 'moovalue' == map.get('moo')</
=={{header|Harbour}}==
Create an empty array and add values:
<
arr[ 10 ] := "Val_10"
arr[ "foo" ] := "foovalue"</
Create and initialize array:
<
// or
arr := { 10 => "Val_10", "foo" => "foovalue" }</
=={{header|Haskell}}==
Binary trees:
{{works with|GHC}}
<
dict = fromList [("key1","val1"), ("key2","val2")]
ans = Data.Map.lookup "key2" dict -- evaluates to Just "val2"
</syntaxhighlight>
It is also possible to use association lists (lists of pairs). It is inefficient (O(n) lookup), but simple.
<
ans = lookup "key2" dict -- evaluates to Just "val2"
</syntaxhighlight>
GHC also had an imperative hash table implementation in the <code>Data.HashTable</code> module, but was removed in <code>GHC 7.8</code>.
Line 2,343 ⟶ 3,384:
=={{header|hexiscript}}==
<
let d["test"] "test" # Strings can be used as index
let d[123] 123 # Integers can also be used as index
println d["test"]
println d[123]</
=={{header|Icon}} and {{header|Unicon}}==
Icon and Unicon associative arrays are called tables. Any value may be used as a key including complex structures. Tables can have default values and they have no inherent size limitation growing from empty to whatever size is needed.
<
local t
t := table()
t["foo"] := "bar"
write(t["foo"])
end</
=={{header|Inform 7}}==
Line 2,364 ⟶ 3,405:
===Static relation===
<
Connection relates various texts to one number. The verb to be connected to implies the connection relation.
Line 2,381 ⟶ 3,422:
let V be the number that "baz" relates to by the connection relation;
say "'baz' => [V].";
end the story.</
===Dynamic relation===
<
When play begins:
Line 2,398 ⟶ 3,439:
let V be the number that "baz" relates to by R;
say "'baz' => [V].";
end the story.</
=={{header|Insitux}}==
It is possible to use any value type for both keys and values for a dictionary in Insitux.
<syntaxhighlight lang="insitux">{
:a "value" ;keyword key, string value
:b 123 ;keyword key, number value
456 [1 2 3] ;number key, vector value
[5 6 7] :b ;vector key, keyword value
{:a 1} {:b 2} ;dictionary key, dictionary value
}</syntaxhighlight>
<syntaxhighlight lang="insitux">;use dictionary as function for lookup; commas for readability, treated as white-space
> ({:a 1, :b 2, :c 3} :b)
2</syntaxhighlight>
<syntaxhighlight lang="insitux">;extend existing dictionary by using it as a function with two arguments
> ({:a 1, :b 2, :c 3} :b 3)
{:a 1, :b 3, :c 3}</syntaxhighlight>
=={{header|Ioke}}==
<
=={{header|J}}==
Line 2,409 ⟶ 3,470:
However, it's also possible to use the symbol table itself to hold the names. The symbol table has limitations (can only accept syntactically valid names), but we can turn arbitrary strings into valid symbols using base 62 encode and prefixing with a letter (hypothetically speaking, base 64 encode would let us build longer names than base 62, because of computational complexity issues - but the J symbol table also comes with a name length limit - 255 characters - and does not support 64 different characters in names):
<
encode=: 'z', (a.{~;48 65 97(+ i.)&.>10 26 26) {~ 62x #.inv 256x #. a.&i.
get=: ".@encode
has=: 0 <: nc@<@encode
set=:4 :'(encode x)=:y'</
Example use:
<
'foo' set__example 1 2 3
1 2 3
Line 2,429 ⟶ 3,490:
get__example 'bletch'
7 8 9
codestroy__example''</
Note that J's symbols (http://www.jsoftware.com/help/dictionary/dsco.htm) might also be used for this purpose. However, symbols are not garbage collected within a J session (and, instead, a mechanism is provided to optionally preserve them across sessions).
=={{header|
<syntaxhighlight lang="jakt">
fn main() {
let dictionary = ["foo": 1, "bar": 2]
println("{}", dictionary)
}
</syntaxhighlight>
=={{header|Java}}==
<p>
Java offers an associative array, referred to as a <code>Map</code>, as part of the Collections Framework.<br />
There are numerous implementing classes, each which provide unique functionality for various tasks.<br />
</p>
<p>
It's worth noting that Java also offers the <code>Dictionary</code> class, which appears to be less preferred, according to Java.<br />
<kbd><i>"[The Map] interface takes the place of the Dictionary class ..."</i></kbd>.
</p>
<p>
The most generalized <code>Map</code> would be the <code>HashMap</code>, which is a basic, unordered, set of <kbd>keys</kbd> and <kbd>values</kbd>.<br />
There is also the <code>LinkedHashMap</code>, which will preserve the order of input.<br />
There is the <code>TreeMap</code>, which is used to store the <kbd>key</kbd>s in a specific order, using the <kbd>key</kbd>'s <code>compareTo</code> method.
Optionally, you could provide your own <kbd>comparator</kbd> using the <code>Comparator</code> interface, which I'll demonstrate below.<br />
There are numerous other implementing classes, which can be found under the <code>Map</code> <kbd>Javadoc</kbd>,
[https://docs.oracle.com/en/java/javase/20/docs/api/java.base/java/util/Map.html. Map (Java SE 20 & JDK 20)].
</p>
<p>
Here is a basic implementation of a <code>HashMap</code>.
</p>
<syntaxhighlight lang="java">
Map<String, Integer> map = new HashMap<>();
</syntaxhighlight>
<p>
To add a <kbd>key</kbd> and <kbd>value</kbd> pair, you use the <code>Map.put</code> method.<br />
A useful feature of <code>Map.put</code> is that if the <kbd>key</kbd> already exists, thus is being overridden,
it will return the overridden value, otherwise <code>null</code>.
</p>
<syntaxhighlight lang="java">
map.put("rosetta", 100);
map.put("code", 200);
</syntaxhighlight>
<p>
To get a <kbd>value</kbd>, you use the <code>Map.get</code> method, specifying the <kbd>key</kbd> as the parameter.<br />
If the specified <kbd>key</kbd> does not exist, <code>null</code> is returned.
</p>
<syntaxhighlight lang="java">
int valueA = map.get("rosetta");
int valueB = map.get("code");
</syntaxhighlight>
<p>
To mutate a <kbd>key</kbd>'s <kbd>value</kbd>, you use the <code>Map.replace</code> method.
</p>
<syntaxhighlight lang="java">
map.replace("rosetta", 300);
</syntaxhighlight>
<p>
Alternately, you can replace the <kbd>value</kbd>, only if it is of a current <kbd>value</kbd>.<br />
So, in this example it will return <kbd>true</kbd>, only if the <kbd>key</kbd> <kbd><i>"rosetta"</i></kbd> had the current <kbd>value</kbd> of <kbd><i>100</i></kbd>.
</p>
<syntaxhighlight lang="java">
boolean replaced = map.replace("rosetta", 100, 300);
</syntaxhighlight>
<p>
To check for the existence of a <kbd>key</kbd>, you use the <code>containsKey</code> method.
</p>
<syntaxhighlight lang="java">
boolean contains = map.containsKey("rosetta");
</syntaxhighlight>
<p>
And to check for the existence of a <kbd>value</kbd>, you use the <code>containsValue</code> method.
</p>
<syntaxhighlight lang="java">
boolean contains = map.containsValue(100);
</syntaxhighlight>
<p>
A <code>LinkedHashMap</code> is exactly the same as a <code>HashMap</code>, except it will preserve the order in which the <kbd>key</kbd>s were added.
</p>
<syntaxhighlight lang="java">
Map<String, Integer> map = new LinkedHashMap<>();
map.put("rosetta", 100);
map.put("code", 200);
</syntaxhighlight>
<p>
A <code>TreeMap</code> is useful for when you want the <kbd>key</kbd>s in a specific order.<br />
By default, it will use the <kbd>key</kbd>'s <code>compareTo</code> method, to determine the order.<br />
So, if you're <kbd>key</kbd> is a <code>String</code>, the order will be ascending, similar to an actual dictionary.
</p>
<syntaxhighlight lang="java">
Map<String, Integer> map = new TreeMap<>();
map.put("rosetta", 100);
map.put("code", 200);
</syntaxhighlight>
<p>
You could, optionally, specify a comparator by implementing a <code>Comparator</code> interface.<br />
A <code>TreeMap</code>, conveniently, only requires you to implement the <code>compare</code> method of the <code>Comparator</code>,
so the implementation can be done as an <kbd>anonymous class</kbd>.
</p>
<syntaxhighlight lang="java">
Comparator<String> comparator = new Comparator<String>() {
public int compare(String stringA, String stringB) {
if (stringA.compareTo(stringB) > 0) {
return -1;
} else if (stringA.compareTo(stringB) < 0) {
return 1;
}
return 0;
}
};
</syntaxhighlight>
<p>
Which you then supply as an argument to the constructor.
</p>
<syntaxhighlight lang="java">
Map<String, Integer> map = new TreeMap<>(comparator);
</syntaxhighlight>
<p>
To make things even simpler, you could use a <kbd>lambda</kbd> for the <kbd>anonymous class</kbd>.
</p>
<syntaxhighlight lang="java">
Comparator<String> comparator = (stringA, stringB) -> {
if (stringA.compareTo(stringB) > 0) {
return -1;
} else if (stringA.compareTo(stringB) < 0) {
return 1;
}
return 0;
};
</syntaxhighlight>
=={{header|JavaScript}}==
Line 2,470 ⟶ 3,626:
Javascript object property names (keys) are strings. Other types and expressions can be used with square bracket notation, they are evaluated and converted to strings and the result used as the property name. Using quotes on property names avoids potential collisions with reserved JavaScript key words.
<
assoc['foo'] = 'bar';
Line 2,491 ⟶ 3,647:
alert('key:"' + key + '", value:"' + assoc[key] + '"');
}
}</
ECMAScript 6 (ES6) offers both a map and a weak map implementation. While Objects must use strings, Maps may use objects, functions, and numbers as keys in addition to strings.
<
fn = function () {},
obj = {};
Line 2,515 ⟶ 3,671:
for (var key of map.keys()) {
console.log(key + ' => ' + map.get(key));
}</
=={{header|jq}}==
===Associative Arrays with String-Valued Keys===
In jq, JSON objects can be used as associative arrays, it being understood that only strings can be used as keys. To avoid confusion, for the remainder of this section, we refer to JSON objects as such. Their type in jq is "object".
<
{}
Line 2,541 ⟶ 3,697:
# Alteration of the value of an existing key:
{"A": 65}["A"] = "AA"</
===Associative Arrays with JSON-Valued Keys===
In this subsection, we define addKey(key;value), getKey(key), and removeKey(key)
to operate on a hash table for which the keys may be any JSON entities. This is done by defining a collisionless hash function.
<
if type == "object" then with_entries(.value = (.value|collisionless))|tostring
elif type == "array" then map(collisionless)|tostring
Line 2,560 ⟶ 3,716:
def getKey(key): .[key|collisionless];
def removeKey(key): delpaths( [ [key|collisionless] ] );</
'''Example''':
<
produces:
<
=={{header|Jsish}}==
From Javascript. jsish warns of duplicate ''var'', in this case the ''assoc'' variable is reused.
<
assoc['foo'] = 'bar';
Line 2,601 ⟶ 3,757:
assoc ==> { "another-key":3, foo:"bar" }
=!EXPECTEND!=
*/</
{{out}}
<pre>prompt$ jsish -u associativeArray.jsi
Line 2,609 ⟶ 3,765:
{{works with|Julia|0.6}}
We build dictionaries associating to some characters their code points, by listing the key/value pairs, through a dictionary comprehension, by creating an empty dictionary and filling it, by using the specific syntax associated to typed dictionaries.
<
# Dict{Char,Int64} with 2 entries:
# 'b' => 98
Line 2,635 ⟶ 3,791:
typeof(dict) # type is infered correctly
# Dict{Char,Int64}
</syntaxhighlight>
=={{header|K}}==
Keys in a dictionary must be symbols (`symbol).
<
d1:.((`foo;1); (`bar;2); (`baz;3))
/ extracting a value
d1[`bar]
2</
Another approach.
<
d2[`"zero"]:0
d2[`"one"]:1
Line 2,655 ⟶ 3,811:
.((`zero;0;)
(`one;1;)
(`two;2;))</
Extracting the keys and values.
<
`zero `one `two
d2[] / the values
0 1 2</
=={{header|Kotlin}}==
{{trans|Java}}
<
// map definition:
val map = mapOf("foo" to 5,
Line 2,691 ⟶ 3,847:
// iterate over key, value pairs:
for ((k, v) in map) println("$k => $v")
}</
=={{header|Lambdatalk}}==
Associative arrays are not currently built in the JS.js kernel of lambdatalk but are added via the lib_hash library page.
<
1) a (currently) reduced set of functions:
Line 2,753 ⟶ 3,909:
bar: Barcelona, Catalunya
]
</syntaxhighlight>
=={{header|Lang5}}==
<
: first 0 extract nip ; : second 1 extract nip ;
Line 2,772 ⟶ 3,928:
'bar over at .
'hello 'bar rot set-at
20 'baz rot set-at .</
=={{header|langur}}==
Hash keys in langur may be numbers or strings. Number keys are simplified, so that 1.0 is the same key as 1.
<
# may assign with existing or non-existing hash key (if hash is mutable)
Line 2,788 ⟶ 3,944:
# using an alternate value in case of invalid index; prevents exception
writeln .hash[1; 42]
writeln .hash[2; 42]</
{{out}}
Line 2,798 ⟶ 3,954:
=={{header|Lasso}}==
<
// Define an empty map
Line 2,835 ⟶ 3,991:
#1 -> reverse
}
#mymap // map(2 = YADSEUT, fourth = YADSRUHT, one = YADNOM, 3 = YADSENDEW)</
=={{header|LFE}}==
<
(let* ((my-dict (: dict new))
(my-dict (: dict store 'key-1 '"value 1" my-dict))
Line 2,845 ⟶ 4,001:
(: io format '"some data: ~p~n" (list (: dict fetch 'key-1 my-dict))))
</syntaxhighlight>
=={{header|Liberty BASIC}}==
Needs the sublist library from http://basic.wikispaces.com/SubList+Library since LB does not have built-in associative arrays.
<syntaxhighlight lang="lb">
data "red", "255 50 50", "green", "50 255 50", "blue", "50 50 255"
data "my fave", "220 120 120", "black", "0 0 0"
Line 2,862 ⟶ 4,018:
print " Key 'green' is associated with data item "; sl.Get$( myAssocList$, "green")
</syntaxhighlight>
Key 'green' is associated with data item 50 255 50
=={{header|Lingo}}==
<
put props[#key2]
Line 2,875 ⟶ 4,031:
-- "value2"
put props.getProp(#key2)
-- "value2"</
=={{header|LiveCode}}==
Livecode arrays are only associative, but can be accessed by ordinal if they are used as the key.
<
local tArray
put "value 1" into tArray["key 1"]
Line 2,888 ⟶ 4,044:
"length of item 3:" && the length of tArray["abc"] & return & \
"keys:" && the keys of tArray
end assocArray</
Output
<
length of item 3: 5
keys: key numbers
abc
key 1</
=={{header|Logo}}==
[[UCB Logo]] has "property lists" which associate names with values. They have their own namespace.
<
pprop "animals "dog 4
pprop "animals "mouse 11
print gprop "animals "cat ; 5
remprop "animals "dog
show plist "animals ; [mouse 11 cat 5]</
=={{header|LOLCODE}}==
BUKKITs are associative arrays
<
I HAS A Hash ITZ A BUKKIT
Hash HAS A key1 ITZ "val1" BTW This works for identifier-like keys, like obj.key in JavaScript
Line 2,913 ⟶ 4,069:
VISIBLE Hash'Z SRS "key-2"
KTHXBYE
</syntaxhighlight>
{{Out}}
<pre>1</pre>
Line 2,919 ⟶ 4,075:
=={{header|Lua}}==
Lua tables are Hashes
<
hash[ "key-1" ] = "val1"
hash[ "key-2" ] = 1
hash[ "key-3" ] = {}</
Returns nil on unknown key.
=={{header|M2000 Interpreter}}==
Μ2000 has Inventory object to use it as a Map. All keys converted to strings. If a key has no value then key is the value until we place one. A special type of Inventory is the Inventory Queue, where we can use same keys, and we can't delete except from the last append.
<syntaxhighlight lang="m2000 interpreter">
Inventory A="100":=1, "200":=5, 10:=500, 20:="Hello There"
Print len(A)
Line 2,949 ⟶ 4,105:
If Exist(A, "End") Then Print Eval(A)=5000
</syntaxhighlight>
=={{header|Maple}}==
Maple tables are hashed arrays. A table can be constructed by using the table constructor.
<
T := table(["foo" = 1, sin(x) = cos(x), (2, 3) = 4])
Line 2,963 ⟶ 4,119:
> T["foo"];
1</
New entries are added by assignment.
<
T["bar"] := 2
> T[ "bar" ];
2</
Entries can be removed as follows.
<
T["foo"] := T["foo"]
> T[ "foo" ];
T["foo"]</
(The latter output indicates that T["foo"] is an unassigned name.)
=={{header|Mathematica}} / {{header|Wolfram Language}}==
<
=={{header|MATLAB}} / {{header|Octave}}==
Line 2,986 ⟶ 4,142:
Associative arrays are called structs. The following methods of creating hash are equivalent.
<
hash.b = 2;
hash.C = [3,4,5]; </
alternatively
<
hash = setfield(hash,'a',1);
hash = setfield(hash,'b',2);
hash = setfield(hash,'C',[3,4,5]); </
or
<
hash.('b') = 2;
hash.('C') = [3,4,5]; </
<pre>>> disp(hash)
Line 3,011 ⟶ 4,167:
===MATLAB only: containers.Map===
Use of containers.Map removes some restrictions on key types that structs have. Keys can all be numeric or all be strings. Values can be of any type. Key and value types cannot be changed after creation of the containers.Map object.
<
is equivalent to
<
m('a') = 1;
m('b') = 2;
m('C') = 3;</
since the KeyType defaults to 'char'. For numeric keys, the key and value types must be specified at creation.
<
is equivalent to
<
m(51) = 'fiftyone';
m(72) = 'seventytwo';
m(37) = 'thirtyseven';</
Usage:
<pre>>> m = containers.Map([51 72 37], {'fiftyone' 'seventytwo' 'thirtyseven'});
Line 3,039 ⟶ 4,195:
=={{header|Maxima}}==
<
h[1]: 6;
Line 3,045 ⟶ 4,201:
arrayinfo(h);
[hashed, 1, [1], [9]]</
=={{header|min}}==
{{works with|min|0.19.6}}
<
=={{header|MiniScript}}==
A map literal in MiniScript is enclosed in curly braces, with key:value pairs separated by commas. Keys and values may be any type. Retrieval or assignment is by putting the key in square brackets. As syntactic sugar, when a string key follows the rules of a MiniScript identifier (starts with a letter and contains only letters, numbers, and underscores), you may also access it with dot syntax.
<
print map[3]
Line 3,060 ⟶ 4,216:
print map["foo"]
print map.foo // same as map["foo"] (only for string keys that are valid identifiers)
</syntaxhighlight>
=={{header|Nemerle}}==
This demonstrates two of several constructors, initializing the hashtable with a list of tuples or just specifying an initial capacity.
<
using System.Console;
using Nemerle.Collections;
Line 3,080 ⟶ 4,236:
WriteLine(hash1[entry]);
}
}</
=={{header|NetRexx}}==
<
options replace format comments java crossref symbols
Line 3,094 ⟶ 4,250:
say '<hash key="'key0'" value="'hash[key0]'" />' -- Display a value for a key that wasn't set
say '<hash key="'key1'" value="'hash[key1]'" />' -- Display a value for a key that was set</
{{out}}
Line 3,103 ⟶ 4,259:
=={{header|Nim}}==
<
var
Line 3,131 ⟶ 4,287:
echo "iterate values:" # iterating over values
for key in hash.values:
echo key</
{{out}}
<pre>hash has 3 elements
Line 3,151 ⟶ 4,307:
=={{header|Oberon-2}}==
{{works with| oo2c Version 2}}
<
MODULE AssociativeArray;
IMPORT
Line 3,194 ⟶ 4,350:
END AssociativeArray.
</syntaxhighlight>
=={{header|Objeck}}==
Line 3,200 ⟶ 4,356:
=== Associative map===
<
# create map
map := StringMap->New();
Line 3,211 ⟶ 4,367:
map->Find("thirteen")->As(IntHolder)->GetValue()->PrintLine();
map->Find("seven")->As(IntHolder)->GetValue()->PrintLine();
</syntaxhighlight>
===Hash table===
<
# create map
map := StringHash->New();
Line 3,225 ⟶ 4,381:
map->Find("thirteen")->As(IntHolder)->GetValue()->PrintLine();
map->Find("seven")->As(IntHolder)->GetValue()->PrintLine();
</syntaxhighlight>
=={{header|Objective-C}}==
Line 3,231 ⟶ 4,387:
You can use a NSDictionary to create an immutable hash. A dictionary can contain only objects; if you want store non objects like integer, you have to box it in NSNumber.
<
@"Joe Doe", @"name",
[NSNumber numberWithUnsignedInt:42], @"age",
[NSNull null], @"extra",
nil];</
The same as the above with the new literal syntax in clang 3.1+ / Apple LLVM Compiler 4.0+ (XCode 4.4+) :
<
@"name": @"Joe Doe",
@"age": @42,
@"extra": [NSNull null],
};</
To create a mutable dictionary, use NSMutableDictionary:
<
[dict setObject:@"Joe Doe" forKey:@"name"];
[dict setObject:[NSNumber numberWithInt:42] forKey:@"age"];</
You can access value with objectForKey:. If a key does not exists, nil is returned.
<
unsigned age = [dict objectForKey:@"age"] unsignedIntValue];
id missing = [dict objectForKey:@"missing"];</
=={{header|OCaml}}==
===Hash table===
A simple idiom to create a hash table mapping strings to integers:
<
List.iter (fun (key, value) -> Hashtbl.add hash key value)
["foo", 5; "bar", 10; "baz", 15];;</
To retrieve a value:
<
To retrieve a value, returning a default if the key is not found:
<
===Binary tree===
A simple idiom to create a persistent binary tree mapping strings to integers:
<
type t = string
let compare = Pervasives.compare
Line 3,278 ⟶ 4,434:
StringMap.empty
["foo", 5; "bar", 10; "baz", 15]
;;</
To retrieve a value:
<
To retrieve a value, returning a default if the key is not found:
<
===Association list===
Some list functions allow you to use a list as an associative map, although the access time is O(N) so a Hashtbl or binary tree should be used for larger data-sets.
<
(* retrieve value *)
Line 3,291 ⟶ 4,447:
(* see if key exists *)
print_endline (if List.mem_assoc "foo" dict then "key found" else "key missing")</
=={{header|Ol}}==
Line 3,298 ⟶ 4,454:
You can use only values as keys (atomic numbers, constants) and, as exception, symbols (symbols are references, but unique). No strings, lists, vectors and other objects can be used directly. In such cases use hashes or similar mechanisms.
<
;;; empty associative array
#empty
Line 3,330 ⟶ 4,486:
(print my-new-map)
; ==> #((1 . 100) (2 . 200) (7 . 777) (the-key . the-value))
</syntaxhighlight>
=={{header|ooRexx}}==
Line 3,343 ⟶ 4,499:
Defining the map:
<
map["foo"] = 5
map["bar"] = 10
map["baz"] = 15
map["foo"] = 6
</syntaxhighlight>
"Putting" a value for a key that already exists ("map["foo"] = 6" in this example) will replace and return the old value for the key.
Retrieving a value:
<
item = map["invalid"] -- => .nil</
Note that it is possible to put <code>.nil</code> as a value, so <code>.nil</code> being returned as a value is not sufficient for determining that the key is not in the collection. There is a <code>hasIndex</code> method for that.
Iterate over keys:
<
say key
end
</syntaxhighlight>
Iterate over values:
<
say value
end
</syntaxhighlight>
Iterate over key, value pairs:
<syntaxhighlight lang="oorexx">
s = map~supplier
loop while s~available
Line 3,373 ⟶ 4,529:
s~next
end
</syntaxhighlight>
=={{header|OxygenBasic}}==
Not very efficient but the 'find' method could be optimised very easily.
<
def n 200
Line 3,430 ⟶ 4,586:
A.dat("computers")="LC99" '
print A.dat("computers") 'result LC99
</syntaxhighlight>
=={{header|Oz}}==
A mutable map is called a 'dictionary' in Oz:
<
Dict = {Dictionary.new}
in
Line 3,442 ⟶ 4,598:
Dict.foo := 20
{Inspect Dict}</
'Records' can be consideres immutable maps:
<
Rec = name(foo:5 bar:10 baz:20)
in
{Inspect Rec}</
=={{header|PARI/GP}}==
Line 3,454 ⟶ 4,610:
GP's associative arrays are called maps, and can be created like so:
<
They can be used as follows:
<
mapput(M, 17, "different value");
mapput(M, "key2", Pi);
mapget(M, "key2") \\ returns Pi
mapisdefined(M, "key3") \\ returns 0
mapdelete(M, "key2");</
In PARI the commands are <code>gtomap</code>, <code>mapput</code>, <code>mapget</code>, <code>mapisdefined</code>, and <code>mapdelete</code>. You can also use the solutions in [[Associative arrays/Creation/C]].
Line 3,468 ⟶ 4,624:
===Hash===
Definition:
<
my %hash = (
key1 => 'val1',
Line 3,482 ⟶ 4,638:
'three', -238.83,
4, 'val3',
);</
Use:
<
$hash{key1} = 'val1';
@hash{'key1', 'three'} = ('val1', -238.83);</
===HashRef===
Definition:
<
key1 => 'val1',
'key-2' => 2,
three => -238.83,
4 => 'val3',
}</
Use:
<
$hashref->{key1} = 'val1';
@{$hashref}{('key1', 'three')} = ('val1', -238.83);</
===Key Types===
Line 3,522 ⟶ 4,678:
integer tid=new_dict(), and pass that as an additional (final) parameter to the other routines (taking care not to miss
any). When you have no further use for it, an entire dictionary can be removed by invoking destroy_dict(tid).
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #7060A8;">setd</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"one"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
Line 3,532 ⟶ 4,688:
<span style="color: #7060A8;">deld</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span>
<span style="color: #0000FF;">?</span><span style="color: #7060A8;">getd</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">)</span> <span style="color: #000080;font-style:italic;">-- shows 0</span>
<!--</
=={{header|Phixmonti}}==
<
def getd /# dict key -- dict data #/
Line 3,569 ⟶ 4,725:
PI getd tostr print nl
3 getd print
</syntaxhighlight>
=={{header|PHP}}==
<
$array = []; // Simpler form of array initialization
$array['foo'] = 'bar';
Line 3,592 ⟶ 4,748:
// Check if key exists in the associative array
echo(isset($array['foo'])); // Faster, but returns false if the value of the element is set to null
echo(array_key_exists('foo', $array)); // Slower, but returns true if the value of the element is null</
===Iterate over key/value===
<
{
echo "Key: $key Value: $value";
}</
=={{header|Picat}}==
Associative arrays are called "map" in Picat.
<syntaxhighlight lang="picat">go =>
% Create an empty map
Map = new_map(),
println(Map),
% add some data
Map.put(a,1),
Map.put("picat",2),
Map.put("picat",3), % overwrite values
% Add a new value (a long list of different stuff)
Map.put([a,list,of,different,"things",[including, lists],3.14159],2),
println(Map),
println(a=Map.get(a)), % get a value
println(b=Map.get(b,'default value')), % the second argument to get/2 is the default value
% create a map from a list of values
Map2 = new_map([K=V : {K,V} in zip([a,b,c,d,e,f,g,h],1..8)]),
println(Map2),
println(h=Map2.get(h)),
% Check if there is a value in the map
if not Map2.has_key(z) then
println("no key 'z'")
end,
% keys() and value() returns unsorted list of elements
% so we sort them.
println(keys=Map2.keys().sort()),
println(values=Map2.values().sort()),
% Print the values for the keys that are even
println([K : K=V in Map2, V mod 2=0].sort),
nl.
</syntaxhighlight>
{{out}}
<pre>(map)[]
(map)[a = 1,picat = 3,[a,list,of,different,things,[including,lists],3.14159] = 2]
a = 1
b = default value
(map)[b = 2,a = 1,e = 5,h = 8,f = 6,g = 7,d = 4,c = 3]
h = 8
no key 'z'
keys = abcdefgh
values = [1,2,3,4,5,6,7,8]
bdfh</pre>
=={{header|PicoLisp}}==
Line 3,605 ⟶ 4,813:
[http://software-lab.de/doc/refA.html#assoc association lists].
<
(put 'A 'bar 10)
(put 'A 'baz 15)
Line 3,620 ⟶ 4,828:
foo 20
bar 10
baz 15</
=={{header|Pike}}==
Line 3,634 ⟶ 4,842:
''indices()'' and ''values()'' can be used to enumerate the contents
of an existing mapping.
<syntaxhighlight lang="pike">
mapping m = ([ "apple": "fruit", 17: "seventeen" ]);
write("indices: %O\nvalues: %O\n17: %O\n",
Line 3,640 ⟶ 4,848:
values(m),
m[17]);
</syntaxhighlight>
{{Out}}
<pre>
Line 3,656 ⟶ 4,864:
Since any data type can be used nested structures of arbitrary size can
be constructed.
<syntaxhighlight lang="pike">
mapping m2 = ([ "car": ([ "ford":17, "volvo":42 ]) ]);
write("#ford: %O, #volvo: %O\n",
m2->car->ford,
m2["car"]["volvo"]);
</syntaxhighlight>
{{Out}}
<pre>
Line 3,668 ⟶ 4,876:
=={{header|PL/I}}==
<
assocarr: Proc Options(main);
Dcl 1 aa,
Line 3,716 ⟶ 4,924:
End;
End;</
{{out}}
<pre>added >1< -> spam<
Line 3,736 ⟶ 4,944:
The following example code is a "record definition", which has nothing to do with associative arrays:-
<
type ThisIsNotAnAssocArrayType is record (
myShape VARCHAR2(20),
Line 3,749 ⟶ 4,957:
dbms_output.put_line ('assocArray.mySize: ' || assocArray.mySize);
END;
/</
=={{header|Pop11}}==
<
;;; value 0 (default value is returned when the item is absent).
vars ht = newmapping([], 50, 0, true);
Line 3,773 ⟶ 4,981:
printf(value, '%p\t');
printf(key, '%p\n');
endprocedure);</
=={{header|PostScript}}==
<
<</a 100 /b 200 /c 300>>
dup /a get =
</syntaxhighlight>
=={{header|Potion}}==
<
redblue = "purple"
Line 3,789 ⟶ 4,997:
255 == mydictionary("blue")
65280 == mydictionary("green")
16711935 == mydictionary("purple")</
=={{header|PowerShell}}==
An empty hash table can be created with:
<
A hash table can be initialized with key/value pairs:
<
"key1" = "value 1"
key2 = 5 # if the key name has no spaces, no quotes are needed.
}</
Individual values can be assigned or replaced by either using a property-style access method or indexing into the table with the given key:
<
$hashtable['bar'] = 42
$hashtable."a b" = 3.14 # keys can contain spaces, property-style access needs quotation marks, then
$hashtable[5] = 8 # keys don't need to be strings</
NB. PowerShell compares strings as case-insensitive, that means the hashtable keys 'a' and 'A' are considered the same key. This happens when @{} is turned into a hashtable, but can be overridden by an explicit long-form:
<
$h=@{}
$h['a'] = 1
Line 3,824 ⟶ 5,032:
---- -----
A 2
a 1 </
Similarly, values can be retrieved using either syntax:
<
$hashtable['key2'] # 5</
It is common to see a hashtable literal used to create an object, by casting it to a new type:
<
"key1" = "value 1"
key2 = 5
}</
This is a convenience syntax, has less code and runs faster than other ways to create objects.
=={{header|Prolog}}==
We use the facts table for this purpose.
<
mymap(key1,value1).
mymap(key2,value2).
Line 3,843 ⟶ 5,051:
?- mymap(key1,V).
V = value1
</syntaxhighlight>
=={{header|PureBasic}}==
Hashes are a built-in type called Map in Purebasic.
<
dict("country") = "Germany"
Debug dict("country")</
=={{header|Python}}==
Hashes are a built-in type called dictionaries (or mappings) in Python.
<
hash = dict(red="FF0000", green="00FF00", blue="0000FF")
hash = { 'key1':1, 'key2':2, }
value = hash[key]</
Numerous methods exist for the mapping type https://docs.python.org/3/library/stdtypes.html#mapping-types-dict
<
d = {}
d['spam'] = 1
Line 3,881 ⟶ 5,089:
# iterating over (key, value) pairs
for key, value in d.iteritems():
print key, value</
Note: Python dictionary keys can be of any arbitrary "hashable" type. The following contains several distinct key value pairs:
<
(Some other languages such as ''awk'' and ''Perl'' evaluate all keys such that numerically or lexically equivalent expressions become identical entries in the hash or associative array).
Line 3,898 ⟶ 5,106:
=== environment example ===
<
> env[["x"]] <- 123
> env[["x"]]</
<pre>[1] 123</pre>
<
> env[[index]] <- "rainfed hay"
> env[[index]]</
<pre>[1] "rainfed hay"</pre>
<
<pre>[1] "rainfed hay"</pre>
<syntaxhighlight lang
<pre><environment: 0xb7cd560></pre>
<syntaxhighlight lang
<pre><environment: 0xb7cd560></pre>
=== vector example ===
<
> print(x)</
<pre>hello world !
1 2 3</pre>
<syntaxhighlight lang
<pre>[1] "hello" "world" "!"</pre>
<syntaxhighlight lang
<pre>[1] 1 2 3</pre>
=== list example ===
<
> print(a)</
<pre>$a
[1] 1
Line 3,939 ⟶ 5,147:
$d
[1] "xyz"</pre>
<syntaxhighlight lang
<pre>[1] "a" "b" "c" "d"</pre>
<syntaxhighlight lang
<pre>[[1]]
[1] 1
Line 3,957 ⟶ 5,165:
In Racket, hash tables are natively supported and encouraged over association lists in many cases. Data structures that behave like dictionaries support a unified interface.
<
#lang racket
Line 3,971 ⟶ 5,179:
(dict-ref a-list 'a) ; => 5
(dict-ref table 'a) ; => 5
</syntaxhighlight>
=={{header|Raku}}==
Line 3,979 ⟶ 5,187:
The fatarrow, <code>=></code>, is no longer just a quoting comma; it now constructs a <code>Pair</code> object. But you can still define a hash with an ordinary list of even length.
<syntaxhighlight lang="raku"
my %h2 = 'key1', 'val1', 'key-2', 2, 'three', -238.83, 4, 'val3';
Line 4,006 ⟶ 5,214:
class C {};
my %cash{C};
%cash{C.new} = 1;</
=={{header|Raven}}==
<
a_hash print
Line 4,021 ⟶ 5,229:
6.28 a_hash 'c' set # set key 'c'
a_hash.'c' # get key 'c' shorthand
6.28 a_hash:'c' # set key 'c' shorthand</
Null is returned for unknown keys.
Line 4,027 ⟶ 5,235:
=={{header|Relation}}==
<
relation key, value
insert "foo", "bar"
Line 4,036 ⟶ 5,244:
select key == "fruit"
print
</syntaxhighlight>
'''assert''' will show an error, if a key is used twice. However, it not stop the insertion.
Line 4,059 ⟶ 5,267:
=={{header|Retro}}==
<
hashTable constant table
Line 4,066 ⟶ 5,274:
table @" first" putn
table @" second" puts</
=={{header|REXX}}==
===version 1===
Associative arrays are called ''stem variables'' in Rexx.
<
key0 = '0'
Line 4,080 ⟶ 5,288:
Say 'stem.key0= 'stem.key /* Display a value for a key that wasn't set */
Say 'stem.key1= 'stem.key1 /* Display a value for a key that was set */</
{{out}}
<pre>stem.key0= .
Line 4,086 ⟶ 5,294:
===version 2===
<
/*┌────────────────────────────────────────────────────────────────────┐
│ The (below) two REXX statements aren't really necessary, but it │
Line 4,112 ⟶ 5,320:
yyy='RI'
say 'capital of' stateN.yyy "is" stateC.yyy
/*stick a fork in it, we're done.*/</
{{out}}
<pre>
Line 4,121 ⟶ 5,329:
=={{header|Ring}}==
<
# Project Associative array/Creation
Line 4,129 ⟶ 5,337:
see find(myarray,"two",1) + nl
see find(myarray,2,2) + nl
</syntaxhighlight>
Output:
<pre>
Line 4,138 ⟶ 5,346:
=={{header|RLaB}}==
Associative arrays are called ''lists'' in RLaB.
<syntaxhighlight lang="rlab">
x = <<>>; // create an empty list using strings as identifiers.
x.red = strtod("0xff0000"); // RLaB doesn't deal with hexadecimal numbers directly. Thus we
Line 4,164 ⟶ 5,372:
{ x.[i] = i; } // assign to the element of list ''i'' the real value equal to i.
</syntaxhighlight>
=={{header|Ruby}}==
===Hash literals===
Ruby has literal syntax for Hash objects.
A Hash with symbols as keys:
<syntaxhighlight lang="ruby">
{:name => 'Zeus', :planet => 'Jupiter'}
</syntaxhighlight>
Shorthand for symbol keys:
<syntaxhighlight lang="ruby">
{name: 'Zeus', planet: 'Jupiter'}
</syntaxhighlight>
A Hash with keys and values of arbitrary types:
<syntaxhighlight lang="ruby">
{1 => 'two', three: 4}
</syntaxhighlight>
An empty Hash:
<syntaxhighlight lang="ruby">
{}
</syntaxhighlight>
===Customizing the default value===
A Hash object that returns [[nil]] for unknown keys:
<syntaxhighlight lang="ruby">hash = {}
hash[666] = 'devil'
hash[777] # => nil
hash[666] # => 'devil'</
A
<
hash[666] = 'devil'
hash[777] # => 'unknown key'
hash[666] # => 'devil'</
A
<
hash[666] = 'devil'
hash[777] # => 'unknown key 777'
hash[666] # => 'devil'</
A
<
hash[777] # => 'key 777 was added at Sun Apr 03 13:49:57 -0700 2011'
hash[555] # => 'key 555 was added at Sun Apr 03 13:50:01 -0700 2011'
hash[777] # => 'key 777 was added at Sun Apr 03 13:49:57 -0700 2011'</
=={{header|Rust}}==
<
fn main() {
let mut olympic_medals = HashMap::new();
Line 4,200 ⟶ 5,436:
olympic_medals.insert("Germany", (252, 260, 270));
println!("{:?}", olympic_medals);
}</
=={{header|Sather}}==
<
main is
-- creation of a map between strings and integers
Line 4,223 ⟶ 5,459:
end;
end;
</syntaxhighlight>
=={{header|Scala}}==
<
var map = Map(1 -> 2, 3 -> 4, 5 -> 6)
map(3) // 4
map = map + (44 -> 99) // maps are immutable, so we have to assign the result of adding elements
map.isDefinedAt(33) // false
map.isDefinedAt(44) // true</
<
import scala.collection.mutable.HashMap
val hash = new HashMap[Int, Int]
Line 4,242 ⟶ 5,478:
hash.contains(33) // false
hash.isDefinedAt(33) // same as contains
hash.contains(44) // true</
<
hash.foreach {e => println("key "+e._1+" value "+e._2)} // e is a 2 element Tuple
// same with for syntax
for((k,v) <- hash) println("key " + k + " value " + v)</
<
map.filter {k => k._1 > 3} // Map(5 -> 6, 44 -> 99)
// same with for syntax
for((k, v) <- map; if k > 3) yield (k,v)</
=={{header|Scheme}}==
Scheme has association lists (alists), which are inefficient, ordered maps with arbitrary keys and values.
<
(assoc 'a my-dict) ; evaluates to '(a b)</
Hash tables are provided by SRFI-69 [http://srfi.schemers.org/srfi-69/srfi-69.html]. Many Scheme implementation also provide native hash tables.
<
(define my-hash (alist->hash-table my-alist))</
The R6RS standard specifies support for hashtables in the [http://www.r6rs.org/final/html/r6rs-lib/r6rs-lib-Z-H-14.html#node_chap_13 standard libraries] document.
<
(import (rnrs base)
Line 4,276 ⟶ 5,512:
(hashtable-set! my-hash 'a 'b)
(hashtable-set! my-hash 1 'hello)
(hashtable-set! my-hash "c" '(a b c))</
=== A ''persistent'' associative array from scratch ===
{{works with|CHICKEN|5.3.0}}
{{libheader|r7rs}}
{{libheader|srfi-1}}
{{libheader|srfi-151}}
Most implementations of associative arrays—including those for Scheme—are for ‘''mutable''’ arrays, whose previous values are effectively lost whenever an insertion is done. Here instead is a ''persistent'' (‘''immutable''’) implementation, using code from [[AVL_tree#Scheme|the AVL Tree task]]. (So performance will be on average logarithmic. Just be aware of that.)
That there are so many implementations of associative arrays for Scheme is partly because making an implementation from scratch is fairly easy. But many approaches are difficult to use if the goal is ''persistent'' associative arrays. For instance, if you use a classical hash table, inserting an association would require copying an entire array.
Associate arrays are not part of the Scheme language itself, but are compiler/interpreter or library add-ons. So I feel justified in presenting this sketch of yet another library add-on.
<syntaxhighlight lang="scheme">(cond-expand
(r7rs)
(chicken (import r7rs)))
(define-library (avl-trees)
;;
;; This library implements ‘persistent’ (that is, ‘immutable’) AVL
;; trees for R7RS Scheme.
;;
;; References:
;;
;; * Niklaus Wirth, 1976. Algorithms + Data Structures =
;; Programs. Prentice-Hall, Englewood Cliffs, New Jersey.
;;
;; * Niklaus Wirth, 2004. Algorithms and Data Structures. Updated
;; by Fyodor Tkachov, 2014.
;;
;; THIS IS A TRIMMED-DOWN VERSION OF MY SOLUTION TO THE AVL TREES
;; TASK: https://rosettacode.org/wiki/AVL_tree#Scheme
;;
(export avl)
(export avl?)
(export avl-empty?)
(export avl-insert)
(export avl-search-values)
(export avl-check-usage)
(import (scheme base))
(import (scheme case-lambda))
(import (scheme process-context))
(import (scheme write))
(begin
(define-syntax avl-check-usage
(syntax-rules ()
((_ pred msg)
(or pred (usage-error msg)))))
(define-record-type <avl>
(%avl key data bal left right)
avl?
(key %key)
(data %data)
(bal %bal)
(left %left)
(right %right))
(define (avl)
(%avl #f #f #f #f #f))
(define (avl-empty? tree)
(avl-check-usage
(avl? tree)
"avl-empty? expects an AVL tree as argument")
(not (%bal tree)))
(define (avl-search-values pred<? tree key)
;; Return two values: the data matching the key, or #f is the
;; key is not found; and a second value that is either #f or #t,
;; depending on whether the key is found.
(define (search p)
(if (not p)
(values #f #f)
(let ((k (%key p)))
(cond ((pred<? key k) (search (%left p)))
((pred<? k key) (search (%right p)))
(else (values (%data p) #t))))))
(avl-check-usage
(procedure? pred<?)
"avl-search-values expects a procedure as first argument")
(if (avl-empty? tree)
(values #f #f)
(search tree)))
(define (avl-insert pred<? tree key data)
(define (search p fix-balance?)
(cond
((not p)
;; The key was not found. Make a new node and set
;; fix-balance?
(values (%avl key data 0 #f #f) #t))
((pred<? key (%key p))
;; Continue searching.
(let-values (((p1 fix-balance?)
(search (%left p) fix-balance?)))
(cond
((not fix-balance?)
(let ((p^ (%avl (%key p) (%data p) (%bal p)
p1 (%right p))))
(values p^ #f)))
(else
;; A new node has been inserted on the left side.
(case (%bal p)
((1)
(let ((p^ (%avl (%key p) (%data p) 0
p1 (%right p))))
(values p^ #f)))
((0)
(let ((p^ (%avl (%key p) (%data p) -1
p1 (%right p))))
(values p^ fix-balance?)))
((-1)
;; Rebalance.
(case (%bal p1)
((-1)
;; A single LL rotation.
(let* ((p^ (%avl (%key p) (%data p) 0
(%right p1) (%right p)))
(p1^ (%avl (%key p1) (%data p1) 0
(%left p1) p^)))
(values p1^ #f)))
((0 1)
;; A double LR rotation.
(let* ((p2 (%right p1))
(bal2 (%bal p2))
(p^ (%avl (%key p) (%data p)
(- (min bal2 0))
(%right p2) (%right p)))
(p1^ (%avl (%key p1) (%data p1)
(- (max bal2 0))
(%left p1) (%left p2)))
(p2^ (%avl (%key p2) (%data p2) 0
p1^ p^)))
(values p2^ #f)))
(else (internal-error))))
(else (internal-error)))))))
((pred<? (%key p) key)
;; Continue searching.
(let-values (((p1 fix-balance?)
(search (%right p) fix-balance?)))
(cond
((not fix-balance?)
(let ((p^ (%avl (%key p) (%data p) (%bal p)
(%left p) p1)))
(values p^ #f)))
(else
;; A new node has been inserted on the right side.
(case (%bal p)
((-1)
(let ((p^ (%avl (%key p) (%data p) 0
(%left p) p1)))
(values p^ #f)))
((0)
(let ((p^ (%avl (%key p) (%data p) 1
(%left p) p1)))
(values p^ fix-balance?)))
((1)
;; Rebalance.
(case (%bal p1)
((1)
;; A single RR rotation.
(let* ((p^ (%avl (%key p) (%data p) 0
(%left p) (%left p1)))
(p1^ (%avl (%key p1) (%data p1) 0
p^ (%right p1))))
(values p1^ #f)))
((-1 0)
;; A double RL rotation.
(let* ((p2 (%left p1))
(bal2 (%bal p2))
(p^ (%avl (%key p) (%data p)
(- (max bal2 0))
(%left p) (%left p2)))
(p1^ (%avl (%key p1) (%data p1)
(- (min bal2 0))
(%right p2) (%right p1)))
(p2^ (%avl (%key p2) (%data p2) 0
p^ p1^)))
(values p2^ #f)))
(else (internal-error))))
(else (internal-error)))))))
(else
;; The key was found; p is an existing node.
(values (%avl key data (%bal p) (%left p) (%right p))
#f))))
(avl-check-usage
(procedure? pred<?)
"avl-insert expects a procedure as first argument")
(if (avl-empty? tree)
(%avl key data 0 #f #f)
(let-values (((p fix-balance?) (search tree #f)))
p)))
(define (internal-error)
(display "internal error\n" (current-error-port))
(emergency-exit 123))
(define (usage-error msg)
(display "Procedure usage error:\n" (current-error-port))
(display " " (current-error-port))
(display msg (current-error-port))
(newline (current-error-port))
(exit 1))
)) ;; end library (avl-trees)
(define-library (associative-arrays)
;;
;; Persistent associative arrays for R7RS Scheme.
;;
;; The story:
;;
;; An implementation of associative arrays, where keys are compared
;; with an ‘equal to’ predicate, typically has three parts:
;;
;; * a hash function, which converts a key to a hash value; and
;; the hash value either has a ‘less than’ predicate or can be
;; put in a radix tree;
;;
;; * a table keyed by the hash values;
;;
;; * a way to resolve hash value collisions.
;;
;; At one extreme is the association list, which can be viewed as
;; having a hash function that *always* collides. At a nearly
;; opposite extreme are ideal hash trees, which never have
;; collisions, but which, towards that end, require hash values to
;; ‘grow’ on the fly.
;;
;; Perhaps the simplest form of associative array having all three
;; parts is ‘separate chaining’: the hash function generates an
;; integer modulo some table size; the table itself is an array of
;; that size; and collisions are resolved by falling back to an
;; association list.
;;
;; Below I use my solution to the AVL Tree task
;; (https://rosettacode.org/wiki/AVL_tree#Scheme) to implement
;; *persistent* (that is, ‘immutable’) associative arrays. The hash
;; function is whatever you want, as long as it produces (what
;; Scheme regards as) a real number. Hash value collisions are
;; resolved by falling back to association lists.
;;
(export assoc-array)
(export assoc-array?)
(export assoc-array-set)
(export assoc-array-ref)
(import (scheme base))
(import (scheme case-lambda))
(import (scheme write))
(import (avl-trees))
(cond-expand
(chicken (import (only (srfi 1) alist-delete)))
;; Insert whatever you need here for your Scheme.
(else))
(begin
(define-record-type <assoc-array>
(%assoc-array hashfunc pred=? default table)
assoc-array?
(hashfunc %hashfunc)
(pred=? %pred=?)
(default %default)
(table %table))
(define assoc-array
;; Create an associative array.
(case-lambda
((hashfunc)
(let ((pred=? equal?)
(default #f))
(assoc-array hashfunc pred=? default)))
((hashfunc pred=?)
(let ((default #f))
(assoc-array hashfunc pred=? default)))
((hashfunc pred=? default)
(%assoc-array hashfunc pred=? default (avl)))))
(define (assoc-array-set array key data)
;; Produce a new associative array that is the same as the input
;; array except for the given key-data association. The input
;; array is left unchanged (which is why the procedure is called
;; ‘assoc-array-set’ rather than ‘assoc-array-set!’).
(let ((hashfunc (%hashfunc array))
(pred=? (%pred=? array))
(default (%default array))
(table (%table array)))
(let ((hash-value (hashfunc key)))
;; The following could be made more efficient by combining
;; the ‘search’ and ‘insert’ operations for the AVL tree.
(let*-values
(((alst found?) (avl-search-values < table hash-value)))
(cond
(found?
;; Add a new entry to the association list. Removal of
;; any old associations with the key is not strictly
;; necessary, but without it the associative array will
;; grow every time you replace an
;; association. (Alternatively, you could occasionally
;; clean the associative array of shadowed key
;; associations.)
(let* ((alst (alist-delete key alst pred=?))
(alst `((,key . ,data) . ,alst))
(table (avl-insert < table hash-value alst)))
(%assoc-array hashfunc pred=? default table)))
(else
;; Start a new association list.
(let* ((alst `((,key . ,data)))
(table (avl-insert < table hash-value alst)))
(%assoc-array hashfunc pred=? default table))))))))
(define (assoc-array-ref array key)
;; Return the data associated with the key. If the key is not in
;; the table, return the associative array’s default data.
(let* ((hashfunc (%hashfunc array))
(hash-value (hashfunc key)))
(let*-values
(((alst found?)
(avl-search-values < (%table array) hash-value)))
(if found?
(let ((pair (assoc key alst (%pred=? array))))
(if pair
(cdr pair)
(%default array)))
(%default array)))))
)) ;; end library (associative-arrays)
(cond-expand
(DEMONSTRATION
(begin
(import (scheme base))
(import (scheme write))
(import (srfi 151))
(import (associative-arrays))
;; I like SpookyHash, but for this demonstration I shall use the
;; simpler ‘ElfHash’ and define it only for strings. See
;; https://en.wikipedia.org/w/index.php?title=PJW_hash_function&oldid=997863283
(define (hashfunc s)
(let ((n (string-length s))
(h 0))
(do ((i 0 (+ i 1)))
((= i n))
(let* ((ch
;; If the character is outside the 8-bit range,
;; probably I should break it into four bytes, each
;; incorporated separately into the hash. For this
;; demonstration, I shall simply discard the higher
;; bits.
(bitwise-and (char->integer (string-ref s i))
#xFF))
(h^ (+ (arithmetic-shift h 4) ch))
(high^ (bitwise-and h^ #xF0000000)))
(unless (zero? high^)
(set! h^
(bitwise-xor h^ (arithmetic-shift high^ -24))))
(set! h (bitwise-and h^ (bitwise-not high^)))))
h))
(let* ((a1 (assoc-array hashfunc))
(a2 (assoc-array-set a1 "A" #\A))
(a3 (assoc-array-set a2 "B" #x42)) ; ASCII ‘B’.
(a4 (assoc-array-set a3 "C" "C")))
(write (assoc-array-ref a1 "A")) (newline)
(write (assoc-array-ref a1 "B")) (newline)
(write (assoc-array-ref a1 "C")) (newline)
(write (assoc-array-ref a2 "A")) (newline)
(write (assoc-array-ref a2 "B")) (newline)
(write (assoc-array-ref a2 "C")) (newline)
(write (assoc-array-ref a3 "A")) (newline)
(write (assoc-array-ref a3 "B")) (newline)
(write (assoc-array-ref a3 "C")) (newline)
(write (assoc-array-ref a4 "A")) (newline)
(write (assoc-array-ref a4 "B")) (newline)
(write (assoc-array-ref a4 "C")) (newline))
))
(else))</syntaxhighlight>
{{out}}
<pre>$ csc -DDEMONSTRATION -R r7rs -X r7rs associative_array-scheme.scm && ./associative_array-scheme
#f
#f
#f
#\A
#f
#f
#\A
66
#f
#\A
66
"C"</pre>
It is easy [[Associative_array/Iteration#For_persistent_associative_arrays|to add ''generators'']] to this implementation, by which I mean ‘iterators’ that are themselves executable procedures.
(''Afterword''. To be honest, I would not use the term ‘associative array’, because ‘array’ implies uniformly constant time access, which even a traditional hash table generally cannot provide. I would call these things ‘maps’—or, if the word ‘map’ is heavily used for something else [such as Scheme’s '''map''' procedures], then I would call them ‘dictionaries’.)
=={{header|Seed7}}==
Seed7 uses the type [http://seed7.sourceforge.net/manual/types.htm#hash hash] to support associative arrays.
<
# Define hash type
Line 4,325 ⟶ 5,976:
writeln("key: " <& stri <& ", value: " <& number);
end for;
end func;</
=={{header|SenseTalk}}==
Associative arrays in SenseTalk are called property lists, or objects.
<
put an empty property list into emptyPlist2
Line 4,337 ⟶ 5,988:
put "!!!" after the occupation of Einstein
put Einstein
</syntaxhighlight>
{{out}}
<pre>
Line 4,345 ⟶ 5,996:
=={{header|SETL}}==
Associative arrays (referred to in SETL terminology as <i>maps</i>) are implemented as sets whose only members are tuples of length 2. Create such a set:
<
We can then index the set, or map, with the first element of a constituent tuple to return that tuple's second element:
<
{{out}}
<pre>b</pre>
If the map might contain more than one value associated with the same key, we can return the set of them (in this instance a unit set because the keys are in fact unique):
<
{{out}}
<pre>{b}</pre>
=={{header|SETL4}}==
<syntaxhighlight lang="setl4">
* Iterate over key-value pairs of a map
Line 4,381 ⟶ 6,032:
out('next domain entry',next(d)) :s(next)
done
</syntaxhighlight>
=={{header|Sidef}}==
<
key1 => 'value1',
key2 => 'value2',
)
# Add a new key-value pair
hash{:key3} = 'value3'
=={{header|Slate}}==
<
=={{header|Smalltalk}}==
<
states at: 'MI' put: 'Michigan'.
states at: 'MN' put: 'Minnesota'.</
alternative:
<
=={{header|SNOBOL4}}==
<
t<"red"> = "#ff0000"
t<"green"> = "#00ff00"
Line 4,412 ⟶ 6,063:
output = t<"blue">
output = t<"green">
end</
=={{header|SQL}}==
<syntaxhighlight lang="sql">
REM Create a table to associate keys with values
CREATE TABLE associative_array ( KEY_COLUMN VARCHAR2(10), VALUE_COLUMN VARCHAR2(100)); .
Line 4,422 ⟶ 6,073:
REM Retrieve a key value pair
SELECT aa.value_column FROM associative_array aa where aa.key_column = 'KEY';
</syntaxhighlight>
=={{header|SQL PL}}==
{{works with|Db2 LUW}} version 9.7 or higher.
With SQL PL:
<
--#SET TERMINATOR @
Line 4,446 ⟶ 6,097:
CALL DBMS_OUTPUT.PUT_LINE(HASH['5']);
END@
</syntaxhighlight>
Output:
<pre>
Line 4,466 ⟶ 6,117:
=={{header|Stata}}==
<
a=asarray_create()
Line 4,483 ⟶ 6,134:
// End Mata session
end</
=={{header|Swift}}==
<
var a = [String: Int]()
// or
Line 4,498 ⟶ 6,149:
// make a map with a literal
var d = ["foo": 2, "bar": 42, "baz": -1]</
=={{header|Symsyn}}==
Symsyn implements Hash as a list of strings. Each name/value or key/value pair is stored in another string. The name/value pair is in the format 'name=value', the '=' is reserved.
<syntaxhighlight lang="symsyn">
#+ 'name=bob' $hash | add to hash
#? 'name' $hash $S | find 'name' and return 'bob' in $S
#- 'name' $hash | delete 'name=bob' from hash
</syntaxhighlight>
=={{header|Tcl}}==
All arrays in Tcl are associative.
<
set hash(foo) 5
Line 4,526 ⟶ 6,177:
foreach key [array names hash] {
puts $hash($key)
}</
Tcl also provides associative map values (called “dictionaries”) from 8.5 onwards.
<br>
{{works with|Tcl|8.5}}
<
set d [dict create foo 5 bar 10 baz 15]
Line 4,550 ⟶ 6,201:
# Output the whole dictionary (since it is a Tcl value itself)
puts $d</
=={{header|Toka}}==
Toka provides associative arrays via a library.
<
( create an associative array )
Line 4,568 ⟶ 6,219:
( obtain and print the values )
" first" foo asarray.get .
" second" foo asarray.get .</
=={{header|UNIX Shell}}==
{{works with|ksh}}
<
hash=( [key1]=val1 [key2]=val2 )
hash[key3]=val3
echo "${hash[key3]}"</
{{works with|bash}}
assigning values is the same as ksh, but to declare the variable as an associative array:
<syntaxhighlight lang
=={{header|UnixPipes}}==
A key value file can be considered as an associative array
<
function init() {
Line 4,626 ⟶ 6,277:
put c cow
get c
dump</
=={{header|Vala}}==
{{libheader|Gee}}
<
using Gee;
Line 4,648 ⟶ 6,299:
stdout.printf("%d\n", map.get("two"));
}
</syntaxhighlight>
Compile with flag: <pre> --pkg gee-1.0 </pre>
Line 4,655 ⟶ 6,306:
See '''[https://msdn.microsoft.com/en-us/library/x4k5wbx4.aspx here]''' in the MSDN the reference for the Dictionary object that can be used in VBA. The following example shows how to create a dictionary, add/remove keys, change a key or a value, and check the existence of a key.
<
Sub Test()
Dim h As Object
Line 4,670 ⟶ 6,321:
h.RemoveAll
Debug.Print h.Count
End Sub</
=={{header|Vim Script}}==
Dictionary keys are always strings.
<
let dict = {"one": 1, "two": 2}
Line 4,693 ⟶ 6,344:
let one = remove(dict, "one")
unlet dict["two"]
unlet dict.three</
=={{header|Visual FoxPro}}==
Visual FoxPro has a collection class which can be used for this.
<
LOCAL loCol As Collection, k, n, o
CLEAR
Line 4,737 ⟶ 6,388:
ENDPROC
ENDDEFINE
</syntaxhighlight>
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">fn main() {
// make empty map
mut my_map := map[string]int{}
//s et value
my_map['foo'] = 3
// getting values
y1 := my_map['foo']
// remove keys
my_map.delete('foo')
// make map with values
my_map = {
'foo': 2
'bar': 42
'baz': -1
}
}</syntaxhighlight>
=={{header|Wart}}==
<
h 'a
=> 1</
=={{header|Wren}}==
Wren has a Map class built in.
<
fruit[1] = "orange" // associates a key of 1 with "orange"
fruit[2] = "apple" // associates a key of 2 with "apple"
Line 4,763 ⟶ 6,436:
System.print(capitals) // prints all remaining entries
System.print(capitals.count) // prints the number of remaining entries
System.print(capitals["Sweden"]) // prints the entry for Sweden (null as there isn't one)</
{{out}}
Line 4,775 ⟶ 6,448:
null
</pre>
=={{header|XLISP}}==
XLISP refers to associative arrays as tables. The <tt>MAKE-TABLE</tt> function returns a new empty table, for instance:
<
Values can then be inserted using <tt>TABLE-SET!</tt>:
<
(table-set! starlings "Abbot's starling" "Poeoptera femoralis")
(table-set! starlings "Cape starling" "Lamprotornis nitens")</
and retrieved using <tt>TABLE-REF</tt> with their keys:
<
Output in a REPL:
<pre>"Lamprotornis nitens"</pre>
Other functions provided for tables include <tt>MAP-OVER-TABLE-ENTRIES</tt>, which takes a table and a function of two arguments and applies the function to each entry (using the key and value as the two arguments), for instance:
<
Output in a REPL:
<pre>"Abbott's starling (Linnaean name Poeoptera femoralis)"
Line 4,796 ⟶ 6,468:
=={{header|XPL0}}==
<
char Dict(10,10);
int Entries;
Line 4,822 ⟶ 6,494:
ChOut(0, Lookup("beta")); CrLf(0);
ChOut(0, Lookup("omega")); CrLf(0);
]</
For greater speed a hashing algorithm should be used to look up items in
Line 4,835 ⟶ 6,507:
=={{header|zkl}}==
<
D(two:2,three:3,one:1)
zkl: T("one",1, "two",2, "three",3).toDictionary()
D(two:2,three:3,one:1)</
{{omit from|Applesoft BASIC}}
|