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