# Implementing a dictionary data structure

As one learns from a course on data structures, hash maps or dictionaries can be efficient when applied to appropriate tasks.

I need a hash map in Mathematica and I've never found it. I'm scratching in one of my notebooks files, and I find myself still using the following code (Leonid Shifrin) to simulate this data structure.

ClearAll[linkedList, toLinkedList, fromLinkedList, addToList, pop, emptyList];
List @@ Flatten[ll, Infinity, linkedList];

pop[ll_] := Last@ll;

ClearAll[makeHash];
makeHash[] := Module[{hash},
hash[_] := emptyList[];
hash /: add[hash, key_, value_] := ash[key] = addToList[hash[key], value];
hash /: get[hash, key_] := fromLinkedList@hash[key];
Return[hash]];


I was wondering if any of you had needed a dictionary. If you have, I would like know how you implemented it. I'm interested to use a map<string, int>.

-
Could you give us a formal or semiformal description of the semantics you require for you dictionary data structure? – m_goldberg Sep 8 '13 at 23:56
There's also a prefix tree (trie) which was used to great effect in Boggle. – rcollyer Sep 9 '13 at 13:19
You got it from Leonid Shifrin's answer here. I found it by searching for his name because it uses the same naming convention as his code over here. – C. E. Sep 10 '13 at 19:38

Mathematica has no obvious hash-table structure but what most people forget is, that the DownValues of symbols, which means the simple, always-used function definitions, are implemented using hashing. Therefore, the most straightforward way to create a dictionary from string to integer is by making definitions:

dict["hello"] = 1;
dict["blub"] = 2;


By setting a definition for dict[___] you can create a default rule, when the key is not in the dictionary.

Another thing you should look into is Dispatch, which

generates an optimized dispatch table representation of a list of rules.

There hashing is used too and you can build your dictionary on a list of rules like

{"hello" -> 1, "blub" -> 2, ... }


Indeed, the documentation suggests, that's exactly this what is used to speed up function definitions:

Lists of rules produced by assignments made with = and := are automatically optimized with dispatch tables when appropriate.

As pointed out by Faysal in his comment, please review the following Q&A:

Struct equivalent in Mathematica?

-
Ideas around such a dictionary structure here: mathematica.stackexchange.com/a/999/66 – faysou Sep 9 '13 at 15:31
@FaysalAberkane Thanks, I was looking for exactly this because I was sure I have seen it around here but was unable to find it. I have included the reference in my answer. – halirutan Sep 9 '13 at 19:40
Note that Mathematica 10 has introduced Association, which has most of the important properties of a dictionary data structure. It makes this answer (currently with the most votes) somewhat deprecated. – Jess Riedel Nov 1 '15 at 17:31
@JessRiedel Rather than editing these older answers, consider submitting your own answer. – bbgodfrey Nov 1 '15 at 19:01
@bbgodfrey: In general I agree, but I'd argue that this is a special situation. Several answers have been made unambiguously defunct by an official Mathematica release designed explicitly to provide this functionality, and it can only confuse people to have the now-best answer buried. Given the traffic on these articles, it could literally take years before the correct answer floats to the top. A short edit reflecting the change of affairs ought to be justified. – Jess Riedel Nov 2 '15 at 9:00

Mathematica 10 has introduced Association, which has most of the important properties of a dictionary data structure.

someData = <| "name" -> "Bob", "age" -> 23 |>

In[1]:= someData["name"]
Out[1]= Bob

In[2]:= someData["age"]
Out[2]= 23

In[3]:= someData[[2]]
Out[3]= 23


-

Salvatore Mangano implements a dictionary data structure in his Mathematica Cookbook (ISBN: 978-0-596-52099-1, Copyright 2010 O'Reilly Media, Inc.). According to the copyright, I can share it with you ("answering a question by citing this book and quoting example code," as I am). For the same reasons as Halirutan mentions, more or less, he uses DownValues and relies on it, but as he says, you need more functionality to be able to work with the dictionary data structure efficiently. His functions are surely only meant to be a start, many other languages implement many more such functions. But his is a start to see how it can be done and to build on. I put them into a package. The usage messages are mine, but the code has only been touched to fix what I assume were type setting errors in the book:

BeginPackage["DataDictionary"]

makeDictionary::usage =
"makeDictionary[] initializes a new dictionary and returns an identifier.";
destroyDictionary::usage =
"destroyDictionary[dictionary] destroys a dictionary.";
dictName::usage =
"dictName[dictionary] returns the internal symbol used for storing data in a dictionary.";
dictStore::usage =
"dictStore[dictionary, key, value] stores a value in a dictionary using a key.";
dictReplace::usage =
"dictReplace[dictionary, key, value] works the same way as dictStore except that any duplicates in a dictionary will be removed.";
dictRemove::usage =
"dictRemove[dictionary, key, value] removes a value that is stored in a  dictionary under a key.";
dictLookup::usage =
"dictLookup[dictionary, key] returns all values in a dictionary under a key.";
"dictHasKeyQ[dictionary, key] gives True if key in dictionary has not unset.";
dictKeyEmptyQ::usage =
"dictKeyEmptyQ[dictionary, key] gives True if the value of key in dictionary is an empty list.";
dictKeys::usage =
"dictKeys[dictionary] returns all keys in a dictionary.";
dictKeyValuePairs::usage =
"dictKeyValuePairs[dictionary] returns all key value pairs in a dictionary.";

Begin["Private"]

makeDictionary[]:=Module[{name},
name=Unique["dict"];
Evaluate[name][k_]:={};
Dictionary[name]
]
destroyDictionary[Dictionary[name_,___]]:=If[ValueQ[name[_]],Remove[name];True,False]
dictName[Dictionary[name_,___]]:=name
dictStore[dict_Dictionary,key_,value_]:=Module[{d=dictName[dict]},d[key]=Prepend[d[key],value]]
dictReplace[dict_Dictionary,key_,value_]:=Module[{d=dictName[dict]},d[key]=Union[d[key],{value}]]
dictRemove[dict_Dictionary,key_,value_]:=Module[{d=dictName[dict]},d[key]=Complement[d[key],{value}]]
dictLookup[Dictionary[name_,___],key_]:=name[key]
dictKeyEmptyQ[Dictionary[name_,___],key_]:=name[key]==={}
dictKeys[dict_Dictionary]:=Most[DownValues[Evaluate@dictName[dict]]]/.HoldPattern[a_:>values_List]:>a[[1,1]]
dictKeyValuePairs[dict_Dictionary]:=Most[DownValues[Evaluate[dictName[dict]]]]/.HoldPattern[a_:>values_List]:>{a[[1,1]],values}
Dictionary[name_][prop_] := With[{d = dictLookup[Dictionary[name], prop]}, If[Length@d == 1, First@d, d]]

End[ ]

EndPackage[ ]


A basic example:

sweden = {"Gothenburg", "Stockholm", "Kalmar", "Halmstad"};
unitedstates = {"Clinton", "Terre Haute", "Springfield",
"St. Louis"};
cities = makeDictionary[];
dictStore[cities, "Sweden", #] & /@ sweden;
dictStore[cities, "United States", #] & /@ unitedstates;

dictKeys[cities]


{"Sweden", "United States"}

dictLookup[cities, "United States"]


{"St. Louis", "Springfield", "Terre Haute", "Clinton"}

I've added a shorthand for dictLookup, so that you can retrieve a property easily by just writing dictionary["prop"]`.

-