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

EditText of this page (last edited June 18, 2013) or FindPage with title or text search