What is the difference between a map and a dictionary?



I know a map is a data structure that maps keys to values. Isn't a dictionary the same? What is the difference between a map and a dictionary1?

1. I am not asking for how they are defined in language X or Y (which seems to be what generally people are asking here on SO), I want to know what is their difference in theory.

devoured elysium

Posted 2010-05-21T17:12:30.970

Reputation: 38 060



Two terms for the same thing:

  • "Map" is used by Java, C++
  • "Dictionary" is used by .Net, Python
  • "Associative array" is used by JavaScript, PHP

"Map" is the correct mathematical term, but it is avoided because it has a separate meaning in functional programming.

See here.

BlueRaja - Danny Pflughoeft

Posted 2010-05-21T17:12:30.970

Reputation: 57 213

4Isn't JAVA has both Map and Dictionary? Whats the differences there? – vivek_jonam – 2012-12-20T14:31:04.367

20@vivek_jonam: Dictionary in Java is obsolete. It's an abstract class, used before the Map interface was created. – BlueRaja - Danny Pflughoeft – 2012-12-20T16:00:09.017

4I know the question is language agnostic, so this is the right answer, but I ended up here looking for the reason Java had both, so this comment was really the perfect thing for me. – GrandOpener – 2014-09-01T20:04:07.963

1"table" is used in lua. – Deduplicator – 2015-06-19T16:36:32.270

it's also somewhat confusingly called "Object" in JSON (for historical reasons related to JavaScript) – Aprillion – 2015-10-09T13:17:54.670

It's called 'Object' for both JSON and JavaScript. There is no such thing as 'associative arrays' in JS. If you used named index for JS array, it get redefined as an JS 'Object' – Dan – 2016-08-29T02:42:37.733

Perl used to use "associative array" before migrating to the more succinct "hash." The leaking of implementation (vs. using an abstraction) avoids collision with the map function. – Michael Carman – 2018-11-29T14:49:53.127


One is an older term for the other. Typically the term "dictionary" was used before the mathematical term "map" took hold. Also, dictionaries tend to have a key type of string, but that's not 100% true everywhere.

Edwin Buck

Posted 2010-05-21T17:12:30.970

Reputation: 55 423


My 2 cents.

Dictionary is an abstract class in Java whereas Map is an interface. Since, Java does not support multiple inheritances, if a class extends Dictionary, it cannot extend any other class.

Therefore, the Map interface was introduced.

Dictionary class is obsolete and use of Map is preferred.


Posted 2010-05-21T17:12:30.970

Reputation: 418


Typically I assume that a map is backed by a hash table; it connotes an unordered store. Dictionaries connote an ordered store.

There is a tree-based dictionary called a Trie.

In Lisp, it might look like this:

(a (n (d t)) n d )

Which encapsulates the words:

  • a
  • and
  • ant
  • an
  • ad

The traversal from the top to the leaf yields a word.

Paul Nathan

Posted 2010-05-21T17:12:30.970

Reputation: 27 992

4Dictionary in .Net is unordered. – BlueRaja - Danny Pflughoeft – 2010-05-21T17:35:33.810

2Cocoa dictionaries are also unordered. – Ken – 2010-05-21T18:11:33.027

C++ std::map is ordered it's implementation is not specified in the standard, the std::unordered_map was introduced in c++11, it is implemented via a hash – Harald Scheirich – 2014-12-30T19:42:01.493

2@HaraldScheirich - While the C++ standard doesn't specifically say "thou shalt use a red-black tree to implement std::map", try using anything else. An AVL tree won't work; it's insertion costs don't meet the standard. A hash won't work; a hash is unordered and hence doesn't meet the standard. The standard pretty much says "thou shalt use a red-black tree to implement std::map" without saying so explicitly. – David Hammen – 2015-03-19T14:16:24.467

+1. Though dictionaries are unordered in many platforms, the word connotes an order. I like the term map more. – nawfal – 2015-11-17T09:43:58.717


Yes, they are the same, you may add "Associative Array" to the mix.

using Hashtable or a Hash ofter refers to the implementation.


Posted 2010-05-21T17:12:30.970

Reputation: 140 471


so on a purely theoretical level.

A Dictionary is a value that can be used to locate a Linked Value. A Map is a Value that provides instructions on how to locate another values

all collections that allow non linear access (ie only get first or get last) are a Map, as even a simple Array has an index that maps to the correct value. So while a Dictionary is a Type of map, maps are a much broader range of possible function.

In Practice a its usually the mapping function that defines the name, so a HashMap is a mapped data structure that uses a hashing algorithm to link the key to the value, where as a Dictionary doesn't specify how the keys are linked to a value so could be stored via a linked list, tree or any other algorithm. from the usage end you usually don't care what the algorithm only that they work so you use a generic dictionary and only shift to one of the other structures only when you need to enfore the type of algorithm


Posted 2010-05-21T17:12:30.970

Reputation: 3 285


Not really the same thing. Maps are a subset of dictionary. Dictionary is defined here as having the insert, delete, and find functions. Map as used by Java (according to this) is a dictionary with the requirement that keys mapping to values are strictly mapped as a one-to-one function. A dictionary might have more than one key map to one value, or one key map to several values (like chaining in a hasthtable), eg Twitter hashtag searches.

As a more "real world" example, looking up a word in a dictionary can give us a number of definitions for the same word, and when we find an entry that points us to another entry (see other word), a number of words for the same list of definitions. In the real world, maps are much broader, allowing us to have locations for names or names for coordinates, but also we can find a nearest neighbor or other attributes (populations, etc), so IMHO there could be argument for a greater expansion of the map type to possibly have graph based implementations, but it would be best to always assume just the key-value pair, especially since nearest neighbor and other attributes to the value could all just be data members of the value.

java maps, despite the one-to-one requirement, can implement something more like a generalized dictionary if the value is generalized as a collection itself, or if the values are merely references to collections stored elsewhere.

Remember that Java maintainers are not the maintainers of ADT definitions, and that Java decisions are specifically for Java.


Posted 2010-05-21T17:12:30.970

Reputation: 11


Other terms for this concept that are fairly common: associative array and hash.

Hank Gay

Posted 2010-05-21T17:12:30.970

Reputation: 51 460

1Hash is nothing to do with this. It's a method of quickly detecting whether objects are different. You are thinking of a hashmap, which uses a hash to do the Map/Dictionary job. – DJClayworth – 2011-07-20T14:51:55.683


@DJClayworth No, many programming languages actually call these things hashes. See Ruby. I didn't design it, and I wouldn't call it that, but don't shoot the messenger.

– Hank Gay – 2011-07-21T13:20:50.430


The main difference is that a Map, requires that all entries(value & key pair) have a unique key. If collisions occur, i.e. when a new entry has the same key as an entry already in the collection, then collision handling is required.

Usually, we handle collisions using either Separate Chaining. Or Linear Probing.

A Dictionary allows for multiple entries to be linked to the same key.

When a Map has implemented Separate Chaining, then it tends to resemble a Dictionary.

Bondo Kalombo

Posted 2010-05-21T17:12:30.970

Reputation: 1


These are two different terms for the same concept.
Hashtable and HashMap also refer to the same concept.


Posted 2010-05-21T17:12:30.970

Reputation: 672 943

3Actually, Hashtable/Hashmap imply a specific implementation in their name (vs. say a balanced tree, which is used in the C++ std::map, for example). – Joe – 2010-05-21T17:20:44.237

In general, you shouldn't care about the implementation. (Except for performance reasons) Also, that's not always true; look at .Net, for example. – SLaks – 2010-05-21T17:25:08.577