GESP7级C++考试语法知识（四、哈希表（6、快速判断是否存在）
第六课：《失踪宝石调查队——快速判断是否存在》
一、国王的宝石失踪了！
1、一天早晨。
程序王国的国王刚刚起床。
忽然发现：
💎 王者宝石不见了！
2、国王大喊：
“不好啦！”
“我的宝石丢了！”
3、整个王国立刻行动起来。
成立了一支特别小队：
🕵️ 失踪宝石调查队
4、队长小智接到任务：
“请立刻调查！”
“看看宝石是否还在仓库里！”
二、最笨的调查方法
1、仓库里有很多箱子：
红宝石 蓝宝石 绿宝石 黄金 钻石 银币2、现在要找：
钻石3、最笨的方法：
看第1个箱子 ↓ 不是 ↓ 看第2个箱子 ↓ 不是 ↓ 看第3个箱子 ↓ 不是一直找到最后。
4、如果有：
100万件宝物怎么办？
😨
三、智慧大臣的新武器
1、智慧大臣说：
“别傻找了！”
“我们有哈希表呀！”
2、于是他拿出：
unordered_map<string,int> mp;3、记录：
红宝石 → 1 蓝宝石 → 1 绿宝石 → 1 黄金 → 1 钻石 → 14、这里：
Key表示：
宝物名字5、而：
Value其实不重要。
6、重要的是：
这个宝物在不在四、调查队的问题
1、调查队经常问：
钻石存在吗？ 黄金存在吗？ 珍珠存在吗？2、这种问题其实都是：
是否存在
3、而不是：
出现多少次4、所以今天我们要学习：
快速判断是否存在
五、第一个神器：count()
1、假设仓库：
unordered_map<string,int> mp; mp["红宝石"] = 1; mp["蓝宝石"] = 1; mp["钻石"] = 1;2、现在调查：
钻石在吗？3、代码：
cout << mp.count("钻石");输出：
1表示：
存在六、如果不存在呢？
1、调查：
珍珠在吗？2、代码：
cout << mp.count("珍珠");输出：
0表示：
不存在是不是特别方便？
七、count() 的含义
1、记住：
mp.count(x)意思：
x在不在哈希表里？2、返回值只有两种：
1 → 存在 0 → 不存在3、因为：
unordered_map里面一个 Key 只能有一个。
所以不会出现：
2次 3次 5次八、最经典写法
1、调查钻石：
if(mp.count("钻石")) { cout << "找到了"; } else { cout << "没找到"; }2、如果存在：
找到了否则：
没找到九、宝石调查系统
完整程序：
#include <iostream> #include <unordered_map> using namespace std; int main() { unordered_map<string,int> mp; mp["红宝石"] = 1; mp["蓝宝石"] = 1; mp["钻石"] = 1; string x; cin >> x; if(mp.count(x)) cout << "存在"; else cout << "不存在"; return 0; }输入：
钻石输出：
存在输入：
珍珠输出：
不存在十、第二个神器：find()
1、调查队里还有另一位高手。
他喜欢使用：
find()2、例如：
mp.find("钻石")意思：
去仓库找钻石十一、find() 返回什么？
1、如果找到：
mp.find("钻石")返回：
宝石位置2、如果找不到：
返回：
mp.end()3、所以经典写法：
if(mp.find("钻石") != mp.end()) { cout << "找到"; } else { cout << "没找到"; }十二、count() 与 find() 对比
方法1
mp.count(x)适合：
只关心存在不存在例如：
宝石在吗？方法2
mp.find(x)适合：
还想拿到数据位置例如：
找到这个人 然后查看信息十三、查重问题来了
1、调查队又接到新任务。
输入：
5 2 7 1 3突然又来了一个：
72、调查队问：
7是不是已经出现过？
十四、哈希表秒杀查重
建立仓库：
unordered_map<int,int> mp;读到：
5存进去：
mp[5] = 1;读到：
2存进去：
mp[2] = 1;读到：
7存进去：
mp[7] = 1;后来又来了：
7判断：
if(mp.count(7))发现：
存在说明：
7重复出现了十五、经典题：判断是否有重复数字
1、输入：
1 5 2 7 3 5看到：
1不存在。
记录。
看到：
5不存在。
记录。
看到：
2不存在。
记录。
看到：
7不存在。
记录。
看到：
3不存在。
记录。
2、看到：
5发现：
mp.count(5)结果：
1说明：
5重复了十六、完整代码
#include <iostream> #include <unordered_map> using namespace std; int main() { int n; cin >> n; unordered_map<int,int> mp; for(int i=0;i<n;i++) { int x; cin >> x; if(mp.count(x)) { cout << "发现重复数字：" << x << endl; } mp[x] = 1; } return 0; }十七、时间复杂度为什么快？
1、假设：
100万个数字2、普通方法：
每来一个数字。
都去前面找。
复杂度：
O(n²)3、哈希表：
mp.count(x)平均：
O(1)总复杂度：
O(n)快得多！
十八、比赛中的高频应用
1、以后看到下面这些词：
是否出现过 是否存在 查重 重复数字 重复单词 黑名单 白名单 访问记录2、第一反应：
unordered_map或者：
unordered_set
unordered_set是unordered_map的"阉割版"——去掉了 value，只留 key，专用于去重和存在性判断。
十九、小试牛刀
1、仓库：
苹果 香蕉 橘子2、问题1：
苹果存在吗？答案：
存在3、问题2：
西瓜存在吗？答案：
不存在4、问题3：
判断代码：
if(mp.count("苹果"))条件成立吗？
答案：
✅ 成立
本课总结
1、今天我们学会了哈希表第二大应用：
快速判断是否存在
2、核心函数：
mp.count(x)含义：
x存在吗？返回：
1 → 存在 0 → 不存在3、另一种写法：
mp.find(x)4、经典应用：
✅ 查重
✅ 判断存在
✅ 黑名单
✅ 白名单
✅ 访问记录
5、经典模板
判断是否存在：
if(mp.count(x)) { cout << "存在"; } else { cout << "不存在"; }查重：
if(mp.count(x)) { cout << "重复"; } mp[x] = 1;6、魔法口诀
哈希仓库真奇妙， 找东西根本不用找。 count一下马上知， 存在不存在全知道。 查重复，查名单， 哈希表最擅长。 统计次数用++， 判断存在用count！下一课我们将认识哈希表的亲兄弟：
《魔法通讯录——认识 unordered_set》
你会发现：
🤔
有时候我们根本不关心 Value！
只关心：
这个东西在不在？这时unordered_set就要闪亮登场了！🚀