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.

Konrad Rudolph
  • 13,059
  • 4
  • 55
  • 75
Sairam
  • 641
  • 1
  • 5
  • 8

4 Answers4

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.

Konrad Rudolph
  • 13,059
  • 4
  • 55
  • 75
  • 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 '10 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 '10 at 01: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 '10 at 09:34
  • 9
    Interestingly, in Ruby 1.9, it is actually impossible to implement the `Hash` class with a hash table, since Ruby 1.9 `Hash`es 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 '12 at 11:46
  • 2
    -1 for subjectivity and personal opinion that distract from otherwise good answer. – hippietrail Jan 09 '13 at 06:15
  • @hippietrail Care to explain? Where did I add subjectivity? And why is personal opinion inherently bad (hint: it isn’t)? – Konrad Rudolph Jan 09 '13 at 08:10
  • 3
    @KonradRudolph: "Poorly named", "correct", "too lazy", "misnomer" - none are objective. While I agree "hash" is imperfect, "dictionary" doesn't seem much better. A dictionary is a list of words with definitions etc. The most neutral, least ambiguous term among the many used for this data structure is "associative array". To me "hash" is a Perlism, "dictionary" is a Pythonism, "object" is a JavaScriptism, and "associative array" is nice and techinical, which could be one way in which to judge "correctness". Otherwise it's just down to each persons' preference and taste, ie "subjective". – hippietrail Jan 09 '13 at 08:23
  • 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](http://xlinux.nist.gov/dads/HTML/dictionary.html) 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 09 '13 at 08:44
  • 3
    @hippietrail To summarise: “hash” is a misnomer because (a) it’s factually incorrect: the structure isn’t a hash (which is something completely different), nor is it even a hash table (see Jörg’s comment). And (b) even if “hash table” *were* correct, there’s no reason (other than laziness) to abbreviate it in a non-canonical fashion. And finally, as you can see in the link I previously posted, a “dictionary” is not quite the same as an associative array (although even I admit to using the two synonymously). – Konrad Rudolph Jan 09 '13 at 08:50
  • 2
    @hippietrail No, "associative array" is even worse than hash ( "array" part is an irrelevant implementation detail). And also PHPism. Mapping or dictionary (it's not a "list of words", it's a mapping from word to definition — see the analogy? You don't read dictionaries by reading everything sequentially, you look up specific words) is correct. – Cat Plus Plus Jan 09 '13 at 08:57
  • Well there's now some good stuff in these comments that would be better off in the answer, even better without the "tone" (-: I will have to look into whether a "national" institute gets to say what's "correct" or "official". Wikipedia also has "associate array" for the page title that includes all these terms, but of course they are not official either. Thanks for the links. I've learned something but I also think the answer would be better if neutral and stated what makes it "correct" or "official". Please also consider improving the Wikipedia article. – hippietrail Jan 09 '13 at 09:57
  • @hippietrail But the answer *does* say that (the comments don’t have any more information than the answer, just rephrased). Re the Wikipedia article: I agree, and I’ve been meaning to do that for a long time but then I want to do it right so I can never find enough time. ;-) – Konrad Rudolph Jan 09 '13 at 10:00
  • 1
    Related: Apparently such data structures were first implemented in SNOBOL, which called them ***tables***: [History of Associative Array?](http://programmers.stackexchange.com/questions/173573) – hippietrail Jan 09 '13 at 11:53
  • 1
    • [Wikipedia had a "naming discussion"](http://en.wikipedia.org/wiki/Talk:Associative_array#Naming_discussion_.28assoc_array_vs._dict_vs._hash_etc.29) for the article on these datatypes back in 2010: • Wikipedia has another article discussing their implementations, differences, and terminology in many programming languages: [Comparison of programming languages (mapping)](http://en.wikipedia.org/wiki/Comparison_of_programming_languages_(mapping)) – hippietrail Jan 09 '13 at 11:57
  • 1
    Though not necessarily, the word "dictionary" in today's world connotes an order. I prefer the term "map" for typical unordered key-value pairs. – nawfal Nov 17 '15 at 11:03
  • @nawfal There’s a difference between everyday usage of a term and technical jargon. In [computer science jargon](https://xlinux.nist.gov/dads/HTML/dictionary.html), this is simply unambiguous: dictionary does *not* indicate order. “Map” is broadly a synonym of this, although the term “map” also has other meanings in computer science which, to make matters worse, overlap to some extent. So using “map” always carries the risk of confusion. – Konrad Rudolph Nov 17 '15 at 11:12
  • @KonradRudolph I certainly get/got your point, just saying if designing an API *now*, map would be more intent revealing. The "map" construct of functional language is less of a distraction for me here. Just personal preferences. Side note: NIST also recognizes other usages like map: https://xlinux.nist.gov/dads/ – nawfal Nov 17 '15 at 11:27
  • "Badly chosen"? Maybe. Conveniently abbreviated in a simple one syllable word that implies the underlying implementation...definitely. "Hash" beats "Dictionary" or "Associative array" anyday. – runrig Feb 26 '16 at 22:45
  • 3
    @runrig I’m sorry but that’s nonsense. You have to balance concerns, and `hash` clearly doesn’t do that. If you want to have a short word, use `dict` or `map`. `hash` almost universally refers to a *hash function* (or its result). It’s definitely a poor name for a data structure. – Konrad Rudolph Feb 27 '16 at 09:39
  • About the only reason to use a hash function is to build a hash table to map values. Just think of "hash" as short for "hash table". Also, I don't like "dict", and "map" almost universally refers to a specific function that will "map" a list of values to another list of values, that has (usually) nothing to do wtih hashing. – runrig Feb 29 '16 at 17:45
  • @runrig “About the only reason to use a hash function is to build a hash table to map values” — No. And even if — they’d still be two different things. If you dislike `dict` and `map` then you’re really not in any position to argue for the much less accurate `hash`. – Konrad Rudolph Feb 29 '16 at 19:49
  • "...then you’re really not in any position to argue..." - I don't see why..."dict" is not a word. Though it's not bad to type, it just doesn't sound as good as "hash". And as the first paragraph of your post implies, let's just say I'm lazy...and less pedantic. – runrig Feb 29 '16 at 22:40
9

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

dan_waterworth
  • 7,287
  • 2
  • 34
  • 45
  • 1
    Hash is also an ADT . HashTable is an implementation of a Hash – Sairam Dec 28 '10 at 08:23
  • 3
    @Sairam I think its far more common for 'hash' to mean a hash function rather than a hash table. – jk. Jan 09 '13 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 '13 at 01: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](https://ruby-doc.org/core-2.2.0/Hash.html). – Sean Burton Mar 13 '18 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.

aufather
  • 4,449
  • 2
  • 26
  • 24
  • Hash is also an ADT. Is there any specific difference between Hash and Dictionary ADT ? – Sairam Dec 28 '10 at 08:22
  • 2
    @Sairam: No, a hash is the output of a certain kind of algorithm (hash function). –  Dec 28 '10 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)

Ross
  • 921
  • 5
  • 13