C++ hash table and related stuff
1. 引入
主要涉及的模板类有set/unordered_set/map/unordered_map。其中，无unordered前缀的版本（即set和map）均内部实现红黑树，而unordered_set和unordered_map内部实现哈希表。此外，map组与set组之间区别在于内部数据形式，set组均为单一数据，而map组则为std::pair格式的键值对，先key，再value。
插入部分：std::pair的简单用法
- 主成员变量first和second是成员变量，不是成员函数，不用加括号
- 构造语句写法和vector完全一样，可以有如下方式：
std::pair<int, int> ppp = {1, 2};
std::pair<int, int> ppp(1, 2);
std::pair<int, int> ppp{1, 2};
- 使用make_pair构造右值pair时，无需传入模板类型，即直接uMap.insert(make_pair(1, "str"))即可。
- 当然使用正常的右值pair构造时就需要传入模板类型，如uMap.insert(pair<int, bool>(1, true));
2. 红黑树与哈希表容器的简单对比
红黑树map/set：
- 优点：
- 有序性，最大的优点，其元素的有序性在很多应用中都会简化很多的操作
- 高效且稳定，查询、插入操作时间复杂度稳定为O(logN)
- 缺点：
- 空间占用率高，以红黑树作为内部实现时，每一个节点都需要额外保存父节点、孩子节点和红/黑性质等数据字段，使得每一个节点都占用大量的空间
- 查找的平均时间不如哈希表
- 适用处： 对数据排序有顺序要求的场景
哈希表 unordered_map/unordered_set：
- 优点：
- 效率极高，查询和插入的平均时间复杂度为O(1)
- 缺点：
- 无序性
- 哈希表的建立比较耗时
- 在部分情况下，性能不稳定。比如当大量插入数据时，可能触发大量rehash；当哈希函数设置不合理时，冲突过多，单次查询/插入操作最坏时间复杂度达到O(N)
- 适用处： 高效率的查找场景
对比小结：
在需要元素有序性或者对单次查询性能要求较为敏感时，请使用map/set，其余情况下应使用unordered_map/unorderer_set。
刷题踩的坑
哈希表好归好，但是需要格外注意其无序性。若需要用到哈希表将一个数组进行散列化，由于哈希表内部的无序，往往需要用unordered_map保存元素的原始数组下标。即：键值对中，key为nums[i]，value为i。
3. 常用成员函数
- insert 插入数据。返回值是一个pair，其second值是一个bool变量，代表插入是否冲突
- find 查询数据。返回值是iterator，如果查找失败，则返回值等于end()；此外也可以用count查询数据，查询成功为1，否则为0
- 修改数据的时候，可以用iterator或者operator[]，如下所示：
unordered_map<int, int> uMap;
uMap.insert(pair<int, int>(1, 1));
uMap.insert(make_pair(2, 2));
auto iter = uMap.find(2);
++(*iter).second;
cout << uMap[2] << endl;
++uMap[2];
cout << uMap[2] << endl;
但是需要注意，operator[]在键值不存在的时候会直接进行数据的插入，然后再返回其映射值的引用。当你不确定某键值是否存在于哈希表中，请使用find而非operator[]。
- erase删除数据。参数可以是键值，可以是一个迭代器，可以是两个迭代器[left, right]。
uMap.erase(1);
uMap.erase(iter);
uMap.erase(uMap.begin(), uMap.end());
4. 一些比较有启发的用法
LeetCode-17 电话号码的字母组合
unordered_map<char, string> table{
{'0', " "}, {'1',"*"}, {'2', "abc"},
{'3',"def"}, {'4',"ghi"}, {'5',"jkl"},
{'6',"mno"}, {'7',"pqrs"},{'8',"tuv"},
{'9',"wxyz"}};
