What is the difference between Hash
and Dictionary
?
Coming from a scripting background, I feel that they are similar, but I wanted to find out the exact differences. Googling did not help me much.
data structuresdictionarydifferencehashinghashtable
What is the difference between Hash
and Dictionary
?
Coming from a scripting background, I feel that they are similar, but I wanted to find out the exact differences. Googling did not help me much.
Best Answer
Hash
is an extremely poorly named data structure where the programmer has confused the interface with implementation (and was too lazy to write the full name, i.e.HashTable
instead resorting to an abbreviation,Hash
).Dictionary
is the “correct” name of the interface (= the ADT), i.e. an associative container that maps (usually unique) keys to (not necessarily unique) values.A hash table is one possible implementation of such a dictionary that provides quite good access characteristics (in terms of runtime) and is therefore often the default implementation.
Such an implementation has two important properties:
(For a key to be hashable means that we can compute a numeric value from a key which is subsequently used as an index in an array.)
There exist alternative implementations of the dictionary data structure that impose an ordering on the keys – this is often called a sorted dictionary (and is usually implemented in terms of a search tree, though other efficient implementations exist).
To summarize: a dictionary is an ADT that maps keys to values. There are several possible implementations of this ADT, of which the hash table is one.
Hash
is a misnomer but in context it’s equivalent to a dictionary that is implemented in terms of a hash table.