Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

What is the difference between Hash and Dictionary. Coming from a scripting background, I feel that they are similar , but wanted to find out the exact differences, Googling did not help me much.

share|improve this question
2  
"Hash" that answered your question? :) sorry for the awful pun... –  Darknight Dec 29 '10 at 14:35
    
See also Stack Overflow: What is the difference between a Map and a Dictionary? –  hippietrail Jan 9 '13 at 10:50
    
See also Computer Science SE: Relation and difference between associative array and hashing table? –  hippietrail Jan 9 '13 at 10:51

4 Answers 4

up vote 46 down vote accepted

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.

share|improve this answer
3  
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
2  
“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 1:43
5  
@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 9:34
3  
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 '12 at 11:46
4  
@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 '13 at 8:44

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.

share|improve this answer
    
Hash is also an ADT. Is there any specific difference between Hash and Dictionary ADT ? –  Sairam Dec 28 '10 at 8:22
1  
@Sairam: No, a hash is the output of a certain kind of algorithm (hash function). –  delnan Dec 28 '10 at 13:22

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

share|improve this answer
1  
Hash is also an ADT . HashTable is an implementation of a Hash –  Sairam Dec 28 '10 at 8:23
    
@Sairam I think its far more common for 'hash' to mean a hash function rather than a hash table. –  jk. Jan 9 '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 1:02

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)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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