在STL中STL

Question

与C++ STL中的map和hashmap有什么区别，有两个map，map和hashmap。任何人都知道他们的主要区别？

Answer 1

地图采用了红黑树的数据结构，所以你把元素有排序，插入/删除是O（日志（N））。元素需要至少实现operator<。

散列映射使用散列，所以元件未排序，插入/删除是O（1）。元素至少需要实现operator==，并且您需要散列函数。

Answer 2

map是红黑树，O(log(n))访问时间。 hash_map（这不是标准，然而unordered_map将成为标准）使用（在概念上）一个在链表的阵列的关键字作为索引的散列，并因此具有的O(1)最好的情况存取时间和O(n)最坏情况。

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

Answer 3

主要区别在于搜索时间。

的几个数据是更好的地图

的大量数据是更好的HashMap

反正前面给出的答案软件Tecnical是正确的。

Answer 4

hash_map使用散列表。理论上这是“不变的”时间。大多数实现使用“碰撞”散列表。会发生什么事在现实中是：

• 它创建了一个大桌子
• 你必须为你的对象“散列”功能，生成您随机发生在表（随机寻找，但是哈希函数永远会返回与你的对象相同的值），通常这是实际的32位（或64位）散列值与表的大小的模。
• 该表查看空间是否可用。如果是这样，它将项目放在表格中。如果不是，它会检查是否存在您正在尝试插入的元素。如果是这样，它是重复的，所以没有插入。如果不是，则称为“碰撞”，它使用一些公式来查找另一个单元格，并继续执行，直到它找到一个重复单元格或一个空单元格。
• 当表格被填满太多时，它会调整大小。一个有效的（及时的）实现将所有的原始散列值与元素一起存储起来，因此当它这样做时不需要重新计算散列值。此外，比较哈希通常比比较元素更快，所以它可以在搜索时做到这一点，以消除大部分碰撞作为前期步骤。
• 如果你从不删除任何东西，那很简单。但是删除元素会增加额外的复杂性。一个已经被删除的元素的单元格与一直处于空白状态的单元格处于不同的状态，因为您可能发生了冲突，并且如果您只是将其清空，则将找不到这些元素。所以通常有一些“标记”。当然，现在当我们想要重用单元格时，如果存在重复的更低下（在这种情况下，我们无法在此单元格中插入），我们仍然不得不减弱，然后记住重新使用已删除的单元格。
• 通常的约束是你的对象必须执行检查的平等，而是Dinkumware的（或者说是SGI）来实现他们与运营商<可能会比较慢，但有脱钩的元件和相关容器的类型的优势，他们可以存储在中，尽管你仍然需要一个散列函数来存储散列。

理论是，如果你有一个足够大的表，操作是恒定的时间，即它不取决于你有实际元素的数量。当然，在实践中，发生更多碰撞的元素越多。

std :: map使用二叉树。没有必要为一个对象定义一个散列函数，只是严格地排序比较。插入时，向下递归搜索树以找到插入点（以及是否有任何重复项）并添加节点，并且可能需要重新平衡树，以便树叶的深度永远不会超过1。再平衡时间也与树的深度有关，所以所有这些操作都是O（log N），其中N是元素的数量。

散的优点是复杂 树的优点是：

• 完全可扩展的。它只使用它需要的东西，不需要一个巨大的表格或预先占据表格的大小，虽然哈希每个元素可能需要比树更少的“包袱”。
• 不需要首先进行哈希，如果数据集不是很大，那么对于一个好的函数来说，这可能需要比比较更长的时间。

另外一个问题与std::map是，它使用一个单一的严格有序的比较函数，而该返回-1，0或1将是一个很大更有效率，特别是最常用的键“比较”功能类型，std :: string，它已经实现了这个功能（它是char_traits::compare）。 （这种效率低下的前提是要检查x==y，你检查x<y和y<x，这样你就可以进行两次比较了，每次查找只做一次）。