What is the difference between a map and a dictionary?

B

BlueRaja - Danny Pflughoeft

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.

Isn't JAVA has both Map and Dictionary? Whats the differences there?

@vivek_jonam: Dictionary in Java is obsolete. It's an abstract class, used before the Map interface was created.

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

"table" is used in lua.

Javascript has a "Map" data structure now too (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/…)

n

nbro

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.

T

Tony Delroy

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"} }.

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

That Oxford CS definition is simply WRONG, because by that definition "dictionary" would merely be a synonym for "set", which it clearly isn't. The distinguishing characteristic of a "dictionary" is that each entry has both a key (subject to set semantics) and an associated value. This corresponds to a conventional natural language dictionary in which each term has a definition

@DavidBooth: I'll address your last sentence first, by pointing out that there's no particular requirement that the usage when discussing "a conventional natural language dictionary" match usage in Computing Science. Which leaves the rest of your sentence as a "The Oxford CS definition is simply wrong" because you don't use or understand the term that way. Hardly convincing. To reasonably argue with such a reference, you need to survey important Comp Sci. textbooks or talks and see how the term has actually been used in that academic context - a survey I hope Oxford did.

My point was not that natural language definitions are the same as CS definitions. Certainly they are not: CS definitions are more precise, though the CS terms are chosen to be evocative of natural language definitions. My point was that the Oxford CS definition is clearly wrong, because by their definition a "dictionary" would be the same as a "set", which it isn't. If you disagree with this then you really must read some CS books on data structures. (I still have some from my BS, MS and PhD degrees in CS, and still remember them quite well.) Hope that clarifies.

@DavidBooth Well, your comments are here for readers to consider. I looked for more confirmation - first textbook I found online was from Stanford - Ullman's Foundations of Computer Science where it says "The dictionary abstract data type is a kind of set, on which particular operations — insert, delete, and lookup — are performed". Examples clearly show dictionaries do not need to have key/value pairs. Until/unless you cite actual definitions from well-regarded texts, I won't be changing my answer.

Technically a dictionary is indeed "a kind of set", because it is a mapping, and a mapping is a set of pairs. But it is very misleading to merely describe a dictionary as a set, because that misses the point of it being a mapping. If a dictionary were MERELY a set, then there would be no point in calling it a dictionary. Ullman himself happens to clarify the meaning of "dictionary" on this slide.

N

Nishit

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.

While this answer is true, the question poster stated: I am not asking for how they are defined in language X or Y. This answer is Java-specific.

P

Paul Nathan

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.

Dictionary in .Net is unordered.

Cocoa dictionaries are also unordered.

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

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

+1. Though dictionaries are unordered in many platforms, the word connotes an order. I like the term map more.

u

user6585083

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.

H

Hank Gay

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

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

O

OscarRyz

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

using Hashtable or a Hash ofter refers to the implementation.

S

SLaks

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

Actually, Hashtable/Hashmap imply a specific implementation in their name (vs. say a balanced tree, which is used in the C++ std::map, for example).

In general, you shouldn't care about the implementation. (Except for performance reasons) Also, that's not always true; look at .Net, for example.

M

MikeT

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

B

Bondo Kalombo

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.

c

cocoakrispies93

I'm in a data structures class right now and my understanding is the dict() data type that can also be initialized as just dictionary = {} or with keys and values, is basically the same as how the list/array data type is used to implement stacks and queues. So, dict() is the type and maps are a resulting data structure you can choose to implement with the dictionary data type in the same way you can use the list type and choose to implement a stack or queue data structure with it.

What is the difference between a map and a dictionary?

Follow WeChat

Want to stay one step ahead of the latest teleworks?

相似问题

Platform

Support

Contact US