C++中的map与hash_map

Question

C++中的map与hash_map

sky*_*oor 114 c++ hashmap map

我有一个问题hash_map,并map在C++中.我明白这map是STL,但hash_map不是标准.这两者有什么区别？

Answer 1

Joe*_*Joe 132

它们以非常不同的方式实现.

hash_map(unordered_map在TR1和Boost中;使用它们)使用哈希表,其中密钥被散列到表中的一个槽中,并且值存储在与该键相关联的列表中.

map 实现为平衡二叉搜索树(通常是红/黑树).

一个unordered_map应该给表现稍好取得集合的已知元素,但map将有更多的有用的特性(例如它的排序顺序存储,这使得遍历从开始到结束). unordered_map插入和删除比a快map.

嗯,是的,如果您了解您的问题,它会有所帮助.达到一定数量级,它可能是一种清洗性能,但了解两个容器的性能特征非常重要,因为随着数据量变大,它们会以不同的方式发生偏差. (24认同)
我对你的表现并不完全赞同.性能受到许多参数的影响,我会责怪任何程序员使用unordered_map只有10个条目因为"它更快".首先担心接口/功能,稍后再考虑性能. (7认同)
有趣的是,我只是在一个应用程序中用一个boost :: unordered_map交换了一个std :: map,在这个应用程序中我进行了大量的随机查找,但是也迭代了地图中的所有键.我在查找中节省了大量时间,但通过迭代获得了回报,因此我切换回地图并寻找其他方法来提高应用程序性能. (7认同)
@ErikGarrison如果你使用随机访问和迭代比插入和删除元素要多得多,你可以在树和hash_map中使用你的对象(通过将指针或更好的shared_ptr存储到两者中的相同对象)你正在使用实际情况的情况).然后,您将通过hash_map和O(n)迭代时间通过地图获得O(1)时间访问时间.当然,你必须记住每次都添加和删除指针.您可以轻松编写一个自定义容器类(可能也将其模板化),以便为您封装此行为. (4认同)
@ErikGarrison 当然，如果您尝试这种方法，您将需要支付少量的额外空间。但是，由于您将使用指针，因此不应过多。如果你真的想要，你可以过度，编写你自己的 AVL 实现，并使用节点指针作为 hash_map 中的数据类型，这将使你 O(1) 时间访问树中的节点，从中您将能够线性地迭代到您需要的任何地方。当然，这将涉及相当多的编码，我不确定它是否会有回报，除非您需要在随机访问位置之间进行大量迭代。 (2认同)

Answer 2

小智 35

hash_map是许多库实现提供的常见扩展.这就是为什么它被重命名为unordered_map当它作为TR1的一部分被添加到C++标准时.map通常使用平衡的二叉树(如红黑树)实现(当然实现方式不同). hash_map并且unordered_map通常用哈希表实现.因此不保持订单. unordered_mapinsert/delete/query将为O(1)(常量时间),其中map将为O(log n),其中n是数据结构中的项数.所以unordered_map更快,如果你不关心项目的顺序应该是首选map.有时你想维持秩序(按键排序),map这是选择.

我会指出,当可能发生冲突时,hashmap具有O(N)的最坏情况访问(错误的散列fcn,加载因子太高等) (9认同)

Answer 3

R S*_*hko 14

一些关键差异在于复杂性要求.

映射需要O(log(N))时间才能插入和查找.

对于插入和查找,unordered_map要求"平均"时间为O(1),但允许最坏情况时间为O(N).

因此,通常,unordered_map会更快,但根据您存储的密钥和散列函数,可能会变得更糟.

归档时间：	15 年，8 月前
查看次数：	147366 次
最近记录：	6 年，7 月前