What is the difference between a map and a dictionary?

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.

Two terms for the same thing:

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

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

Some languages use still other terms ("Object" in Javascript, "Hash" in Ruby, "Table" in Lua), but those all have separate meanings in programming too, so I'd avoid them.

See here for more info.

Summary of Computer Science terminology:

• a dictionary is a data structure representing a set of elements, with insertion, deletion, and tests for membership; the elements may be, but are not necessarily, composed of distinct key and value parts

• a map is an associative data structure able to store a set of keys, each associated with one (or sometimes more than one - e.g. C++ multimap) value, with the ability to access and erase existing entries given only the key.

---

Discussion

Answering this question is complicated by programmers having seen the terms given more specific meanings in particular languages or systems they've used, but the question asks for a language agnostic comparison "in theory", which I'm taking to mean in Computing Science terms.

The terminology explained

The Oxford University Dictionary of Computer Science lists:

dictionary any data structure representing a set of elements that can support the insertion and deletion of elements as well as test for membership

• For example, we have a set of elements { A, B, C, D... } that we've been able to insert and could start deleting, and we're able to query "is C present?".

The Computing Science notion of map though is based on the mathematical linguistic term mapping, which the Oxford Dictionary defines as:

mapping An operation that associates each element of a given set (the domain) with one or more elements of a second set (the range).

• As such, a map data structure provides a way to go from elements of a given set - known as "keys" in the map, to one or more elements in the second set - known as the associated "value(s)".
• The "...or more elements in the second set" aspect can be supported by an implementation is two distinct way:
  • Many map implementations enforce uniqueness of the keys and only allow each key to be associated with one value, but that value might be able to be a data structure itself containing many values of a simpler data type, e.g. { {1,{"one", "ichi"}, {2, {"two", "ni"}} } illustrates values consisting of pairs/sets of strings.
  • Other map implementations allow duplicate keys each mapping to the same or different values - which functionally satisfies the "associates...each [key] element...with...more [than one] [value] elements" case. For example, { {1, "one"}, {1, "ichi"}, {2, "two"}, {2, "ni"} }.

Dictionary and map contrasted

So, using the strict Comp Sci terminology above, a dictionary is only a map if the interface happens to support additional operations not required of every dictionary:

• the ability to store elements with distinct key and value components

• the ability to retrieve and erase the value(s) given only the key

A trivial twist:

• a map interface might not directly support a test of whether a {key,value} pair is in the container, which is pedantically a requirement of a dictionary where the elements happen to be {key,value} pairs; a map might not even have a function to test for a key, but at worst you can see if an attempted value-retrieval-by-key succeeds or fails, then if you care you can check if you retrieved an expected value.

Communicate unambiguously to your audience

⚠ Despite all the above, if you use dictionary in the strict Computing Science meaning explained above, don't expect your audience to follow you initially, or be impressed when you share and defend the terminology. The other answers to this question (and their upvotes) show how likely it is that "dictionary" will be synonymous with "map" in the experience of most programmers. Try to pick terminology that will be more widely and unambiguously understood: e.g.

• associative container: any container storing key/value pairs with value-retrieval and erasure by key
• hash map: a hash table implementation of an associative container
• hash set enforcing unique keys: a hash table implementation of a dictionary storing element/values without treating them as containing distinct key/value components, wherein duplicates of the elements can not be inserted
• balance binary tree map supporting duplicate keys: ...

Crossreferencing Comp Sci terminology with specific implementations

C++ Standard Library

• maps: map, multimap, unordered_map, unordered_multimap
• other dictionaries: set, multiset, unordered_set, unordered_multiset
• note: with iterators or std::find you can erase an element and test for membership in array, vector, list, deque etc, but the container interfaces don't directly support that because finding an element is spectacularly inefficient at O(N), in some cases insert/erase is inefficient, and supporting those operations undermines the deliberately limited API the container implies - e.g. deques should only support erase/pop at the front and back and not in terms of some key. Having to do more work in code to orchestrate the search gently encourages the programmer to switch to a container data structure with more efficient searching.

...may add other languages later / feel free to edit in...