Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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. –  Pickett Sep 10 '13 at 19:38

3 Answers 3

up vote 14 down vote accepted

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?

share|improve this answer
    
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

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

share|improve this answer

As of Mathematica v10 the dictionary data structure is built-in.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.