地图和字典有什么区别？
我知道映射是一种将键映射到值的数据结构。字典不也是一样吗？地图和字典有什么区别1？
<子> 1.我不是问它们在X或Y语言中是如何定义的（这似乎是人们通常在这里问的问题），我想知道它们在理论上有什么区别。
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（12）
同一事物的两个术语：
“Map”是正确的数学术语，但应避免使用它，因为它在 函数式编程。
有些语言还使用其他术语（Javascript 中的“对象”、Ruby 中的“哈希”、Lua 中的“表”），但这些术语在编程中也有不同的含义，因此我会避免使用它们。
请参阅此处了解更多信息。
Two terms for the same thing:
"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.
计算机科学术语摘要：
字典是一种表示一组元素的数据结构，其中插入、删除和成员资格测试；元素可能（但不一定）由不同的键和值部分组成
地图是一种关联数据结构，能够存储一组键，每个键与一个（或有时多个 - 例如C++ multimap）值关联，能够访问和删除仅给定密钥的现有条目。
讨论
回答这个问题很复杂，因为程序员已经看到这些术语在他们使用的特定语言或系统中被赋予了更具体的含义，但这个问题要求“理论上”进行与语言无关的比较，我的意思是 用计算科学术语。
术语解释
牛津大学计算机科学词典列出了
map 的计算科学概念是基于数学语言术语 mapping，牛津词典将其定义为：
字典和地图对比
因此，使用上面严格的计算机科学术语，如果接口恰好支持并非每个字典都需要的其他操作，则字典只是一个地图：
能够存储具有不同键和值组件的元素
检索和擦除值的能力(s) 仅给出密钥
一个简单的变化：
与您的受众明确沟通
⚠尽管有上述所有内容，如果您在上面解释的严格的计算科学含义中使用字典，不要指望您的受众最初会关注您，或者在您分享和辩护时留下深刻的印象术语。这个问题的其他答案（以及他们的赞成票）表明，在大多数程序员的经验中，“字典”与“地图”同义的可能性有多大。尝试选择更广泛、更明确理解的术语：例如
交叉引用 Comp Sci 术语与特定实现
C++ 标准库
地图，多重映射、unordered_map、unordered_multimap设置，multiset,unordered_set，unordered_multisetstd::find您可以删除元素并测试数组，矢量，列表、deque等，但是容器接口不直接支持这一点，因为查找元素的 O(N) 效率非常低，在某些情况下插入/擦除效率低，并且支持这些操作破坏了容器隐含的故意限制的 API - 例如deques 应该只支持前面和后面的擦除/弹出，而不是某些键。必须在代码中做更多工作来编排搜索，这会鼓励程序员切换到具有更高效搜索的容器数据结构。...稍后可能会添加其他语言/随意编辑...
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:
The Computing Science notion of map though is based on the mathematical linguistic term mapping, which the Oxford Dictionary defines as:
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:
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.
Crossreferencing Comp Sci terminology with specific implementations
C++ Standard Library
map,multimap,unordered_map,unordered_multimapset,multiset,unordered_set,unordered_multisetstd::findyou can erase an element and test for membership inarray,vector,list,dequeetc, 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...
一个是另一个的旧术语。通常，术语“字典”是在数学术语“地图”出现之前使用的。此外，字典往往有一个字符串类型的键，但这并不是 100% 到处都是。
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.
我的2分钱。
Dictionary 是 Java 中的抽象类，而 Map 是一个接口。由于Java不支持多重继承，如果一个类扩展了Dictionary，它就不能扩展任何其他类。
因此，引入了Map接口。
Dictionary 类已过时，首选使用 Map。
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.
通常我假设映射由哈希表支持；它意味着无序存储。
字典意味着有序的存储。
有一个基于树的字典，称为 Trie。
在 Lisp 中，它可能看起来像这样：
其中封装了单词：
从顶部到叶子的遍历会产生一个单词。
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:
Which encapsulates the words:
The traversal from the top to the leaf yields a word.
不是同一件事。地图是字典的子集。字典在此处定义为具有插入、删除和查找功能。 Java 使用的 Map（根据 this）是一个字典要求映射到值的键严格映射为一对一函数。字典可能有多个键映射到一个值，或者一个键映射到多个值（如哈希表中的链接），例如 Twitter 主题标签搜索。
作为一个更“现实世界”的例子，在字典中查找一个单词可以为我们提供同一个单词的多个定义，并且当我们找到一个将我们指向另一个条目（查看其他单词）的条目时，许多单词对于相同的定义列表。在现实世界中，地图要广泛得多，使我们能够拥有名称的位置或坐标的名称，而且我们还可以找到最近的邻居或其他属性（人口等），因此恕我直言，可能会有争论更大程度地扩展映射类型可能具有基于图的实现，但最好始终假设仅键值对，特别是因为该值的最近邻居和其他属性都可能只是该值的数据成员。
尽管有一对一的要求，但如果值被概括为集合本身，或者如果值仅仅是对存储在其他地方的集合的引用，则 java 映射可以实现更像广义字典的东西。
请记住，Java 维护者不是 ADT 定义的维护者，并且 Java 决策是专门针对 Java 的。
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.
这个概念的其他术语相当常见：关联数组和散列。
Other terms for this concept that are fairly common: associative array and hash.
是的，它们是相同的，您可以添加“关联数组”。
使用
Hashtable或Hash通常指的是实现。Yes, they are the same, you may add "Associative Array" to the mix.
using
Hashtableor aHashofter refers to the implementation.这是同一概念的两个不同术语。
Hashtable和HashMap也指的是相同的概念。These are two different terms for the same concept.
HashtableandHashMapalso refer to the same concept.所以在纯粹的理论层面上。
字典是可用于定位链接值的值。
映射是一个值，它提供有关如何定位另一个值的说明。
所有允许非线性访问（即仅获取第一个或获取最后一个）的集合都是映射，因为即使是简单的数组也具有映射到正确值的索引。因此，虽然字典是地图的一种类型，但地图的可能功能范围更广。
在实践中，它通常是定义名称的映射函数，因此 HashMap 是一种映射数据结构，它使用哈希算法将键链接到值，而字典不指定键如何链接到值so 可以通过链表、树或任何其他算法来存储。从使用端来看，您通常不关心算法是什么，只关心它们起作用，因此您使用通用字典，并且仅在需要执行算法类型时才转移到其他结构之一
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
主要区别在于Map要求所有条目（值和键对）都有唯一的键。如果发生冲突，即当新条目与集合中已有的条目具有相同的键时，则需要进行冲突处理。
通常，我们使用单独链接来处理冲突。或线性探测。
字典允许多个条目链接到同一个键。
当映射实现了分离链接时，它往往类似于字典。
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.
我现在在数据结构课上，我的理解是 dict() 数据类型也可以初始化为字典 = {} 或使用键和值，基本上与列表/数组数据类型相同用于实现栈和队列。因此，dict() 是类型，map 是结果数据结构，您可以选择使用字典数据类型来实现，就像您可以使用列表类型并选择用它来实现堆栈或队列数据结构一样。
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.