STL中map和hashmap的区别是什么

Question

在C++ STL中,有两个map,map和hashmap.谁知道他们的主要区别？

Answer 1

map使用红黑树作为数据结构,因此放在那里的元素是排序的,插入/删除是O(log(n)).这些要素至少需要实施operator<.

hashmap使用散列,因此元素是未排序的,插入/删除是O(1).元素至少需要实现,operator==你需要一个哈希函数.

Answer 2

hash_map使用哈希表.这在理论上是"恒定的"时间.大多数实现使用"碰撞"哈希表.现实中发生的事情是:

• 它创造了一个大桌子
• 你的对象有一个"哈希"函数,它会在表中生成一个随机位置(随机查看,但哈希函数将始终为对象返回相同的值),通常这是实际32位的mod (或64位)散列值与表的大小.
• 该表查看空间是否可用.如果是这样,它将项目放在表格中.如果没有,它会检查那个元素是否是您要插入的元素.如果是这样,它是重复的,所以没有插入.如果不是,这称为"碰撞",它使用一些公式来查找另一个单元格,并继续直到它找到重复或空单元格.
• 当桌子被填满太多时,它会调整大小.高效(及时)实现将所有原始哈希值与元素一起存储,因此在执行此操作时不需要重新计算哈希值.此外,比较哈希值通常比比较元素更快,因此它可以在搜索时将其作为前置步骤消除大部分冲突.
• 如果你永远不删除任何东西,这很简单.但是删除元素会增加额外的复杂性.其中包含已删除元素的单元格与一直处于空白状态的单元格处于不同状态,因为您可能发生了碰撞,如果只是清空它,则无法找到这些元素.所以通常有一些"标记".当然,现在当我们想要重用单元格时,我们仍然必须向下递归以防下行副本重复(在这种情况下我们不能在此单元格中插入),然后记住重复使用已删除的单元格.
• 通常的限制是你的对象必须被实现来检查是否相等,但是Dinkumware(或它是SGI)用operator <实现它们可能更慢但是具有将元素和它们可以存储的相关容器的类型分离的优点虽然你仍然需要一个哈希函数来存储哈希.

理论上说,如果你有足够大的表,操作是恒定的时间,即它不依赖于你拥有的实际元素的数量.当然,在实践中,你遇到的元素越多,碰撞就越多.

std :: map使用二叉树.没有必要为对象定义哈希函数,只需严格排序比较.在插入时,它向下递归树以找到插入点(以及是否有任何重复项)并添加节点,并且可能需要重新平衡树以使叶子的深度永远不会超过1.重新平衡时间也相对于树的深度,因此所有这些操作都是O(log N),其中N是元素的数量.

哈希的优点是复杂性树的优点是:

• 完全可扩展.它只使用它需要的东西,不需要庞大的表或预先占用表的大小,尽管哈希可能需要每个元素比树更少的"行李".
• 不需要首先进行哈希,如果数据集不大,那么对于一个好的函数来说可能需要比比较更长的时间.

另一个问题std::map是它使用单个严格排序的比较函数,而返回-1,0或1的"compare"函数效率会更高,特别是对于最常用的键类型std :: string,已经实现了这个功能(它是char_traits::compare).(这种效率低下的前提是要检查x==y,检查,x<y然后y<x进行两次比较.每次查询只执行一次).

Answer 3

map是一棵红黑树,O(log(n))访问时间.hash_map(这不是标准的,但unordered_map将成为标准)使用(概念上)密钥的散列作为链表列表中的索引,因此具有最佳情况下的访问时间O(1)和最坏情况O(n).

见http://en.wikipedia.org/wiki/Red-black_tree

Answer 4

主要区别在于搜索时间。

对于很少的数据是更好的地图

对于大量数据来说，哈希图更好

无论如何，之前给出的技术答案是正确的。