239

我知道映射是将键映射到值的数据结构。字典不一样吗？地图和字典1有什么区别？

1.我不是在问它们是如何用语言 X 或 Y 定义的（这似乎是人们在 SO 上通常所问的），我想知道它们在理论上有什么区别。

4

12 回答 12

313

同一事物的两个术语：

  • “Map”被Java、C++使用
  • .Net、Python 使用“字典”
  • PHP使用“关联数组”

“映射”是正确的数学术语，但由于它在函数式编程中具有单独的含义而被避免使用。

有些语言还使用其他术语（Javascript 中的“Object”，Ruby 中的“Hash”，Lua 中的“Table”），但这些在编程中也有不同的含义，所以我会避免使用它们。

请参阅此处了解更多信息。

于 2010-05-21T17:30:37.800 回答
21

一个是另一个的旧术语。通常在数学术语“地图”出现之前使用术语“字典”。此外，字典往往有一个键类型的字符串，但这并不是在任何地方都 100% 正确。

于 2010-05-21T17:14:52.307 回答
18

计算机科学术语摘要：

  • 字典是表示一组元素的数据结构，具有插入、删除和成员资格测试；元素可能但不一定由不同的键和值部分组成

  • 映射是一种关联数据结构，能够存储一组键，每个键与一个（或有时多个 - 例如 C++ 多映射）值相关联，并且能够访问和擦除仅给定键的现有条目。

讨论

回答这个问题很复杂，因为程序员已经看到在他们使用的特定语言或系统中赋予了更具体含义的术语，但这个问题要求“理论上”进行语言不可知的比较，我在计算科学术语中的意思是.

术语解释

牛津大学计算机科学词典列出：

字典表示一组元素的任何数据结构，可以支持元素的插入和删除以及成员资格测试

  • 例如，我们有一组元素 { A, B, C, D... }，我们可以插入并开始删除，我们可以查询“C 是否存在？” .

计算科学的地图概念虽然基于数学语言术语映射，但牛津词典将其定义为：

