Dictionary Data Structure

Sometimes called "AssociativeArray", "Map", or "HashTable" (the latter is strictly an implementation of a dictionary). Almost all script languages, including PerlLanguage, RubyLanguage, PythonLanguage, LispLanguage, support some kind of dictionary built-in facility.

In a dictionary, you store a value with an associated key and then you may retrieve this value later using the key. There are a lot of examples. For example, in PerlLanguage you might use the built-in hash capability:

 my %english2latin = (
    sailor  => 'nauta',
    man     => 'vir',
    woman   => 'femina',
 );
 $english2latin{'dog'} = 'canis';

 foreach $key (sort keys %english2latin)
 {
   my $value = $english2latin{$key};
   print "The Latin word for $key is $value.\n";
 }

 outputs:
   The Latin word for dog is canis.
   The Latin word for man is vir.
   The Latin word for sailor is nauta.
   The Latin word for woman is femina.

---

In Smalltalk I could do it like this

| dict |
dict := (IdentityDictionary? new)
add: 'man' -> 'vir';
add: 'woman' -> 'femina';
add: 'sailor' -> 'nauta';
yourself.
dict add: 'dog' -> 'canis'.
dict keys asSortedCollection do: 
[:key | 
Transcript
cr;
show: 'The Latin word for ';
show: key;
show: ' is ';
show: (dict at: key)]

Plenty of more to write, but nevertheless

---

In RDBMS (RelationalDatabase) terms, a dictionary has 2 columns, one of which is a primary (unique) key.

---

In Smalltalk, IdentityDictionary? is a subclass of Dictionary. When should I use one, and when the other?

I just read the answer to my own question. It is was posted a few years ago at http://wiki.squeak.org/squeak/1845 very tersely: "uses == (identity) for accessing. " In the Squeak sources, it is used for things that must exist only once: the classes SystemDictionary? and DynamicBindings?.

Actually the above example can also works fine with a Dictionary, and does not need an IdentityDictionary?.

dict2 := (Dictionary new)
add: 'man' -> 'vir';
add: 'woman' -> 'femina';
add: 'sailor' -> 'nauta';
yourself. 
dict2 add: 'dog' -> 'canis'. 'dog'->'canis'
dict2 keys asSortedCollection do: 
[:key | 
Transcript
cr;
show: 'The Latin word for ';
show: key;
show: ' is ';
show: (dict2 at: key)] 

One difference I spotted from browsing the Squeak sources, is that in the Dictionary, the entries are identified by the Collection>>hash Smalltalk method. However, in the IdentityDictionary?, that is replaced with ProtoObject?>>identityHash, which is a virtual machine primitive.

---

PythonLanguage is based heavily on its dictionaries: every object has an underlying dictionary mapping to its attributes, which may be accessed through the __dict__ attribute.

class ExampleObject?:
spam = "example"

obj = ExampleObject?()
print obj.spam # prints "example"
print obj.__dict__["spam"] # also prints "example"

---

Not to be confused with DataDictionary.

---

CategoryDataStructure