CODEWITHSUNDEEP
powershelldictionary
Shaun Luttin
Shaun Luttin

Reputation: 141622

What formally differentiates a hash table from a dictionary?

What differentiates them generally?

According to Wikipedia, a dictionary is synonymous with an associative array.

According to Wikipedia, a hash table is a common way to implement a dictionary. Another implementation is a binary search tree.

From that, it seems dictionary is to human as hash table is to female and binary search tree is to male, or dictionary is to pasta as hash table is to radiatori and binary search tree is to spaghetti.

dictionary     :: hash table     :: binary search tree
human          :: male           :: female
pasta          :: radiatori      :: spaghetti

What confuses the issue is that documentation sometimes calls for a dictionary as an argument. The PowerShell documentation (as one of many examples) says,

Enter a hash table or dictionary.

Does that just mean "enter a hash table or any other implementation of dictionary" or are they actually asking for a concrete type known as dictionary? If it's the latter, then what differentiates the concrete type hash table from the concrete type dictionary?

Upvotes: 1

Views: 369

Answers (2)

Armen Michaeli
Armen Michaeli

Reputation: 9150

One can make the argument that a dictionary is an abstract data type (ADT), while a hash table, like you yourself implied through quoting your sources, is a concrete implementation of the dictionary type, same as a binary search tree is. A dictionary simply lets you relate keys to values, it is an interface. An interface does not define implementation. Many classes can implement the same interface, principally differently. On a machine where cost of memory access and data comparison is negligible compared to cost of executing a given hash function, a dictionary implemented through simple linear iteration over keys, may be a better option than a hash table. Especially for smaller dictionary sizes.

The dictionary interface, or ADT, is a set of function signatures -- get value with a given key, enumerate keys and/or values, obtain amount of keys/values. Classes are then designed that implement the interface by providing the actual functions that match these signatures.

Powershell seems to (mostly) agree with this line of reasoning -- naturally, hash tables being actual objects, they are of a (non-abstract) class. Specifically, the System.Collections.HashTable class. This class declares to implement the System.Collections.IDictionary interface.

Interestingly enough, however, Powershell does have a concrete "generic" dictionary class -- System.Collections.Generic.Dictionary<TKey,TValue>. No mechanism seems to be hinted at for this dictionary class. There are other similar "generic" classes that differentiate between one another based on factors like whether mutating the dictionary is allowed (at runtime), whether the dictionary is "sorted", etc. But they too, do not hint at how e.g. value lookup is actually done, to name one thing.

Whether any of these more "generic" dictionary implementations would satisfy a purist of sorts, is debatable, but again one might think that System.Collections.Generic.Dictionary<TKey, TValue> is made for cases where application designer does not want or need to bother with how their dictionaries are implemented. The class is effectively a "type alias" for this or the other type of dictionary class, like a hash table, a binary tree or something else entirely, without disclosing which. I am not sure why .NET designers wouldn't just leave it at aliasing with using Dictionary = System.Collections.HashTable instead, though.

Upvotes: 1

briantist
briantist

Reputation: 47832

I would say don't get too hung up on dictionary definitions of the terms.

If we focus on the classes, [System.Collections.Generic.Dictionary] and [System.Collections.Hashtable] it should help.

You can see that both classes implement the IDictionary interface, which might only be more confusing to your question, but that is likely the key to what makes it easy for a parameter to take either one (it can probably take any object which implements that interface).

When they say it takes a Dictionary they probably mean it accepts [IDictionary].

You can also see that these classes are implemented a bit differently. [Dictionary] is templated for the key and the value, and that's not typical in PowerShell which is probably why you don't see it that often.

Upvotes: 2

Related Questions