map、hash

编程入门行业动态更新时间:2024-10-28 14:33:15

map、hash

unordered_map

转载：.html

同事告诉我用unordered_map代替hash_map，好像是标准推荐的吧。（都是哈希啦）

头文件#include <tr1/unordered_map>

命名空间using namespace std::tr1;

其他用法和hash_map一样~

随便说一点，hash_map和map的区别：

4.1 hash_map和map的区别在哪里？

构造函数。hash_map需要hash函数，等于函数；map只需要比较函数(小于函数).
存储结构。hash_map采用hash表存储，map一般采用红黑树(RB Tree)实现。因此其memory数据结构是不一样的。
4.2 什么时候需要用hash_map，什么时候需要用map?

总体来说，hash_map 查找速度会比map快，而且查找速度基本和数据量大小无关，属于常数级别;而map的查找速度是log(n)级别。并不一定常数就比log(n) 小，hash还有hash函数的耗时，明白了吧，如果你考虑效率，特别是在元素达到一定数量级时，考虑考虑hash_map。但若你对内存使用特别严格，希望程序尽可能少消耗内存，那么一定要小心，hash_map可能会让你陷入尴尬，特别是当你的hash_map对象特别多时，你就更无法控制了，而且 hash_map的构造速度较慢。

现在知道如何选择了吗？权衡三个因素: 查找速度, 数据量, 内存使用。

本文是Devour Heavens撰写整理的关于C++标准库的知识，所有资料均来自于C++官方文档，欢迎转载。但是为了尊重原作者的劳动，请注明出处！谢谢！

class template

unordered_map

template < class Key, //unordered_map::key_type

class T, //unordered_map::mapped_type

class Hash = hash<Key>, // unordered_map::hasher

class Pred =equal_to<Key>, //unordered_map::key_equal

class Alloc = allocator<pair<const Key,T> > // unordered_map::allocator_type

> class unordered_map;

Unordered Map

哈希map是一种关联容器，通过键值和映射值存储元素。允许根据键值快速检索各个元素。

在unordered_map中，键值一般用来唯一标识元素，而对应的值是一个对象关联到这个键的内容。键映射值的类型可能会有所不同。在内部unordered_map的元素不以键值或映射的元素作任何特定的顺序排序，其存储位置取决于哈希值允许直接通过其键值为快速访问单个元素（具有恒定平均的平均时间复杂度）。 unordered_map容器比map容器更快地通过键值访问他们的单个元素，虽然unordered_map一般都是比map通过其元素的一个子集范围迭代效率低。哈希map允许使用操作运算符（运算符[]）以其键值作为参数直接访问元素。