53

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.

Improve this question
0

4 Answers 4

Reset to default
101

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:

  1. the keys have to be hashable and equality comparable.
  2. the entries appear in no particular order in the dictionary.

(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.

Improve this answer
22
  • 4
    To give an example in C++, the standard associative container templates couldn't be implemented as hashes, although the next standard will have what are effectively hash tables. They're called unordered_map to show what they do rather than what they are.
    – David Thornley
    Dec 28, 2010 at 16:10
  • 6
    “correct” according to what authority? In some languages, such as Ruby and Perl, the official—read “correct”—name for these structures is “hash”.
    – nohat
    Dec 29, 2010 at 1:43
  • 11
    @nohat: Notice my use of quotes. Furthermore, I have explained why the name is badly chosen, haven’t I? So if you require an authority then I’ll say that it’s by the authority of the theoretical computer science police.
    – Konrad Rudolph
    Dec 29, 2010 at 9:34
  • 9
    Interestingly, in Ruby 1.9, it is actually impossible to implement the Hash class with a hash table, since Ruby 1.9 Hashes preserve the insertion order while a hash table does not. So, in Ruby 1.9, the name Hash doesn't even reflect the implementation any more.
    – Jörg W Mittag
    May 21, 2012 at 11:46
  • 8
    @hippietrail You’re wrong – first, those are objective descriptions. After all, I qualify why the naming is poor and a misnomer (see below). “too lazy” is artistic license on my part but the point remains that the reason to shorten the name is intrinsic, i.e. there’s no reason to use a short name here other than to shorten the name. And you are wrong about “dictionary”: that is simply the official name of the data structure. Your definition of “dictionary” is wrong in the context of computer science, and the name predates Python by decades.
    – Konrad Rudolph
    Jan 9, 2013 at 8:44
9

"Dictionary" is the name of the concept. A hashtable is a possible implementation.

Improve this answer
4
  • 1
    Hash is also an ADT . HashTable is an implementation of a Hash
    – Sairam
    Dec 28, 2010 at 8:23
  • 3
    @Sairam I think its far more common for 'hash' to mean a hash function rather than a hash table.
    – jk.
    Jan 9, 2013 at 13:04
  • @jk Actually the "hash" is the result of applying a "hash function/algorithm" to some input. An "hash table" or "hash map" omehoe relates and hashable object to some object (object in a generic form, not limited to OOP)
    – johannes
    Feb 24, 2013 at 1:02
  • There are languages that use 'Hash' to refer to a dictionary-type structure rather than just to the hash function operation. Ruby, for example.
    – Sean Burton
    Mar 13, 2018 at 17:15
7

A dictionary is the collective term given for any data structure implementation used for fast lookups/insertions. This can be achieved/implemented using a variety of data structures like hash table, skip lists, rb tree etc. A hash table is a specific data structure useful for many purposes including implementing a dictionary.

Improve this answer
2
  • Hash is also an ADT. Is there any specific difference between Hash and Dictionary ADT ?
    – Sairam
    Dec 28, 2010 at 8:22
  • 2
    @Sairam: No, a hash is the output of a certain kind of algorithm (hash function).
    – user7043
    Dec 28, 2010 at 13:22
6

A dictionary uses a key to reference the value directly inside of an associative array.

i.e (KEY => VALUE)

A hash is more often described as a hash table which uses a hash function to calculate the position in memory (or more easily an array) where the value will be. The hash will take the KEY as input and give a value as output. Then plug that value into the memory or array index.

i.e KEY => HASH FUNCTION => VALUE

I guess one is direct while the other isn't. Hash functions may not be perfect either and may sometimes provide an index referencing the wrong value. But that can be corrected.

Best place to look: Wikipedia (associative array and hash table)

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.