C++ unordered_map
hash_map ≈ unordered_map
最初的 C++ 标准库中没有类似 hash_map 的实现，但不同实现者自己提供了非标准的 hash_map。 因为这些实现不是遵循标准编写的，所以它们在功能和性能保证方面都有细微差别。
从 C++ 11 开始，hash_map 实现已被添加到标准库中。但为了防止与已开发的代码存在冲突，决定使用替代名称 unordered_map。这个名字其实更具描述性，因为它暗示了该类元素的无序性。
unordered_map 原理
hashtable + bucket
由于 unordered_map 内部采用 hashtable 的数据结构存储，所以，每个特定的 key 会通过一些特定的哈希运算映射到一个特定的位置，我们知道，hashtable 是可能存在冲突的，在同一个位置的元素会按顺序链在后面。所以把这个位置称为一个 bucket 是十分形象的，每个哈希桶中可能没有元素，也可能有多个元素。
其插入过程是：
1、得到 key；
2、通过 hash 函数得到 hash 值；
3、得到桶号（一般都为 hash 值对桶数求模）；
4、存放 key 和 value 在桶内（发生冲突，用比较函数解决）。
其取值过程是：
1、得到 key
2、通过 hash 函数得到 hash 值
3、得到桶号（一般都为 hash 值对桶数求模）
4、比较桶的内部元素是否与 key 相等，若都不相等，则没有找到。
5、取出相等的记录的 value。
总结其特点如下：
- 关联性：通过 key 去检索 value，而不是通过绝对地址（和顺序容器不同）
- 无序性：使用 hash 表存储，内部无序
- Map : 每个值对应一个键值（unordered_map<Key, Value> 的元素类型是 std::pair<const Key, Value>。如果有某个元素的Value部分的地址，减去 offsetof(std::pair<const Key, Value>, second) 再加上 offsetof(std::pair<const Key, Value>, first) （虽然估计是 0，不加也没事），就是对应的 Key 部分的地址）
- 键唯一性：不存在两个元素的 key 一样（unordered_multimap 可以存放相同相同 key）
- 动态内存管理：使用内存管理模型来动态管理所需要的内存空间
unordered_map 实现
unordered_map 类的定义：
// 通常只用得到前两个 <Key, Ty>
template <class Key,
class Ty,
class Hash = std::hash<Key>,
class Pred = std::equal_to<Key>,
class Alloc = std::allocator<std::pair<const Key, Ty>>>
class unordered_map;
| 参数 | 描述 |
|---|---|
| Key | 密钥类 |
| Ty | 映射类 |
| Hash | 哈希函数对象类 |
| Pred | 相等比较函数对象类 |
| Alloc | allocator 类 |
unordered_map 使用
头文件：
#include <unordered_map>
取得键和值：
unordered_map<Key,T>::iterator it;
it->first; // same as (*it).first (the key value)
it->second; // same as (*it).second (the mapped value)
成员函数：
===================迭代器====================
begin | 返回指向容器起始位置的迭代器（iterator）
end | 返回指向容器末尾位置的迭代器
cbegin | 返回指向容器起始位置的常迭代器（const_iterator）
cend | 返回指向容器末尾位置的常迭代器
===================Capacity===================
size 返回有效元素个数
max_size 返回 unordered_map 支持的最大元素个数
empty 判断是否为空
===================元素访问===================
operator[] 访问元素
at 访问元素（如 m.at(5) = 3.33）
===================元素修改===================
insert 插入元素
erase 删除元素
swap 交换内容
clear 清空内容
emplace 构造及插入一个元素
emplace_hint 按提示构造及插入一个元素
=====================操作=====================
find 通过给定主键查找元素
count 返回匹配给定主键的元素的个数
equal_range 返回值匹配给定搜索值的元素组成的范围
===================Buckets====================
bucket_count 返回槽（Bucket）数
max_bucket_count 返回最大槽数
bucket_size 返回槽大小
bucket 返回元素所在槽的序号
load_factor 返回载入因子，即一个元素槽（Bucket）的最大元素数
max_load_factor 返回或设置最大载入因子
rehash 设置槽数
reserve 请求改变容器容量
