⭐上篇文章：36.C++二叉树进阶5（平衡二叉搜索树 - 红黑树及其插入操作图解）-CSDN博客
⭐本篇代码：c++学习/20.哈希与哈希表 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)
⭐标⭐是比较重要的部分
unordered_set/unordered_map是无序关联式容器。之前使用的STL中的set/map是树形关联容器，set/map的底层是红黑树，其增删查的效率为log(N)。
而C++11提供了unordered_set/unordered_map底层是哈希+链表，其增删查改的平均效率为O(1)，最坏情况(所有元素都哈希冲突，这种情况几乎不存在)下为O(n)
一. unordered_set/map的使用
unordered_set/unordered_map的文档如下：
unordered_set - C++ Reference (cplusplus.com)unordered_map - C++ Reference (cplusplus.com)
使用unordered_set/unordered_map需要包含头文件
#include <unordered_set>
#include <unordered_map>unordered_set/unordered_map的接口与set/map非常类似，很多接口的使用方法几乎是一样的。唯一的区别是set/map支持去重和排序，遍历set/map的结果是有序的。
而unordered_set/unordered_map支持去重，但是不支持排序，遍历出来是无序的。
1.1 set与unordered_set对比
通过对比这两个容器，我们可以更好理解两种容器的差别。
#include <iostream>
#include <unordered_set>
#include <set>
using namespace std;void test1()
{set<int> s1;unordered_set<int> us2;// set插入数据for (int i = 0; i < 10; i++){int num = rand() % 1000;s1.insert(num);s1.insert(num);}// unprdered_set插入数据for (int i = 0; i < 10; i++){int num = rand() % 1000;us2.insert(num);us2.insert(num);}// 遍历setcout << "set:";for (const auto &e : s1)cout << e << " ";// 遍历unorderedd_setcout << endl<< "unordered_set:";for (const auto &e : us2)cout << e << " ";cout << endl;
}int main()
{srand(time(0));test1();
}在上面的代码中，我们向set和unordered_set中都插入10的随机值，并且每一个随机值都会被再一次插入到容器中。用于判断两个容器是否支持去重
然后通过遍历来确定容器是否支持排序，运行结果如下：
可以看到，两个容器都支持去重这个功能，并且set是支持排序的，而unordered_set是不支持排序的。
1.2 unordered_map使用简介
unordered_map的接口与map的接口几乎一样，并且支持[]操作。这里使用unordered_map来实现一个简单的字典。注意：unordered_map插入的是一个键值对pair<k,v>
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;void test1()
{unordered_map<string, string> um;um.insert(make_pair("sort", "排序"));um.insert(make_pair("string", "字符串"));um.insert(make_pair("apple", "苹果"));um.insert(make_pair("int", "整形"));um["double"] = "浮点型";// 使用迭代器遍历unordered_mapauto it = um.begin();while (it != um.end()){cout << it->first << ":" << it->second << " ";++it;}cout << endl;while (true){string s;cout << "输入你想要查找的单词:";cin >> s;if (um.find(s) != um.end())cout << um[s] << endl;elsecout << "该单词不存在" << endl;}
}int main()
{test1();
}运行结果如下：
二. 哈希在算法题中的使用
leetcode350.两个数组的交集
350. 两个数组的交集 II - 力扣（LeetCode）
思路：
遍历数组1，然后插入到哈希表中，如果哈希表存在这个数，则让其Value值加1。这样一来我们就知道了数组1有哪些元素，并且这些元素的数量是多少个。
然后遍历数组2，判断每一个元素是否在哈希表中，如果有则说明这个元素属于交集，插入到vector中，然后让该元素的Value--表示这个交集元素已经被找到了
class Solution {
public:vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {vector<int> ans;unordered_map<int,int> um;for(const auto &e : nums1)um[e]++;for(const auto&e : nums2){if(um[e] > 0){um[e]--;ans.push_back(e);}}return ans;}
};leetcode1.两数之和
1. 两数之和 - 力扣（LeetCode）
思路：
最简单的思路就是两次循环遍历，找到两个值相加等于target即可。不过这样做的效率过低。
使用哈希能够一次遍历就能完成，首先循环遍历数组，遇到每一个数字，判断这个target - 这个数字有没有在哈希表中。如果有，说明这两个数字就是我们需要的，否则将该数字和其下标<num[i], i>插入到哈希表中。
class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> help;for (int i = 0; i < nums.size(); i++) {if (help.count(target - nums[i]))return {help[target - nums[i]], i};elsehelp.insert(make_pair(nums[i], i));}return {-1, -1};}
};
