Implementing a dictionary data structure

Question

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];
SetAttributes[linkedList, HoldAllComplete];
toLinkedList[data_List] := 
  Fold[linkedList, linkedList[], data];
fromLinkedList[ll_linkedList] := 
   List @@ Flatten[ll, Infinity, linkedList];

addToList[ll_, value_] := linkedList[ll, value];
pop[ll_] := Last@ll;
emptyList[] := linkedList[];

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>.

Answer 1

Update: Mathematica version 10 introduced the builtin Association data structure (see tutorial and answer below), which has most important features of dictionaries.

---

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?

Answer 2

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

For more info, see

• Association,
• DataSet (which builds on Association)
• Wolfram guides: Elementary introduction to DataSets and Fast introduction for programmers
• Mathmatica.SE questions: How to make use of Associations and Struct equivalent in Mathematica?
• This HackerNews comment.

Answer 3

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::usage = 
        "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]
dictHasKeyQ[Dictionary[name_,___],key_]:=ValueQ[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"].