我知道map是一种将键映射到值的数据结构。字典不也是这样吗?地图和字典的区别是什么?
1. 我不是问它们在语言X或Y中是如何定义的(这似乎是人们在这里问的),我想知道它们在理论上有什么不同。
我知道map是一种将键映射到值的数据结构。字典不也是这样吗?地图和字典的区别是什么?
1. 我不是问它们在语言X或Y中是如何定义的(这似乎是人们在这里问的),我想知道它们在理论上有什么不同。
当前回答
这是同一个概念的两个不同术语。 Hashtable和HashMap也引用相同的概念。
其他回答
这是同一个概念的两个不同术语。 Hashtable和HashMap也引用相同的概念。
一个是另一个的旧说法。通常,“字典”一词是在数学术语“地图”占主导地位之前使用的。此外,字典倾向于有键类型的字符串,但这并不是100%正确的。
主要的区别是Map要求所有的条目(值和键对)都有一个唯一的键。如果发生冲突,即当一个新条目与集合中已经存在的条目具有相同的键时,则需要冲突处理。
通常,我们使用分离链接来处理冲突。或者线性探测。
Dictionary允许将多个条目链接到同一个键。
当Map实现了独立链接时,它就趋向于字典。
这个概念的其他术语相当常见:关联数组和哈希。
其实不是一回事。映射是字典的一个子集。Dictionary在这里定义为具有插入、删除和查找函数。Java使用的Map(根据本文)是一个字典,它要求键映射到值严格地映射为一对一的函数。一个字典可能有多个键映射到一个值,或者一个键映射到几个值(如hashtable中的链接),例如Twitter标签搜索。
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映射可以实现更类似于广义字典的东西。
请记住,Java维护者不是ADT定义的维护者,Java决策是专门针对Java的。