映射将给定集合（域）的每个元素与第二个集合（范围）的一个或多个元素相关联的操作。

  • 因此，映射数据结构提供了一种从给定集合的元素（称为映射中的“键”）到第二集合中的一个或多个元素（称为关联的“值”）的方法。
  • 实现可以支持“...或第二组中的更多元素”方面有两种不同的 方式：
    • 许多映射实现强制键的唯一性并且只允许每个键与一个值相关联，但该值本身可能是包含许多更简单数据类型的值的数据结构，例如 { {1,{"one" , "ichi"}, {2, {"two", "ni"}} } 说明由字符串对/集合组成的值。
    • 其他映射实现允许重复的键，每个映射到相同或不同的值 - 这在功能上满足“关联...每个 [key] 元素...与...多个 [多于一个] [value] 元素”的情况。例如，{ {1, "one"}, {1, "ichi"}, {2, "two"}, {2, "ni"} }。

字典和地图对比

因此，使用上面严格的 Comp Sci 术语，如果接口碰巧支持并非每个字典都需要的附加操作，则字典只是一个映射：

  • 存储具有不同键和值组件的元素的能力

  • 仅给定键即可检索和擦除值的能力

一个微不足道的转折：

  • map 接口可能不直接支持测试 {key,value} 对是否在容器中，这在元素恰好是 {key,value} 对的字典中是迂腐的要求；地图甚至可能没有测试键的功能，但在最坏的情况下，您可以查看尝试的键值检索是成功还是失败，然后如果您关心您可以检查您是否检索了预期值。

明确地与您的听众交流

⚠ 尽管如此，如果你在上面解释的严格的计算科学含义中使用字典，不要指望你的听众最初会关注你，或者在你分享和捍卫术语时留下深刻的印象。这个问题的其他答案（以及他们的赞成票）表明，在大多数程序员的经验中， “字典”与“地图”同义的可能性有多大。尝试选择更广泛、更明确的术语：例如

  • 关联容器：任何存储键/值对的容器，具有值检索和键擦除
  • 哈希映射：关联容器的哈希表实现
  • 强制唯一键的哈希集：存储元素/值的字典的哈希表实现，而不将它们视为包含不同的键/值组件，其中元素的重复项不能插入
  • 支持重复键的平衡二叉树映射：...

交叉引用具有特定实现的 Comp Sci 术语

C++ 标准库

  • 地图：map, multimap, unordered_map,unordered_multimap
  • 其他词典：set, multiset, unordered_set,unordered_multiset
  • 注意：使用迭代器，或者std::find您可以擦除元素并测试 , , 等中的成员资格array，vector但list容器deque接口不直接支持这一点，因为在 O(N) 时查找元素的效率非常低，在某些情况下插入/擦除是效率低下，并且支持这些操作破坏了容器所暗示的故意限制的 API - 例如deque，s 应该只支持前后的擦除/弹出，而不是某些键。不得不在代码中做更多的工作来编排搜索，这会温和地鼓励程序员切换到具有更高效搜索的容器数据结构。

...以后可能会添加其他语言/随时编辑...

于 2019-05-17T02:37:53.137 回答
14

我的 2 美分。

Dictionary 是 Java 中的一个抽象类，而 Map 是一个接口。因为，Java 不支持多重继承，如果一个类扩展 Dictionary，它不能扩展任何其他类。

因此，引入了 Map 接口。

Dictionary 类已过时，首选使用 Map。

于 2014-11-04T06:41:49.003 回答
3

通常我假设一个映射是由一个哈希表支持的。它意味着一个无序的商店。字典意味着有序的商店。

有一个基于树的字典，称为Trie。

在 Lisp 中，它可能看起来像这样：

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

其中封装了这些词：

  • 一个
  • 和
  • 蚂蚁
  • 一个
  • 广告

从顶部到叶子的遍历产生了一个单词。

于 2010-05-21T17:19:20.377 回答
2

真的不是一回事。地图是字典的子集。字典在这里定义为具有插入、删除和查找功能。Java 使用的 Map（根据this）是一个字典，要求键映射到值被严格映射为一对一的函数。字典可能有多个键映射到一个值，或者一个键映射到多个值（如在哈希表中链接），例如 Twitter 主题标签搜索。

作为一个更“真实世界”的例子，在字典中查找一个词可以为我们提供同一个词的多个定义，当我们找到一个条目将我们指向另一个条目（参见另一个词）时，许多词对于相同的定义列表。在现实世界中，地图要广泛得多，允许我们有名称的位置或坐标的名称，但我们也可以找到最近的邻居或其他属性（人口等），所以恕我直言，可能有更大的扩展map 类型可能具有基于图形的实现，但最好始终只假设键值对，特别是因为最近的邻居和值的其他属性都可能只是值的数据成员。

尽管存在一对一的要求，但如果值被概括为集合本身，或者如果值只是对存储在其他地方的集合的引用，则 java 映射可以实现更像通用字典的东西。

请记住，Java 维护者不是 ADT 定义的维护者，Java 决策专门针对 Java。

于 2016-07-13T14:47:42.440 回答
1

是的，它们是相同的，您可以将“关联数组”添加到组合中。

usingHashtable 或Hashaofter 是指实现。

于 2010-05-21T17:34:31.303 回答
1

这个概念的其他相当常见的术语：关联数组和哈希。

于 2010-05-21T17:18:25.333 回答
0

这是同一概念的两个不同术语。
Hashtable也HashMap指相同的概念。

于 2010-05-21T17:13:58.433 回答
0

所以在纯粹的理论层面上。

字典是可用于定位链接值的值。地图是一个值，它提供有关如何定位其他值的说明

所有允许非线性访问（即只获取第一个或最后一个）的集合都是一个映射，因为即使是一个简单的数组也有一个映射到正确值的索引。因此，虽然 Dictionary 是一种地图类型，但地图是一种更广泛的可能功能。

在实践中，它通常是定义名称的映射函数，因此 HashMap 是一种映射数据结构，它使用哈希算法将键链接到值，而字典没有指定键如何链接到值所以可以通过链表、树或任何其他算法存储。从使用端开始，您通常不关心算法只知道它们的工作原理，因此您使用通用字典，并且仅在需要执行算法类型时才转移到其他结构之一

于 2015-09-22T12:45:31.760 回答
-1

主要区别在于Map要求所有条目（值和键对）具有唯一键。如果发生冲突，即当新条目与集合中已有的条目具有相同的键时，则需要进行冲突处理。

通常，我们使用分离链处理碰撞。或线性探测。

字典允许将多个条目链接到同一个键。

当 Map 实现了分离链时，它往往类似于字典。

于 2017-06-07T09:25:20.250 回答
-2

我现在在数据结构类中，我的理解是 dict() 数据类型也可以初始化为字典 = {} 或键和值，与列表/数组数据类型基本相同用于实现堆栈和队列。因此，dict() 是类型，maps 是结果数据结构，您可以选择使用字典数据类型实现，就像您可以使用列表类型并选择使用它实现堆栈或队列数据结构一样。

于 2021-06-26T17:11:21.357 回答